二維圖形封閉區(qū)域自動識別算法

艾迪，周云燕，萬里兮

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

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

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

1 基本理論

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

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

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

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

1.1 求交點

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

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

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

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

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

1.2 擴展的鄰接表表示法

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

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

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

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

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

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

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

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

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

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

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

2.1 記錄相遇點

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

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

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

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

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

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

圖4 對于圖3（a）的搜索記錄過程Fig.4 Search and record process for fig.3 （a）

對于圖3（b）的第2種情況，搜索過程如下：

圖5 對于圖3（b）的搜索記錄過程Fig.5 Search and record process for fig.3 （b）

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

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

2.2 需要記錄的額外信息

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

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

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

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

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

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

2.4 算法過程綜述

步驟：

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

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

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

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

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

6）通過鄰接表找到u的一個相鄰的點v。

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

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

10）返回第6步，對u其余相鄰的點作第 7）～9）這 3步的判斷。

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)果演示

圖6（a）為讀取含有線段圓弧信息的DXF文件后繪制的版圖。對其應(yīng)用本文的封閉區(qū)域分離算法后，再對封閉區(qū)域著色，結(jié)果如圖6（b）?？梢钥吹皆诒纠兴惴ㄐЧ麨槿サ袅瞬季€部分，凸顯出了板塊布局。

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

4 結(jié) 論

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

[1]武運興.二維圖形內(nèi)側(cè)邊界自動識別的研究[J].華北水利水電學(xué)院學(xué)報，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]杜月云，周子平，張云龍.一種任意多邊形裁剪快速算法[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].計算機輔助設(shè)計與圖形學(xué)學(xué)，1998，10（3）：248-252.

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

[4]陳瑞卿，周健，虞烈.一種判斷點與多邊形關(guān)系的快速算法[J].西安交通大學(xué)學(xué)報，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].電腦開發(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.