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

趙 軍，郝永興

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

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

1 相關概念

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

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

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

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

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

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

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

2 多邊形的初始化

2.1 多邊形的多環(huán)轉(zhuǎn)換為單環(huán)

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

圖1 含孔洞多邊形的轉(zhuǎn)換

具體轉(zhuǎn)換步驟為：

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

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

圖2 含多孔洞多邊形的轉(zhuǎn)換

2.2 兩個轉(zhuǎn)換后的單環(huán)相交

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

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

圖3 與“橋邊”相交的關聯(lián)邊情況

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

3 兩個多邊形交、并、差

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

3.1 最小回路的搜索與種類

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

若多邊形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-四類最小回路后會發(fā)現(xiàn)，所有P+類回路的集合構成了P的內(nèi)域，Q+類回路的集合構成了Q的內(nèi)域。由于多邊形均初始化為逆時針方向，且在交點處均按順時針最小轉(zhuǎn)角搜索，因此最小回路所包圍的區(qū)域均為至少其中一個多邊形的內(nèi)域。亦即P-類回路所圍成的區(qū)域為Q的內(nèi)域、P的外域。Q-類回路所圍成的區(qū)域為P的內(nèi)域、Q的外域。P∪Q的幾何意義為P和Q內(nèi)域的和，可用(P+)∪(Q+)表示，P-Q的幾何意義為P的內(nèi)域、Q的外域，其余類似。確定兩個多邊形的交、并、差集的規(guī)則如表1所示。

表1 確定P與Q的交、并、差的規(guī)則

4 奇異情況處理

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

5 算法分析與算例

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

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

6 結 論

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

圖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版.北京: 機械工業(yè)出版社, 2009: 65-79.

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

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

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

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

[8]朱二喜.基于圖形內(nèi)角的兩個任意多邊形的交并差算法[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.