一種求含孔洞多邊形交、并、差集的新方法

趙 軍，郝永興

(蘭州交通大學機電工程學院，甘肅 蘭州 730070)

多邊形的交、并、差集運算是計算幾何、計算機圖形學的一個基本問題。對這一問題的研究在多個領域具有重要的理論與實踐意義，諸如GIS系統中進行疊加分析、幾何造型中隱藏線的消除、線路板中電子元件的布局和線性規劃等。目前，針對這一問題國內外也進行了不少研究，提出過一些算法[1-10]，其中有些不能處理含孔洞多邊形。周培德[5]提出了一種較為可行的針對含孔洞多邊形的算法，其算法復雜度為O(n2logn)。朱雅音等[6]通過掃描線法并利用多邊形的拓撲信息確定任意多邊形的交、并、差集，其算法復雜度為O((n+m+k)log(n+m+k))，其中m，n是多邊形頂點數，k是兩多邊形的交點數。劉紅軍等[7]以兩多邊形差集為基礎解決了布爾運算問題，可以解決多邊形含孔洞問題，但算法中多邊形求交后每段線段的中點需要進行點包含運算，使其算法復超過O(n2)。朱二喜[8]提出圖形內角的概念，并利用它確定兩個任意多邊形的交并差，算法復雜度為O(k(n+m))+O(n+m+k)。崔璨和王結臣[9]基于梯形剖分求解多邊形布爾運算，所提算法可以處理含孔洞多邊形，時間復雜度為O(nlogm)，m為位于同一掃描條帶上小線段的平均數。本文在文獻[10]的基礎上進一步提出一種解決含孔洞多邊形布爾運算的方法，通過構造的一條雙向“橋邊”，使內環頂點序列并入外環頂點序列中，以消除內環，將多環頂點序列轉換為單環，以便利用不含孔洞多邊形布爾運算的交并差算法。針對兩個多邊形環包含嵌套的奇異情況，通過多邊形和點的包含性來確定嵌套關系。整個方法時間復雜度為O((n+m+k)logd)，其中d為多邊形分割的單調鏈數[11]。

1 相關概念

(1) 最小回路：其內部沒有與其共邊的其他回路。

(2) 頂點的關聯邊：如果邊e以頂點v為其一個端點，則稱邊e是頂點v的一條關聯邊。

(3) 頂點關聯邊序列：平面上s條具有公共頂點m的邊e1,e2, …,es，根據各邊與過m點水平向右方向逆時針夾角的大小進行的一個排列，記為CElist_m。

(4) 順時針最小轉角：平面圖中關聯于同一個節點m的s(s>2)條邊e1,e2,…es，將ei(1≤i≤s)以m點為中心繞平面法矢n順時針旋轉遇到第一條邊ek(1≤k≤s)，稱ek對ei具有順時針最小轉角。

(5) 多邊形內點在邊界的可見點：對簡單多邊形P和多邊形平面內的視點z，若P邊界上的點v與視點z的連線在P內部，則稱v點相對于視點z是可見的。

(6) 點包含性檢測：判斷一點z在簡單多邊形P的內部、外部或者邊界上。

為了便于描述，設P、Q為兩個輸入多邊形，用P∩Q、P∪Q、P-Q分別表示多邊形P與Q的交集、并集和差集。

2 多邊形的初始化

2.1 多邊形的多環轉換為單環

為了解決含空洞多邊形的布爾運算，利用簡單多邊形內一點的邊界可見點，通過增加一條雙向“橋邊”，將含孔洞多邊形多環轉換為單環，以此來解決含孔洞多邊形由于多環的存在而較為困難的布爾運算問題。如圖1(a)所示多邊形P，具有兩個環，外環P-out={1,2,3,4,5}，內環P-in={6,7,8,9}，通過構造雙向“橋邊”6v1，將P的內外環合并為一個環P={1,2,3,v1,6,7,8,9,6,v1,4,5}如圖1(b)。

圖1 含孔洞多邊形的轉換

具體轉換步驟為：

將多邊形外環初始化為逆時針方向，內環初始化為順時針方向，使得多邊形內部區域始終位于有向邊界的左側。選擇內環中的最右頂點，作為外環的一個內部點在外環邊界上搜尋可見點。搜索多邊形可見點的方法參見文獻[12]。將搜索到的可見點以及內環最右頂點作為二重頂點，并將其置于該內環頂點序列的首尾一并插入多邊形的外環序列中，消除一個內環。如此進行直至所有內環均被消除。

比如多邊形P：P-out={1,2,3,4,5}；P-in={6,7,8,9}、{10,11,12,13}，內外環方向如圖2(a)所示。頂點6為內環頂點中最右頂點，找出其在外環邊界上的一個可見點v1，如圖2(b)。將頂點序列段{v1,6,7,8,9,6,v1}插入外環序列，則P-out={1,2,3,v1,6,7,8,9,6,v1,4,5}，消除了一個內環。再找出剩余內環頂點中的最右頂點10，找出其在外環邊界上的一個可見點v2，將頂點序列段{v2,10,11,12,13,10,v2}插入外環序列，則P-out={1,2,3,v1,6,7,v2,10,11,12,13,10,v2,8,9,6,v1,4,5}，至此則消除了所有內環。

圖2 含多孔洞多邊形的轉換

2.2 兩個轉換后的單環相交

兩個轉換為單環的多邊形P={p1，p2，…，pn}與Q={q1，q2，…，qm}，求出各邊的交點，并對交點處各關聯邊進行排序。對P與Q各邊交點的計算，可采用Park和Shin[11]提出的基于多邊形單調鏈的方法。求出P與Q的所有交點后，分別在P與Q頂點序列中將非頂點交點插入到相應位置處。

在每個交點關聯的四條邊中，根據各邊在多邊形中的方向，有兩條邊指向交點，稱為與交點關聯的負向邊，有兩條邊背離交點，稱為與交點關聯的正向邊。“橋邊”是特殊的雙向邊，如果多邊形的邊與另一個多邊形的“橋邊”相交，則在交點處的關聯邊中“橋邊”是一條邊但具有兩個方向。也就是說與交點關聯的“橋邊”段既是正向邊又是負向邊。如圖3中，多邊形P和Q相交，P的邊pipi+1與Q的“橋邊”v1qs相交于m點，在m點的四條關聯邊中，mqs、mv1和mpi+1關于m為正向邊，pim、mv1和qsm為關于m的負向邊。m點處的關聯邊序列CElist_m={mv1,pim,mqs,mpi+1}。各個內環的最右頂點以及其外環邊界的可見點均亦視為交點。

圖3 與“橋邊”相交的關聯邊情況

為了便于搜索最小回路，對關聯于交點的四條邊按照與水平向右方向成逆時針夾角的大小進行排序，即確定交點處的關聯邊序列。

3 兩個多邊形交、并、差

將兩個含孔洞多邊形由多環轉換為單環，求出兩個環的交點，將交點關聯邊排序后，沿交點關聯正向邊按照最小轉角原則搜索最小回路，根據最小回路的不同種類進而確定兩個多邊形的交、并、差。

3.1 最小回路的搜索與種類

對經過轉換為單環的兩個多邊形，確定其邊的交點mi(i=1，2，…)，以及各交點處關聯邊序列CElist_mi，從各個交點處沿所有正向邊搜索最小回路，遇到交點遵循搜索前進邊與當前邊沿順時針方向轉角最小的原則。

若多邊形P和Q有邊相交(含“橋邊”)，則搜索到的所有最小回路中，每個回路均分別包含P和Q的邊，各邊在回路中或是逆時針走向或是順時針走向，但對于同一個多邊形P或Q的邊而言，其方向一致。因此最小回路中邊的方向存在以下三種情形：

情形1：回路中邊ei(ei∈P)的方向呈逆時針走向，而ej(ej∈Q)呈順時針方向；

情形2：回路中邊ei(ei∈P)的方向呈順時針方向，而ej(ej∈Q) 呈逆時針方向；

情形3：回路中所有邊均呈順時針方向。

將最小回路中包含邊ei∈P呈逆時針方向的歸為P+類，包含邊ei∈P呈順時針方向的歸為P-類。

3.2 確定多邊形的交、并、差

對兩個相交多邊形P和Q，歸類出其中的P+、P-、Q+、Q-四類最小回路后會發現，所有P+類回路的集合構成了P的內域，Q+類回路的集合構成了Q的內域。由于多邊形均初始化為逆時針方向，且在交點處均按順時針最小轉角搜索，因此最小回路所包圍的區域均為至少其中一個多邊形的內域。亦即P-類回路所圍成的區域為Q的內域、P的外域。Q-類回路所圍成的區域為P的內域、Q的外域。P∪Q的幾何意義為P和Q內域的和，可用(P+)∪(Q+)表示，P-Q的幾何意義為P的內域、Q的外域，其余類似。確定兩個多邊形的交、并、差集的規則如表1所示。

表1 確定P與Q的交、并、差的規則

4 奇異情況處理

存在兩個多邊形P和Q各邊沒有交點的奇異情況。若兩個多邊形為不含孔洞的簡單多邊形，則只有兩種情形：完全分離或者包含。如果多邊形P有孔洞，多邊形Q無孔洞，滿足P的外環P-out?Q，則P完全處于Q的內域；滿足Q?P-in，則P與Q完全分離；其余情況下，P和Q交、并、差集則需視P有多少內環、其中有哪些處于Q內域、哪些處于Q外域的情況而定。如果P和Q均有孔洞則情況更為復雜，其交、并、差集需要視包含所有內外環之間的嵌套關系而定。由于一個多邊形可能具有多個孔洞，因此需要對兩個多邊形的外環和各個內環之間檢測包含關系，以此來確定交并差集。兩個環的包含關系可通過取一個環上一頂點檢測是否位于另一個環內來確定。

5 算法分析與算例

在用時方面，第3小節算法中若多邊形P和Q的頂點個數分別為n和m，不妨設n≥m，k為P與Q的交點個數，環路轉換過程中，尋找內環最右點時間復雜度不超過O(nlogn)，根據文獻[6]尋找兩個單環的交并差集的時間復雜度為O((n+m+k)logd)，其中d為將多邊形分為不同的單調鏈的個數，d＜max{m，n}。在奇異情況下，點的包含性檢測時間復雜度為O(n)。綜上所述，整個算法時間復雜度為O((n+m+k)logd)，其中d為將多邊形分為不同的單調鏈的個數，d＜max{m，n}，與目前較優的文獻[8]算法復雜度(O(k(n+m)+O(n+m+k))相當，但避免了文獻[8]中大量復雜的反三角函數運算。

在Matlab環境中對兩個含孔洞多邊形的交、并、差集計算進行了大量測試，試驗結果表明算法對各類情況均能有正確的結果，證明了算法的魯棒性。圖4～7為其中四個算例。算例1為含孔洞多邊形與不含孔洞多邊形相交；算例2為兩個含孔洞多邊形相交；算例3為兩個含孔洞多邊形內、外環互相嵌套；算例4為兩個含孔洞多邊形其中一個完全位于另一個內域和外域的兩種情況。

6 結 論

本文給出了基于最小回路方法確定兩個含孔洞多邊形交、并、差集的方法，通過添加一個雙向“橋邊”，將多環頂點序列轉換為單環，進而利用最小回路法進行布爾運算。擴展了最小回路方法的適用域，將兩個任意多邊形交、并、差集的計算方法歸一為同一個算法，算法適應于重疊邊、交于頂點、以及互相包含無交點等奇異情況。算法充分利用了多邊形的幾何及拓撲信息，降低了算法時間復雜度。試驗與分析表明算法具有較高的效率和良好的適應性。

圖4 算例1

圖5 算例2

圖6 算例3

圖7 算例4

[1]Feito F R, Rivero M.Geometric modeling based on simplicial chains [J].Computers & Graphics, 1998, 22(5):611-619.

[2]Rivero M, Feito F R.Boolean operations on general planar polygons [J].Computer & Graphics, 2000, 24(6):881-896.

[3]何援軍.計算機圖形學[M].2版.北京: 機械工業出版社, 2009: 65-79.

[4]董未名, 瑪依拉·巴榜, 周登文, 孫家廣.平面擴展簡單多邊形的布爾運算[J].計算機輔助設計與圖形學學報, 2003, 15(9): 1134-1140, 1144.

[5]周培德.計算幾何——算法分析與設計[M].4版.北京:清華大學出版社, 2011: 238-241.

[6]朱雅音, 王化文, 萬 豐, 于雷易.確定兩個任意簡單多邊形交、并、差的算法[J].計算機研究與發展, 2003,40(4): 576-583.

[7]劉紅軍, 王從軍, 黃樹槐.帶有孔洞的多邊形的布爾運算[J].華中科技大學學報(自然科學版), 2003, 31(8):18-20.

[8]朱二喜.基于圖形內角的兩個任意多邊形的交并差算法[D].上海: 上海交通大學, 2009.

[9]崔 璨, 王結臣.一種基于梯形剖分的多邊形布爾運算方法[J].測繪學報, 2011, 40(1): 104-110.

[10]趙 軍, 劉榮珍.用最小回路求兩個簡單多邊形的交、并、差集[J].計算機應用, 2012, 32(11):3164-3167.

[11]Park S C, Shin H.Polygonal chain intersection [J].Computer& Graphics, 2002, 26(2): 341-350.

[12]劉榮珍, 趙 軍, 程耀東.求簡單多邊形可見點的一種新算法[J].工程圖學學報, 2009, 30(2): 109-113.