二維圖形封閉區(qū)域自動(dòng)識(shí)別算法

艾迪，周云燕，萬(wàn)里兮

（中國(guó)科學(xué)院微電子研究所 北京 100029）

微電子領(lǐng)域，常用的商用仿真軟件如Cadence，HFSS，對(duì)于實(shí)體、層、網(wǎng)格等等單元的操作都會(huì)大量使用到多邊形處理的各種算法。比如鼠標(biāo)點(diǎn)擊選中相應(yīng)單元的操作需要用到點(diǎn)是否在多邊形內(nèi)的算法；繪制版圖時(shí)需要大量用到多邊形的合并，分割、刪除等算法。這些軟件只能對(duì)已經(jīng)存在的多邊形進(jìn)行這些操作。然而有些時(shí)候從DXF文件導(dǎo)入的版圖中僅含有線段信息，不含多邊形信息；或者需要對(duì)橢圓、圓弧等其他實(shí)體圍成的封閉區(qū)域進(jìn)行這種類(lèi)似多邊形操作。對(duì)于這些情況這些軟件就無(wú)能為力。本文在實(shí)際電磁仿真軟件開(kāi)發(fā)的基礎(chǔ)上提出的圖形封閉區(qū)域識(shí)別算法很好的解決了這個(gè)問(wèn)題。

這種識(shí)別算法輸入可以是任意的線段、圓弧信息，輸出則為所有的封閉區(qū)域（包含多邊形）。在處理過(guò)程中首先需要對(duì)于已知線段集合求出所有交點(diǎn)信息。而這種求交點(diǎn)已經(jīng)有了快速高效的算法。本文應(yīng)用了這種高效的算法，并增加了它的適應(yīng)性以支持圓弧。在封閉區(qū)域的搜索過(guò)程中，本文采用了一種類(lèi)似于計(jì)算機(jī)圖形學(xué)中廣泛應(yīng)用的圖的廣度優(yōu)先遍歷搜索算法。該算法原本目的是路徑搜索發(fā)現(xiàn)，本文在算法實(shí)現(xiàn)過(guò)程中加以修改，拓展了圖的相鄰表儲(chǔ)存結(jié)構(gòu)，使之能夠發(fā)現(xiàn)圖中封閉的區(qū)域，同時(shí)又保持了算法本身低時(shí)間復(fù)雜度的特性。

1 基本理論

在二維的計(jì)算幾何學(xué)問(wèn)題中，每個(gè)輸入單元都用一個(gè)點(diǎn)的集合{pn}來(lái)表示，其中每個(gè) pi=（xi，yi），xi∈R，yi∈R。 輸入單元可以是簡(jiǎn)單的點(diǎn)、線段、圓弧或是多邊形，在本文的算法中還有可能是一段折線。用點(diǎn)集表示多邊形P時(shí)，可以按照在P的邊界上出現(xiàn)的逆時(shí)針或是順時(shí)針順序排列的頂點(diǎn)序列來(lái)（p1，p2，…，pn）表示。

對(duì)于圓弧，一般計(jì)算機(jī)中需要用3組信息來(lái)儲(chǔ)存，分別是圓弧的起點(diǎn)、終點(diǎn)以及弧度值大小。圓弧可能是圓的一部分，也有可能是一段任意的曲線。在本文的算法中，對(duì)圓弧的處理只會(huì)用到圓弧與其他單元的交點(diǎn)，以及圓弧上點(diǎn)的次序。因此在計(jì)算完交點(diǎn)后，圓弧可以當(dāng)作一般線段處理，即可用圓弧上順序排列的點(diǎn)（p1，p2，…，pn）來(lái)表示。

本算法與一些其他圖像識(shí)別算法（如文獻(xiàn)[1]）不同之處在于輸入為點(diǎn)集{pn}表示的線條信息，輸出結(jié)果為一系列頂點(diǎn)（p1，p2，…，pn）表示的封閉區(qū)域。 這種結(jié)果的表示形式可以用來(lái)做很多后續(xù)計(jì)算。因此本算法可以成為很多其他圖形算法的接口。例如：多邊形的剪裁[2-3]，判斷點(diǎn)與多邊形的位置關(guān)系[4]等。

文中討論的多邊形都屬于簡(jiǎn)單多邊形。簡(jiǎn)單多邊形具有下列性質(zhì)：1）所有頂點(diǎn)各不相同， 即：坌i≠j?v≠v；2）任何頂點(diǎn)都只屬于它所在的邊；3）任意兩條邊都不相交。本文算法輸出的封閉區(qū)域結(jié)果也符合上述性質(zhì)。

1.1 求交點(diǎn)

在輸入任意線段、圓弧等信息后，本文算法第一步為求出它們之間所有的交點(diǎn)。方法如下：

第一步：先求出所有線段的交點(diǎn)。輸入的線段可能存在很多特殊情況，如兩條線段有一部分重合，或是互相垂直。文獻(xiàn)[5]中的Bentley-Ottmann（1979）算法能夠很好應(yīng)對(duì)這些情況。如果N條線有K個(gè)交點(diǎn)，該算法能在O（N+K）log N的時(shí)間復(fù)雜度下計(jì)算完所有的交點(diǎn)，而不會(huì)有遺漏。文獻(xiàn)[6]給出了求單個(gè)交點(diǎn)的方法，它與上述算法結(jié)合使用。

第二步：增加圓弧的處理。由于圓弧的特殊性，一段圓弧與一條線段可能有多個(gè)交點(diǎn)，并且第一步算法中采用的掃描線判斷線段順序的方法對(duì)于圓弧不再有效，因此需要單獨(dú)計(jì)算出每個(gè)圓弧與其他部分交點(diǎn)。

所有交點(diǎn)都計(jì)算出后，可以根據(jù)這些信息構(gòu)建出一個(gè)圖G=（V，E），如圖 1（a），V 為交點(diǎn)，圖中用圈表示，E 為其中 2個(gè)交點(diǎn)相連的邊界。對(duì)于圓弧則可以忽略其弧度信息，當(dāng)作普通的線段邊界E進(jìn)行處理。

圖1 無(wú)向圖和對(duì)應(yīng)的擴(kuò)展鄰接表結(jié)構(gòu)Fig.1 An undirected graph and its extended adjacency-list representation

1.2 擴(kuò)展的鄰接表表示法

在本文算法中采用了圖G=（V，E）的鄰接表[7]表示方法。這種方法的好處是表示稀疏圖（圖形的邊界數(shù)E遠(yuǎn)小于頂點(diǎn)數(shù)V的平方）比較簡(jiǎn)潔緊湊。一般版圖結(jié)構(gòu)中多邊形結(jié)構(gòu)占了主要部分，因此屬于稀疏圖的范疇。另一種好處是本算法需要從一個(gè)源點(diǎn)進(jìn)行廣度遍歷向外擴(kuò)展搜尋，而發(fā)現(xiàn)的封閉區(qū)域信息則就地儲(chǔ)存在節(jié)點(diǎn)中。鄰接表節(jié)點(diǎn)的鏈表結(jié)構(gòu)，在本例中稍加修改和擴(kuò)展就能滿足一些封閉區(qū)域識(shí)別的需求，如存儲(chǔ)封閉區(qū)域的路徑信息。

在本文算法中，將鄰接表結(jié)構(gòu)擴(kuò)展如圖1（b）所示。將每個(gè)節(jié)點(diǎn)增加了4種數(shù)據(jù)結(jié)構(gòu)。它們分別作用為：COLOR代表節(jié)點(diǎn)的顏色，這樣是為了保持搜索的軌跡；P代表這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)；D代表本節(jié)點(diǎn)到源節(jié)點(diǎn)的距離；M是個(gè)鏈表結(jié)構(gòu)，它記錄著已發(fā)現(xiàn)的封閉區(qū)域相關(guān)信息。4種數(shù)據(jù)缺一不可。

1.3 基于廣度優(yōu)先算法的封閉區(qū)域發(fā)現(xiàn)算法

廣度優(yōu)先算法又可以叫寬度優(yōu)先算法，在計(jì)算機(jī)圖形學(xué)中廣為應(yīng)用，是最簡(jiǎn)便和直觀的圖的搜索算法之一，在文獻(xiàn)[7]中有詳細(xì)介紹。它的直接目的是遍歷搜索圖和尋找最短路徑。本文算法采用了和廣度優(yōu)先搜索算法類(lèi)似的思想用于搜索圖中封閉區(qū)域。原理如下：

已知圖G=（V，E）和一個(gè)源頂點(diǎn)s，廣度優(yōu)先算法以一種系統(tǒng)的方式搜索G的邊，從而遍歷s能達(dá)到的所有頂點(diǎn)。這種算法一直通過(guò)一條已找到和未找到頂點(diǎn)之間的邊界擴(kuò)展。具體做法為將位于這條邊界的點(diǎn)著上灰色，表明下一步要從這些點(diǎn)向外搜索；將已經(jīng)經(jīng)過(guò)的點(diǎn)著上黑色作為標(biāo)識(shí)，使搜索不致走回頭路。其它未探索的點(diǎn)為白色。圖2（a）所示為算法初始階段。經(jīng)過(guò)一輪搜索，灰色邊界點(diǎn)附近的白色點(diǎn)都被發(fā)現(xiàn)并標(biāo)上灰色，而之前的灰色點(diǎn)由于完成了對(duì)附近點(diǎn)的搜索就被標(biāo)上了黑色，如圖2（b）。算法繼續(xù)重復(fù)這個(gè)過(guò)程以發(fā)現(xiàn)更多的外圍點(diǎn)，如圖 2（c）。

圖2 廣度優(yōu)先搜索算法Fig.2 Breadth-first-search procedure

這樣如此反復(fù)，最終所有可到達(dá)的白色點(diǎn)都被發(fā)現(xiàn)。因此這種廣度搜索算法的由內(nèi)向外遍歷所有點(diǎn)的性質(zhì)滿足了本文算法需要搜索出圖中所有封閉區(qū)域的基本要求。

更進(jìn)一步觀察，這種廣度搜索算法就如向縱橫交錯(cuò)的溝渠中倒一桶水，水沿著溝渠的路徑向四面八方擴(kuò)展開(kāi)去，最終到達(dá)所有位置。如果圖中有封閉區(qū)域，就像溝渠中一個(gè)環(huán)路，在水流向四周蔓延時(shí)肯定會(huì)有兩股水流于某一時(shí)刻在環(huán)路另一端相遇。如在圖2（b）的封閉區(qū)域1旁，探索分支s→m與 s→n 在 E（m，n）這條邊“相遇”；在圖 2（c）的封閉區(qū)域 2旁，探索分支m→r與n→r在同一個(gè)r點(diǎn)“相遇”。

由于圖中有封閉環(huán)路時(shí)兩個(gè)探索分支會(huì)“相遇”，并且走在最前的點(diǎn)一定是灰色點(diǎn)，因此在廣度優(yōu)先算法遍歷過(guò)程中，如果兩個(gè)灰色點(diǎn)“相遇”，那么就可以判斷發(fā)現(xiàn)了一個(gè)封閉區(qū)域。

2 封閉區(qū)域分離算法

本文封閉區(qū)域分離算法的關(guān)鍵就在如何對(duì)圖進(jìn)行廣度優(yōu)先遍歷時(shí)兩個(gè)灰色點(diǎn)相遇的情況進(jìn)行判斷和記錄。在最后，算法還需要通過(guò)這個(gè)相遇信息完整提取出所有封閉區(qū)域信息，并以在這些區(qū)域邊界上按順序排列的頂點(diǎn)集{Pn}的形式表示出。

2.1 記錄相遇點(diǎn)

在對(duì)圖進(jìn)行廣度優(yōu)先搜索時(shí)，灰色點(diǎn)相遇會(huì)存在2種情況。這2種情況可以分別用圖3的（a）、（b）來(lái)表示。

圖3 灰色點(diǎn)相遇的兩種情況Fig.3 Two cases of grey points encounter

直觀上來(lái)看，第一種情況是灰色邊界中有兩個(gè)或兩個(gè)以上灰色點(diǎn)“相鄰”，如圖 3（a）中的 n、x、y這 3個(gè)點(diǎn)。 有 2 個(gè)邊分別連接n、x與x、y；另一種是兩個(gè)或兩個(gè)以上灰色點(diǎn)會(huì)通向同一個(gè)白色未探索點(diǎn)，如圖3（b）中的r、n、x這 3個(gè)點(diǎn)。這3個(gè)點(diǎn)沒(méi)有直接連接，但是下一步它們會(huì)同時(shí)向y點(diǎn)去探索。

可以看出由于組成封閉區(qū)域頂點(diǎn)的個(gè)數(shù)可能是偶數(shù)，也可能是奇數(shù)，才會(huì)導(dǎo)致這兩種情況。由于算法每次只是從一個(gè)灰色點(diǎn)開(kāi)始依次向外探索擴(kuò)展，所以無(wú)論哪種情況，當(dāng)相遇發(fā)生時(shí)，總是會(huì)有個(gè)灰色點(diǎn)a發(fā)現(xiàn)它要探索的下一個(gè)點(diǎn)b已經(jīng)被另一個(gè)灰色點(diǎn)所占據(jù)。這時(shí)只用在點(diǎn)b對(duì)應(yīng)的相遇鏈表數(shù)據(jù)結(jié)構(gòu)M中增加點(diǎn)a這一項(xiàng)，表示從點(diǎn)a過(guò)來(lái)的搜索分支也到達(dá)了b處。這個(gè)鏈表M存放在本文1.2所述的鄰接表擴(kuò)展結(jié)構(gòu)中。

例如對(duì)于圖3（a）所述的相遇第一種情況，搜索記錄過(guò)程如下：

假設(shè)在n、x、y這3個(gè)灰色點(diǎn)中從n最先開(kāi)始向外探索。n發(fā)現(xiàn)它的臨界點(diǎn)x已經(jīng)成了灰色，那么在x對(duì)應(yīng)的相遇鏈表結(jié)構(gòu)M[x]中增加一條對(duì)于n記錄，用于構(gòu)建封閉區(qū)域Ⅰ。n探索完畢，自己由灰色變成了黑色，如圖4（a）。接著節(jié)點(diǎn)x開(kāi)始向外探索，它對(duì)于已經(jīng)變黑的n節(jié)點(diǎn)不作理會(huì)，而發(fā)現(xiàn)了灰色的y節(jié)點(diǎn)。因此在y的鏈表M[y]中增加一條記錄x用于構(gòu)建封閉區(qū)域Ⅱ。x探索完畢變成黑色，如圖4（b）。圖中的虛線代表了相遇情況。至此兩個(gè)封閉區(qū)域都Ⅰ、Ⅱ被探索出來(lái)，分別在 M[x]和 M[y]中有所記錄，如圖 4（c）。

圖4 對(duì)于圖3（a）的搜索記錄過(guò)程Fig.4 Search and record process for fig.3 （a）

對(duì)于圖3（b）的第2種情況，搜索過(guò)程如下：

圖5 對(duì)于圖3（b）的搜索記錄過(guò)程Fig.5 Search and record process for fig.3 （b）

假設(shè)在r、n、x這3個(gè)點(diǎn)中從n最先向外搜索。n發(fā)現(xiàn)了白色節(jié)點(diǎn)y。作為廣度搜索的正常步驟，y節(jié)點(diǎn)變成灰色以表示被搜索發(fā)現(xiàn)。n搜索完成，如圖5（a）。接著r、x在各自的搜索過(guò)程中都發(fā)現(xiàn)了灰色點(diǎn)y，如圖5（b）。它們分別在y的鏈表 M[y]中添加了 r、x這兩條記錄，如圖 5（c）。 這兩條記錄分別對(duì)應(yīng)著左、右兩個(gè)四邊形區(qū)域Ⅰ、Ⅱ。

通過(guò)對(duì)這兩種情況的分析，可以發(fā)現(xiàn)在記錄兩個(gè)灰色點(diǎn)相遇的過(guò)程中，一個(gè)灰色點(diǎn)在完成搜索記錄后就變成了黑色。這樣另一個(gè)點(diǎn)就不會(huì)對(duì)同一個(gè)封閉區(qū)域進(jìn)行重復(fù)記錄。同時(shí)，由于對(duì)相遇點(diǎn)的記錄M采用鏈表結(jié)構(gòu)，能夠記錄同一點(diǎn)上的多次相遇，這樣就能反映出多個(gè)封閉區(qū)域共用一個(gè)頂點(diǎn)的情況。

2.2 需要記錄的額外信息

為了在讀取記錄時(shí)能夠知道是在上述哪種情況下 “相遇”，需要在廣度搜索時(shí)記錄下每個(gè)頂點(diǎn)到源點(diǎn)的距離值D。在圖3～5中，節(jié)點(diǎn)中的數(shù)字代表這個(gè)距離值D。源節(jié)點(diǎn)s的D值為0。當(dāng)節(jié)點(diǎn)a探索到一個(gè)新節(jié)點(diǎn)b，b的D值會(huì)在a的D值上加1。 如圖 5（b）中從n搜索到y(tǒng)，則D[y]=D[n]+1=3。

如果只知道在哪一點(diǎn)相遇，還不足以形成由頂點(diǎn)序列（p0，p1，…pn）來(lái)表示的完整的封閉區(qū)域信息。因此假設(shè)從頂點(diǎn)u開(kāi)始向外搜索時(shí)，每發(fā)現(xiàn)一個(gè)白色頂點(diǎn)v，就需要將u作為v的父節(jié)點(diǎn)存在v的鄰接表結(jié)構(gòu)P中。在圖3～5中，實(shí)心箭頭表明了節(jié)點(diǎn)之間的“父子”關(guān)系。例如5（b）中，m為n的父節(jié)點(diǎn)，故P[n]=m；n為y的父節(jié)點(diǎn)，故P[y]=n。因?yàn)橐粋€(gè)節(jié)點(diǎn)最多只能被發(fā)現(xiàn)一次，所以任何節(jié)點(diǎn)最多只有一個(gè)父節(jié)點(diǎn)。通過(guò)這種記錄，在搜索完成后，對(duì)任意一個(gè)節(jié)點(diǎn)，都能重現(xiàn)一條返回源節(jié)點(diǎn)的路徑。如對(duì)于圖5（b）中的y，就有y→n→m→s。

上述兩個(gè)額外信息：距離與父節(jié)點(diǎn)，都儲(chǔ)存在鄰接表擴(kuò)展結(jié)構(gòu)中，如圖 4（c）、圖 5（c）。 它們都用于搜索完成后重構(gòu)封閉區(qū)域信息。

2.3 輸出封閉區(qū)域信息

當(dāng)搜索完成后，選出一個(gè)含有相遇鏈表信息M的節(jié)點(diǎn)u。u自身有一條不斷通過(guò)u的父節(jié)點(diǎn)直到源節(jié)點(diǎn)構(gòu)成的主路徑{u→P[u]→P[P[u]]→…→s}。而M[u]指向的每一個(gè)節(jié)點(diǎn)也都各自有一條主路徑。u的主路徑和任意一條M[u]指向節(jié)點(diǎn)的主路徑都圍成了一個(gè)封閉區(qū)域，因此這兩條路徑會(huì)有一個(gè)相同的起始點(diǎn)。找到這個(gè)起始點(diǎn)，即可知道圍成的封閉區(qū)域的所有頂點(diǎn)信息。

找到這個(gè)起始點(diǎn)的方法為，首先判斷構(gòu)成封閉區(qū)域的頂點(diǎn)數(shù)為奇數(shù)還是偶數(shù)。例如對(duì)于圖4（b），點(diǎn)y的M表中含有x點(diǎn)，比較距離值D[x]與D[y]，它們相等表明區(qū)域Ⅱ由奇數(shù)個(gè)點(diǎn)組成。因此直接從y和x的主路徑y(tǒng)→m→s與x→m→s同時(shí)往回尋找，直到找到了相同的起始點(diǎn)m，即可出構(gòu)建區(qū)域Ⅱ（x，y，m）。實(shí)現(xiàn)方法為比較 P[y]、P[x]，再比較 P[P[y]]、P[P[y]]，…直到它們相同為止。對(duì)于圖5（b）中的y與M[y]中的x，比較D[x]與D[y]不相同，表明區(qū)域Ⅱ由偶數(shù)個(gè)點(diǎn)組成。這時(shí)沿y的主路徑y(tǒng)→n→m→s先返回一級(jí)到n→m→s，再與x的主路徑x→m→s一起同時(shí)往回尋找，就能找到相同的起始點(diǎn) m 并構(gòu)建出封閉區(qū)域Ⅱ（x，y，n，m）。

2.4 算法過(guò)程綜述

步驟：

1）計(jì)算所有線段和圓弧的交點(diǎn)，用交點(diǎn)和線段信息建立鄰接表結(jié)構(gòu)。

2）初始化每個(gè)節(jié)點(diǎn) u。顏色值 COLOR[u]=白；距離值D[u]=無(wú)窮大；父節(jié)點(diǎn)P[u]=空；相遇點(diǎn)鏈表M[u]=空。

3）任意選取一點(diǎn)作為源節(jié)點(diǎn) s。初始化 s：COLOR[s]=灰，D[s]=0，P[s]=空，M[s]=空。

4）將s加入先進(jìn)先出隊(duì)列Q。

5）只要Q中還有元素，取出Q隊(duì)列的首元素u。

6）通過(guò)鄰接表找到u的一個(gè)相鄰的點(diǎn)v。

7）如果 v 為白色，設(shè)置 v 的值：COLOR[v]=灰，D[v]=D[u]+1，P[v]=u。然后將v作為新的一輪探索起點(diǎn)加入隊(duì)列Q的尾部。

8）如果v為灰色，將節(jié)點(diǎn)u添加到v的相遇點(diǎn)鏈表M[u]中。9）如果v為黑色，跳過(guò)這一情形。

10）返回第6步，對(duì)u其余相鄰的點(diǎn)作第 7）～9）這 3步的判斷。

11）至此u的全部相鄰點(diǎn)都已搜索完。將u的顏色COLOR[u]設(shè)為黑。返回第5步，對(duì)隊(duì)列Q中剩余的點(diǎn)進(jìn)行搜索。

12）至此源節(jié)點(diǎn)s所能達(dá)到的節(jié)點(diǎn)都已搜索過(guò)。如果還有點(diǎn)沒(méi)有被探索，那么它是從s無(wú)法到達(dá)的點(diǎn)。選擇這個(gè)未探索點(diǎn)作為新的源節(jié)點(diǎn)s，回到第3步進(jìn)行新的遍歷。

現(xiàn)在整個(gè)圖都遍歷過(guò)，所有節(jié)點(diǎn)都已為黑色，所有的封閉區(qū)域也已找到。以下步驟為輸出這些封閉區(qū)域。

13）從所有節(jié)點(diǎn)中依次取出一個(gè)點(diǎn)u。

14）如果u的相遇點(diǎn)鏈表M[u]為空，那么返回13繼續(xù)判斷下一個(gè)點(diǎn)。

15）如果u的相遇點(diǎn)鏈表 M[u]不為空，那么從 M[u]中取出一個(gè)點(diǎn)v。新建一個(gè)含有節(jié)點(diǎn)信息的初始為空的雙向鏈表L，用來(lái)存放構(gòu)成封閉區(qū)域的點(diǎn)集信息。

16）如果D[v]等于D[u]，則將u與v按次序加入雙向鏈表L中。調(diào)用執(zhí)行第20步。

17）如果 D[v]比 D[u]小 1，則將 u的父節(jié)點(diǎn) P[u]、u與 v這3個(gè)點(diǎn)按次序加入雙向鏈表L中。 取u=P[u]，調(diào)用執(zhí)行第20步。

18）至此雙向鏈表L中已含有封閉區(qū)域邊界上按順序排列的點(diǎn)。返回執(zhí)行第13步構(gòu)建剩余封閉區(qū)域。

19）算法結(jié)束。每一個(gè)雙向鏈表L含有一個(gè)封閉區(qū)域信息。

第 20）步以后為第 16）、17）步所調(diào)用執(zhí)行。

20）如果父節(jié)點(diǎn)P[u]與P[v]為同一個(gè)點(diǎn)，那么把這個(gè)點(diǎn)P[u]加入 L 隊(duì)首，返回調(diào)用處（16）或 17）步）。

21）取 u=P[u]，v=P[v]，再將 u 加入 L 隊(duì)首，v加入 L 隊(duì)末。返回執(zhí)行第20步。

3 結(jié)果演示

圖6（a）為讀取含有線段圓弧信息的DXF文件后繪制的版圖。對(duì)其應(yīng)用本文的封閉區(qū)域分離算法后，再對(duì)封閉區(qū)域著色，結(jié)果如圖6（b）。可以看到在本例中算法效果為去掉了布線部分，凸顯出了板塊布局。

圖6 封閉區(qū)域分離結(jié)果演示Fig.6 Presentation of the enclosed area separation result

4 結(jié) 論

本文介紹了一種封閉區(qū)域的發(fā)現(xiàn)算法。算法適應(yīng)性強(qiáng)，只用給出二維平面中所有線段圓弧等基本元素的信息，就能夠找出所有它們圍成的任意形狀的封閉區(qū)域。算法采用被廣泛應(yīng)用和證明了正確性的廣度優(yōu)先算法作為基礎(chǔ)，這樣最大化提高了算法的準(zhǔn)確度和效率。應(yīng)用在圖形處理仿真軟件中，為原本無(wú)法實(shí)現(xiàn)的任意封閉區(qū)域的選中，著色，切割合并等操作提供了快速可靠的解決方案。

[1]武運(yùn)興.二維圖形內(nèi)側(cè)邊界自動(dòng)識(shí)別的研究[J].華北水利水電學(xué)院學(xué)報(bào)，1997，18（1）：39-44.

WU Yun-xing.Research on automatic identification of 2D graphics medial border[J].Journal of North China Institute of Water Conservancy and Hydroelectric Power，1997，18 （1）：39-44.

[2]杜月云，周子平，張?jiān)讫?一種任意多邊形裁剪快速算法[J].計(jì)算機(jī)應(yīng)用與軟件，2009，26（6）：265-267.

DU Yue-yun，ZHOU Zi-ping，ZHANG Yun-long.A quick algorithm for discretionary polygon clipping[J].Computer Applications and Software，2009，26（6）：265-267.

[3]蔡志杰.一般多邊形的切割[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)，1998，10（3）：248-252.

CAI Zhi-jie.General polygon cutting[J].CAD&CG，1998，10（3）：248-252.

[4]陳瑞卿，周健，虞烈.一種判斷點(diǎn)與多邊形關(guān)系的快速算法[J].西安交通大學(xué)學(xué)報(bào)，2007，41（1）：59-63.

CHEN Rui-qing，ZHOU Jian，YU Lie.Fastmethod to determine spatial relationship between point and polygon[J].Journal of Xi’an Jiaotong University，2007，41（1）：59-63.

[5]Franco P P，Michael I S.Computational geometry：an introduction[M].New York：Library of congress， 1985.

[6]王舒鵬，方莉.混合積判斷線段相交的方法分析[J].電腦開(kāi)發(fā)與應(yīng)用，2006，19（10）：34-35.

WANG Shu-peng，F(xiàn)ANG Li.An analysis of two segments intersection judgment with mixed product[J].Computer Development&Applications，2006，19（10）：34-35.

[7]Thomas H C，Charles E L，Ronald L R.Introduction to algorithms[M].US：The MIT Press，1990.