基于交點有序化的簡單多邊形布爾運算

魏勝利，李 源

(安陽工學(xué)院 計算機(jī)科學(xué)與信息工程學(xué)院，河南 安陽 455000)

0 引 言

多邊形布爾運算，即多邊形間的交、并和差，是計算機(jī)圖形學(xué)、計算幾何中一個最基本的算法，廣泛應(yīng)用于幾何實體造型、地理信息系統(tǒng)(GIS)等領(lǐng)域。國內(nèi)外許多專家對多邊形布爾運算算法進(jìn)行了大量研究，并提出了相應(yīng)的算法。Andereev[1]、Foley[2]、Maillot[3]等提出的算法僅適用于凸多邊形。Weiler等[4]提出的算法使用樹形數(shù)據(jù)結(jié)構(gòu)，Vatti[5]、Greiner_Hormann[6]提出的算法使用雙性鏈表數(shù)據(jù)結(jié)構(gòu)，劉勇奎[7]提出的算法使用單鏈表結(jié)構(gòu)。朱雅音等[8]提出了基于邊的奇偶性質(zhì)的任意簡單多邊形的布爾運算，很好地處理了各種奇異情況。閆浩文等[9]提出一種復(fù)合多邊形求差的矢量算法。崔璨等[10]提出一種基于梯形剖分的多邊形布爾運算方法。Rivero等[11]提出一種全新的適用于任意多邊形的布爾運算，該算法用簡單鏈表示兩個多邊形，得到一個同樣用簡單鏈表示的結(jié)果多邊形；董未名等[12]將Rivero算法擴(kuò)展到可以應(yīng)用于帶圓錐曲線邊的平面簡單多邊形。朱二喜等[13]從圖形內(nèi)角概念開始，對多邊形布爾運算重新全局化建模，實現(xiàn)其算法。趙軍等[14-15]利用最小回路提出分別求簡單和帶洞多邊形的布爾運算的方法。

文中在對Greiner_Hormann和劉永奎提出的算法深入分析的基礎(chǔ)上，提出了一種基于交點有序化的簡單多邊形布爾運算算法。以單鏈表數(shù)據(jù)結(jié)構(gòu)為多邊形的存儲結(jié)構(gòu)，采用基于掃描線的線段求交算法求多邊形的交點，借助鄰接表實現(xiàn)對無序交點的有序化處理，通過一次性遍歷鄰接表把交點依次插入到多邊形鏈表中，然后再分別追蹤出多邊形交、并、差的結(jié)果。最后將該算法與Greiner_Hormann和劉永奎算法進(jìn)行了比較，結(jié)果表明該算法在執(zhí)行效率方面優(yōu)于上述兩種算法。

1 基本概念與定義

為了便于算法的描述，先介紹一些有關(guān)多邊形布爾運算的基本概念和術(shù)語。

(1)主多邊形和裁剪多邊形。

多邊形的布爾運算包括交、并、差，多邊形的布爾運算與多邊形的裁剪運算沒有本質(zhì)的區(qū)別，都需要先對數(shù)據(jù)進(jìn)行處理，才能追蹤結(jié)果。裁剪運算只是得到多邊形的交，布爾運算還需要后續(xù)輸出并和差的結(jié)果。因此，為了便于問題的描述，借鑒裁剪運算的概念，把其中一個多邊形稱為主多邊形，用S表示；另一個多邊形稱為裁剪多邊形，用C表示。

(2)多邊形布爾運算的表示。

對于多邊形S和C，定義S與C的交表示為S∩C,S與C的并表示為S∪C，S與C的差表示為S-C，C與S的差表示為C-S。

(3)多邊形邊的方向與內(nèi)外區(qū)域的關(guān)系。

如果多邊形邊的方向是逆時針，則沿著多邊形邊界方向前進(jìn)，左側(cè)區(qū)域為多邊形的內(nèi)部；相反如果多邊形邊的方向是順時針，則沿著多邊形邊界方向前進(jìn)，右側(cè)區(qū)域為多邊形的內(nèi)部。如無特別說明，這里所述的多邊形都是按逆時針方向存儲的。

(4)進(jìn)點和出點的定義。

設(shè)I是多邊形S和C的一個交點，如果沿著S的邊界方向在I點從C的外部進(jìn)入C的內(nèi)部，則稱I為C的一個進(jìn)點。反之，如果S在I點從C的內(nèi)部到C的外部，則稱I為C的一個出點。

例如，對于圖1所示的多邊形S和C及其交點I，若S的邊為逆時針方向，則I3、I1為C的進(jìn)點，I2、I4為C的出點；若S的邊為順時針方向，則I3、I1為C的出點，I2、I4為C的進(jìn)點。

(5)基點。

所謂基點就是按照多邊形邊的方向交點所在邊的起點。例如，在圖1中，對于多邊形C來說，C1就是I4和I3的基點。

圖1 相交多邊形

2 算法的數(shù)據(jù)結(jié)構(gòu)

多邊形布爾運算算法需要一個合適的數(shù)據(jù)結(jié)構(gòu)來存儲多邊形及交點，并能夠在其上進(jìn)行正確追蹤布爾運算的操作。Weiler算法中把輸入的多邊形組成一個樹形結(jié)構(gòu)，Greiner_Hormann算法采用雙向鏈表的結(jié)構(gòu)，每個多邊形由一個雙向鏈表來表示，并依此把所求得的交點分別按多邊形頂點的有序序列插入到主多邊形和裁剪多邊形的兩個雙向鏈表中。劉勇奎對Greiner_Hormann算法進(jìn)行了改進(jìn)，采用循環(huán)單鏈表來存儲多邊形，同時僅為交點分配一個存儲空間，與Greiner_Hormann中的雙向鏈表結(jié)構(gòu)相比，因減少了一個指針域而節(jié)省了存儲空間，且僅為每個交點建立1個節(jié)點的存儲空間，并分別插入到兩個多邊形的單鏈表中。而Greiner_Hormann算法為每個交點建立兩個存儲空間，然后再分別將每個交點插入到對應(yīng)的多邊形鏈表中。劉勇奎算法設(shè)計了兩種不同的數(shù)據(jù)結(jié)構(gòu)分別存儲多邊形頂點信息和交點信息，但又把以這兩種不同結(jié)構(gòu)表示的多邊形頂點和交點插入到同一個鏈表中，這在采用帶有指針類型的高級語言編程時是無法實現(xiàn)的，因為這類編程語言要求鏈表中的節(jié)點必須具有相同類型的結(jié)構(gòu)?？梢园褎⒂驴惴ㄖ兴O(shè)計的兩種不同的數(shù)據(jù)結(jié)構(gòu)歸結(jié)為一類，即每個單鏈表節(jié)點中含有兩個指針，其中一個指針只有當(dāng)該節(jié)點為交點時才有意義。這樣既保留了劉勇奎算法中單鏈表的優(yōu)點，又便于編程實現(xiàn)。

在基于交點有序化的簡單多邊形布爾運算算法中，單鏈表節(jié)點數(shù)據(jù)結(jié)構(gòu)為：

點坐標(biāo)信息：

struct Point

{

double x,y //點坐標(biāo)

};

多邊形頂點及后續(xù)求的交點坐標(biāo)都存儲到一個點坐標(biāo)數(shù)組中，點的編號即為點在數(shù)組中的下標(biāo)。

單鏈表節(jié)點信息：

struct Vertex

{

bool Intersect; //布爾型

Vertex *next1,*next2; //節(jié)點指針

bool used;//布爾型

intindex; //點編號

};

其中Intersect用于標(biāo)識該節(jié)點是多邊形頂點還是交點，指針域用于指向下一個節(jié)點，如果該節(jié)點是多邊形頂點，則next1指向單鏈表的后繼，next2無意義；如果該節(jié)點為交點，則next1,next2分別指向主多邊形和裁剪多邊形單鏈表的后繼節(jié)點，實現(xiàn)同一個交點分別插入到兩個多邊形單鏈表中。used用來標(biāo)識在追蹤多邊形布爾運算過程中該節(jié)點是否使用過。 index為該頂點在點坐標(biāo)數(shù)組中的索引值。圖2為對圖1采用文中算法得到的的數(shù)據(jù)存儲結(jié)構(gòu)。

3 無序交點的有序化

多邊形求交是影響多邊形布爾運算效率的關(guān)鍵因素，Greiner_Hormann算法和劉勇奎算法都是通過測試兩個多邊形的全部線段對求交點，效率很低。文中采用Park[16]提出的多邊形鏈求交算法求多邊形的交點，其時間復(fù)雜度為O(n+k)logm，其中m為判斷是否存在交點的線段數(shù)，n為兩個多邊形的頂點個數(shù)，k為交點個數(shù)。但Park算法求得的多邊形鏈的交點是無序的。文中采用與鄰接表類似的存儲結(jié)構(gòu)分別暫時存儲主多邊形和裁剪多邊形的交點信息，以實現(xiàn)無序交點的有序化。在鄰接表中，為多邊形的每個頂點建立一個單鏈表，每個單鏈表中的節(jié)點存儲以該頂點為基點對應(yīng)的交點信息。每個單鏈表上附設(shè)一個表頭節(jié)點，在表頭節(jié)點中，除了設(shè)有指針域指向鏈表中第一個節(jié)點，還設(shè)有存儲基點編號的信息域。建立兩個數(shù)組，分別存儲主多邊形和裁剪多邊形的表頭節(jié)點。

存儲交點的單鏈表節(jié)點的結(jié)構(gòu)為：

struct IntersectPoint

{

double distancetobasepoint; //交點到基點的距離

IntersectPoint *next;//指針

int index; //點編號

} ;

表頭節(jié)點的結(jié)構(gòu)為：

struct BaseHead

{

int index ;//基點編號

IntersectPoint * firstpoint; //指向第一個交點

};

其中，firstpoint域指向該基點的第一個交點，next域指向該基點所對應(yīng)的下一個交點，distancetobasepoint為交點到基點的距離，每個基點對應(yīng)的交點按distancetobasepoint從小大到排序，這樣就實現(xiàn)了無序交點的有序化，且有序化后的交點順序與多邊形頂點的存儲順序一致。

設(shè)圖1中主多邊形的頂點從S1至S4的編號分別為1到5，裁剪多邊形的頂點從C1至C4的編號分別為6到9，則主多邊形S上的交點有序化后的存儲信息如圖3(a)所示，裁剪多邊形C上的交點有序化后的存儲信息如圖3(b)所示。

圖3 多邊形交點有序化

4 交點插入多邊形鏈表

完成無序交點的有序化后，下一步需要把交點按多邊形頂點的順序插入到多邊形鏈表中。把交點插入到多邊形鏈表時需要設(shè)置交點的進(jìn)出性，分析發(fā)現(xiàn)沿著S的邊界，對于C的進(jìn)點和出點是交替出現(xiàn)的，所以只需判斷第一個交點是進(jìn)點還是出點，其他交點的進(jìn)出性則可依次確定。確定第一個交點的進(jìn)出性的方法是，在S的交點信息表中，找到第一個交點I,并判斷I的基點Si與多邊形C的位置關(guān)系，如果Si在C的外部，則I為C的進(jìn)點，反之I為C的出點。

把交點插入到S多邊形鏈表中，先遍歷S的每個交點，并在S的多邊形鏈表中找到該交點的基點在多邊形鏈表中的位置即可把交點按照多邊形鏈表節(jié)點結(jié)構(gòu)的形式插入到S的多邊形鏈表中。由于與S對應(yīng)的有序化后的交點順序與S的頂點順序是一致的，因此在查找下一個交點的基點時可在多邊形鏈表中當(dāng)前交點的后繼節(jié)點中查找，而不需重新遍歷鏈表。在插入交點的過程中，可依據(jù)第一個交點的進(jìn)出性交替設(shè)置其他交點的進(jìn)出性。

按照文中采用的多邊形存儲結(jié)構(gòu)，主多邊形鏈表和裁剪多邊形鏈表共享同一個交點存儲單元。由于在把交點插入到S多邊形鏈表時已經(jīng)為交點分配了存儲空間，所以在插入C的交點到C的多邊形鏈表時只需修改指針的指向關(guān)系即可。但是S多邊形鏈表中有序交點對于C多邊形又是無序的。為了在常數(shù)時間內(nèi)查找到每個交點的存儲地址，可用哈希表存儲每個交點的存儲地址。在該哈希表中以交點的編號為關(guān)鍵字，交點的個數(shù)為哈希表的長度，哈希函數(shù)采用除留余數(shù)法，即：

H(key)=(xindex-indexmin) MODp

其中，xindex為交點編號；indexmin為交點編號的最小值；p為哈希表長度。每個交點經(jīng)過哈希函數(shù)處理后都有一個唯一的值，所以不需要設(shè)計處理沖突的方法。

采用與S的交點插入的S的多邊形鏈表中類似的方式，找到C多邊形每個交點的基點在C多邊形鏈表中的位置，并按所設(shè)計的哈希函數(shù)在常數(shù)時間內(nèi)定位到交點的存儲地址，修改指針的指向關(guān)系，即可將交點插入到C多邊形鏈表中。這樣把全部交點插入到多邊形鏈表的時間復(fù)雜度為O(n+2k)。

5 追蹤多邊形布爾運算

把交點按照多邊形頂點的存儲順序分別插入到多邊形鏈表后即可追蹤多邊形布爾運算的結(jié)果。

(1)追蹤多邊形并。

追蹤多邊形并的步驟為：在主多邊形S中查找第一個其后繼為裁剪多形進(jìn)點的節(jié)點ps,沿S的多邊形鏈表，從ps開始逆時針遍歷，當(dāng)遇到交點時，則轉(zhuǎn)到裁剪多邊形C上繼續(xù)逆時針遍歷，遇到交點時，再次轉(zhuǎn)到多邊形S上繼續(xù)逆時針遍歷，重復(fù)以上步驟直至起點ps，追蹤多邊形并結(jié)束。從ps開始到ps結(jié)束按上述過程遍歷到點集就構(gòu)成多邊形的并。

(2)追蹤多邊形交。

追蹤多邊形交的步驟為：在主多邊形S中查找第一個為裁剪多邊形進(jìn)點的交點ps，將其標(biāo)記為已訪問,然后轉(zhuǎn)到裁剪多邊形C上逆時針遍歷，遇到交點時，再次轉(zhuǎn)到多邊形S上繼續(xù)逆時針遍歷，重復(fù)以上步驟直至起點ps追蹤出多邊形交的一部分。在上述過程中，每遍歷到一個節(jié)點都標(biāo)記該點為已訪問。在主多邊形S中查找下一個為裁剪多邊形進(jìn)點且尚未訪問的交點，重復(fù)以上過程，直至所有交點都被訪問，最后各個部分組合在一起即為多邊形的并。

(3)追蹤多邊形差。

求多邊形差與多邊形的并和交略有不同，如果求S-C則要求裁剪多邊形C頂點按順時針存儲。追蹤多邊形S-C的步驟為：在主多邊形S中查找第一個其后繼為裁剪多邊形進(jìn)點的節(jié)點ps，將其標(biāo)記為已訪問,沿S的多邊形鏈表，從ps開始逆時針遍歷，當(dāng)遇到交點時，則轉(zhuǎn)到裁剪多邊形C上繼續(xù)順時針遍歷，遇到交點時，再次轉(zhuǎn)到多邊形S上繼續(xù)逆時針遍歷，重復(fù)以上步驟直至起點ps，追蹤出多邊形S-C差的一部分。在上述過程中，每遍歷到一個節(jié)點都標(biāo)記該點已訪問。在主多邊形S中查找下一個其后繼為裁剪多邊形進(jìn)點且尚未被訪問的節(jié)點，重復(fù)以上過程，直至所有交點都被訪問，最后各個部分組合在一起即為多邊形S-C。追蹤多邊形C-S則只需把上述主多邊形和裁剪多邊形角色互換即可。

6 實驗結(jié)果

對文中提出的求多邊形布爾運算的算法在VC++環(huán)境下進(jìn)行編程實現(xiàn)，結(jié)果如圖4所示。

(a)S和C (b)S∪C (c)S∩C (d)S-C (e)C-S

圖4 多邊形布爾運算結(jié)果

表1為相同的數(shù)據(jù)組在相同的硬軟件環(huán)境下文中算法分別與Greiner_Hormann算法和劉勇奎算法進(jìn)行對比的結(jié)果。

表1 不同算法實驗所需的時間比較 s

從表1中可知，文中算法在求多邊形布爾運算(交、并、差)時優(yōu)于Greiner_Hormann 算法和劉勇奎算法。文中算法在求多邊形布爾運算過程中，時間復(fù)雜度為O(n+k)logm的Park算法求多邊形的交點，對于所求得的無序交點，在插入交點到多邊形鏈表前先以鄰接矩陣的形式存儲多邊形交點，并把相同基點的交點按交點到基點的距離從小到大排序，實現(xiàn)無序交點的有序化。然后再依次把交點插入到多邊形鏈表中，把交點插入到多邊形鏈表中的時間復(fù)雜度為O(n+2k)。實驗結(jié)果表明，該算法顯著提高了多邊形布爾運算的執(zhí)行效率。

7 結(jié)束語

對于簡單多邊形的布爾運算，在分析已有研究的基礎(chǔ)上，提出了一種基于交點有序化的簡單多邊形布爾運算算法。借助鄰接矩陣存儲多邊形交點，并把相同基點的交點按交點到基點的距離從小到大排序以實現(xiàn)無序交點的有序化，并根據(jù)頂點的進(jìn)出性追蹤多邊形的布爾運算結(jié)果。最后該算法進(jìn)行編程實現(xiàn)，并和Greiner_Hormann算法和劉勇奎算法進(jìn)行了對比，結(jié)果證明了該算法的高效性和可行性。