二維圖形封閉區域自動識別算法

艾迪，周云燕，萬里兮

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

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

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

1 基本理論

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

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

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

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

1.1 求交點

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

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

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

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

圖1 無向圖和對應的擴展鄰接表結構Fig.1 An undirected graph and its extended adjacency-list representation

1.2 擴展的鄰接表表示法

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

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

1.3 基于廣度優先算法的封閉區域發現算法

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

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

圖2 廣度優先搜索算法Fig.2 Breadth-first-search procedure

這樣如此反復，最終所有可到達的白色點都被發現。因此這種廣度搜索算法的由內向外遍歷所有點的性質滿足了本文算法需要搜索出圖中所有封閉區域的基本要求。

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

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

2 封閉區域分離算法

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

2.1 記錄相遇點

在對圖進行廣度優先搜索時，灰色點相遇會存在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點去探索。

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

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

假設在n、x、y這3個灰色點中從n最先開始向外探索。n發現它的臨界點x已經成了灰色，那么在x對應的相遇鏈表結構M[x]中增加一條對于n記錄，用于構建封閉區域Ⅰ。n探索完畢，自己由灰色變成了黑色，如圖4（a）。接著節點x開始向外探索，它對于已經變黑的n節點不作理會，而發現了灰色的y節點。因此在y的鏈表M[y]中增加一條記錄x用于構建封閉區域Ⅱ。x探索完畢變成黑色，如圖4（b）。圖中的虛線代表了相遇情況。至此兩個封閉區域都Ⅰ、Ⅱ被探索出來，分別在 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）

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

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

2.2 需要記錄的額外信息

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

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

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

2.3 輸出封閉區域信息

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

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

2.4 算法過程綜述

步驟：

1）計算所有線段和圓弧的交點，用交點和線段信息建立鄰接表結構。

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

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

4）將s加入先進先出隊列Q。

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

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

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

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

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

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

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

現在整個圖都遍歷過，所有節點都已為黑色，所有的封閉區域也已找到。以下步驟為輸出這些封閉區域。

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

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

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

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

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

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

19）算法結束。每一個雙向鏈表L含有一個封閉區域信息。

第 20）步以后為第 16）、17）步所調用執行。

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

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

3 結果演示

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

圖6 封閉區域分離結果演示Fig.6 Presentation of the enclosed area separation result

4 結 論

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

[1]武運興.二維圖形內側邊界自動識別的研究[J].華北水利水電學院學報，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].計算機應用與軟件，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].計算機輔助設計與圖形學學，1998，10（3）：248-252.

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

[4]陳瑞卿，周健，虞烈.一種判斷點與多邊形關系的快速算法[J].西安交通大學學報，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].電腦開發與應用，2006，19（10）：34-35.

WANG Shu-peng，FANG 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.