蔡琪

摘要：該文提出了一種基于二叉樹的幾何圖形拓撲處理算法，實現(xiàn)幾何圖形間的精確處理。并能有效解決大多數(shù)邊界問題，同時可以按需求設(shè)定不同的精度。

關(guān)鍵詞：二叉樹；拓撲運算；邊界問題

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）34-8191-03

隨著Web技術(shù)的發(fā)展，越來越多的應(yīng)用被從傳統(tǒng)的PC端移植到Web端，用戶只需要通過Web瀏覽器就可以得到所需要的服務(wù)。這些Web上的應(yīng)用不僅方便了用戶，也使得自身變得越來越普及。例如百度地圖每天的定位請求數(shù)就達20億以上，可見其用戶規(guī)模。而百度地圖這類應(yīng)用僅僅是WebGis中的一項小功能，而WebGis同樣在在城市規(guī)劃，交通規(guī)劃提供許多功能支持。

WebGis是Web上的地理信息系統(tǒng)，其功能主要是對空間上采集的地理信息進行分析與處理，例如通過人口統(tǒng)計所得的數(shù)據(jù)得到的城市人口密度分布圖，通過道路車輛統(tǒng)計所得的道路交通流量圖。這類信息通常需要通過對采集信息進行精確的拓撲計算得出，例如要計算一個下圖紅線劃定范圍內(nèi)的建筑面積，就需要拿紅色區(qū)域和A，B，C，D四塊區(qū)域進行邏輯判斷，同時計算相交區(qū)域面積。而當前一些開源的拓撲運算庫如Dotspatial等，存在著邊界問題處理不好，精度值無法確定，效率不高等一些問題。

1 關(guān)鍵技術(shù)

1） 多邊形的二叉樹分割

對平面任意閉合多邊形，若指定其包圍區(qū)域為內(nèi)側(cè)，則邊界與內(nèi)側(cè)相對的另外一側(cè)為外側(cè)，若要判斷內(nèi)外側(cè)，一般通過多邊形的方向進行判斷。通常多邊形的方向分為順時針與逆時針，沿多邊形方向，一般定義左側(cè)為內(nèi)側(cè)，右側(cè)為外側(cè)，所以若指定包圍的閉合區(qū)域為內(nèi)側(cè)，則多邊形為逆時針。如下圖，箭頭方向指定了逆時針的方向。

定義好了多邊形的方向后，我們可以對多邊形進行二叉樹分割，其算法大致思想是將多邊形的邊按照多邊形方向形成邊序列，取出序列中首個邊作為二叉樹的根節(jié)點，將其直線方向作為根節(jié)點的方向，再將剩余的邊與根節(jié)點方向進行拓撲判斷，根據(jù)剩余邊與根節(jié)點方向的拓撲關(guān)系，如左側(cè)相離，右側(cè)相離，相交，共線等，依次存入根節(jié)點的左子節(jié)點，右子節(jié)點，以及自身的同向列表中。這里采用遞歸的方式構(gòu)建樹，下面給出相應(yīng)偽碼：

2） 通過二叉樹找多邊形求交

構(gòu)建完多邊形的二叉樹后，我們可通過多邊形的二叉樹判斷一條邊是在多邊形內(nèi)部還是外部。這里以下圖中邊a，b，c為例。將邊a與首先樹的根節(jié)點進行判斷，根節(jié)點中存的是邊1，則a在邊1所在直線方向的右側(cè)，將邊a再與根節(jié)點的右子節(jié)點進行判斷，右子節(jié)點中存儲的為邊2，a在邊2所在直線的左側(cè)，將a與其左子樹進行判斷，重復(fù)該過程直到該節(jié)點沒有任何子樹了，可以看到該節(jié)點中存儲為邊7，由于a在邊7左側(cè)，之前已經(jīng)介紹過逆時針方向的多邊形，其內(nèi)部在其邊的方向的左側(cè)，至此可判斷a在多邊形內(nèi)。這里邊b與邊2相交，因此在判斷時需要將邊b截斷，邊2左側(cè)的繼續(xù)和邊2的左子樹進行判斷，邊2右側(cè)的繼續(xù)和邊2的右子樹進行判斷，這里左側(cè)邊與之前邊a的判斷順序一樣，最后判定位于多邊形內(nèi)部，而邊2右側(cè)的的與邊3進行判斷，其位于邊3右側(cè)，而邊3沒有右子樹，所以這里判定其為多邊形外部，邊c的判定與其相仿。

解決了邊與多邊位置的判斷，我們就可以開始進行多邊形的求交運算。兩個多邊形求交本質(zhì)上就是找到各個多邊形在另一個多邊內(nèi)部的邊。因此只需要對將一個多邊形的所有邊與另一個多邊形的二叉樹進行判斷，再將另一多邊形重復(fù)該操作，這樣便可找到所有的公共邊。

3） 其他拓撲運算

之前介紹了多邊形相交，這里定義多邊形P與Q相交為P∩Q。這里再定義多邊形取反，這里只需要將多邊形的所有邊進行取反，也就是將時針方向取反，這里定義多邊形P取反為?P。其余多邊形的拓撲運算均可用這兩種運算表示。

4） 拓撲運算結(jié)果的多邊形重構(gòu)

由于實際計算中出現(xiàn)的情況較多，這里就出現(xiàn)的多種典型的歧義性情況作出分析并給出相應(yīng)的算法。

對于以上出現(xiàn)的一個閉合區(qū)域的情況，只需將得到的邊按照邊的方向連接成環(huán)即可。而實際中往往會出現(xiàn)多個閉合區(qū)域的情況，如下圖。該文給出的方法的是先將得到的邊集合進行連通性分析，以結(jié)果中的頂點為節(jié)點形成無向圖，對各個連通區(qū)間進行單獨處理。

在之前的二叉樹計算時，我們將與邊重合的情況也列入多邊形內(nèi)部的情況，所以在得到的結(jié)果中會出現(xiàn)重合邊情況。對于邊重合的情況通常有兩種，分別為同向邊重合與異向邊重合。下圖給出了兩種不同的邊重合情況。兩種情況的處理方法不同。例如下圖a中，兩個多邊形的邊屬于同向邊重合，在計算時需要將兩條重合邊合并為一條，再加入到之前的連通圖中進行計算，而對于圖b中的情況，由于異向邊重合時，結(jié)果往往就是該邊所在的這條線段，所以出現(xiàn)異向邊重合時，我們將其所在線段作為結(jié)果，并將兩條異向重合邊從之前的中間結(jié)果中剔除。

頂點重合的情況通常分為無鄰邊重合與有鄰邊重合。通常無鄰邊重合出現(xiàn)在多邊形僅一點相交的情況，如圖a，其處理方式也較為簡單，將該頂點作為結(jié)果即可。對于有鄰邊的頂點相交，通常在排除邊重合之后需要做一些處理。如圖b中兩個圖形作并操作，則與頂點相鄰的有6條邊，這里需要確定每條邊通過頂點與哪條邊相連。

對于這種類型的點重合，確定邊成對的關(guān)系主要是通過邊的方向來確定。如下圖，這六條邊有3條是指向重合點，3條由頂點指向外部，我們可將這六條邊按此規(guī)律分為入邊與出邊。這里有三條入邊，指向重合點，另三條出邊由頂點出來，其中每條入邊對應(yīng)著一條出邊，不會出現(xiàn)其他情況。要找到入邊對應(yīng)的出邊，這里通過夾角的方式來判定其對應(yīng)關(guān)系，由于入邊左側(cè)對應(yīng)的是多邊形的內(nèi)部，則按其順時針方向找到的最小轉(zhuǎn)角的邊應(yīng)為其對應(yīng)的出邊，所以這里的處理方法是選擇一條入邊，計算其與所有出邊的順時針轉(zhuǎn)角，選擇最小轉(zhuǎn)角的出邊作為其對應(yīng)邊，然后依次對其余入邊進行處理。

經(jīng)過以上處理后，剩下的邊在方向上只有唯一的一條路徑，將剩余邊按照順序連接成閉合區(qū)域即可。

2 實驗結(jié)果

本文所介紹的基于二叉樹的拓撲運算算法，時間復(fù)雜度為nlogn，與當前使用較多的裁剪算法相比，其時間復(fù)雜度為n^2，效率得到明顯提升，同時本算法對于多種歧義情況均有處理，且在實際應(yīng)用中效果較好。但由于多邊形拓撲運算情況較多，實驗中可能會出現(xiàn)未考慮到的情況，將在之后的實驗中進行修正。

參考文獻：

[1] 潘瑜春，鐘耳順，趙春江.GIS空間數(shù)據(jù)庫的更新技術(shù)[J].地球信息科學(xué)，2004（1）.

[2] 杜爽，陳成永.以節(jié)點操作實現(xiàn)多邊形求交的算法[J].測繪通報，2007（10）.

[3] 宋立明，閆浩文，李茜茜，李雙元.兩個簡單多邊形求交的算法[J].測繪與空間地理信息，2011（6）.

[4] 樊建華，黃有群，劉嘉敏.帶孔洞的多邊形求交算法[J].沈陽工業(yè)大學(xué)學(xué)報，2001（5）.

[5] Philip J Schneider，David H Eberly .Geometric tools for computer graphics[C]. 2005.endprint

摘要：該文提出了一種基于二叉樹的幾何圖形拓撲處理算法，實現(xiàn)幾何圖形間的精確處理。并能有效解決大多數(shù)邊界問題，同時可以按需求設(shè)定不同的精度。

關(guān)鍵詞：二叉樹；拓撲運算；邊界問題

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）34-8191-03

隨著Web技術(shù)的發(fā)展，越來越多的應(yīng)用被從傳統(tǒng)的PC端移植到Web端，用戶只需要通過Web瀏覽器就可以得到所需要的服務(wù)。這些Web上的應(yīng)用不僅方便了用戶，也使得自身變得越來越普及。例如百度地圖每天的定位請求數(shù)就達20億以上，可見其用戶規(guī)模。而百度地圖這類應(yīng)用僅僅是WebGis中的一項小功能，而WebGis同樣在在城市規(guī)劃，交通規(guī)劃提供許多功能支持。

WebGis是Web上的地理信息系統(tǒng)，其功能主要是對空間上采集的地理信息進行分析與處理，例如通過人口統(tǒng)計所得的數(shù)據(jù)得到的城市人口密度分布圖，通過道路車輛統(tǒng)計所得的道路交通流量圖。這類信息通常需要通過對采集信息進行精確的拓撲計算得出，例如要計算一個下圖紅線劃定范圍內(nèi)的建筑面積，就需要拿紅色區(qū)域和A，B，C，D四塊區(qū)域進行邏輯判斷，同時計算相交區(qū)域面積。而當前一些開源的拓撲運算庫如Dotspatial等，存在著邊界問題處理不好，精度值無法確定，效率不高等一些問題。

1 關(guān)鍵技術(shù)

1） 多邊形的二叉樹分割

對平面任意閉合多邊形，若指定其包圍區(qū)域為內(nèi)側(cè)，則邊界與內(nèi)側(cè)相對的另外一側(cè)為外側(cè)，若要判斷內(nèi)外側(cè)，一般通過多邊形的方向進行判斷。通常多邊形的方向分為順時針與逆時針，沿多邊形方向，一般定義左側(cè)為內(nèi)側(cè)，右側(cè)為外側(cè)，所以若指定包圍的閉合區(qū)域為內(nèi)側(cè)，則多邊形為逆時針。如下圖，箭頭方向指定了逆時針的方向。

定義好了多邊形的方向后，我們可以對多邊形進行二叉樹分割，其算法大致思想是將多邊形的邊按照多邊形方向形成邊序列，取出序列中首個邊作為二叉樹的根節(jié)點，將其直線方向作為根節(jié)點的方向，再將剩余的邊與根節(jié)點方向進行拓撲判斷，根據(jù)剩余邊與根節(jié)點方向的拓撲關(guān)系，如左側(cè)相離，右側(cè)相離，相交，共線等，依次存入根節(jié)點的左子節(jié)點，右子節(jié)點，以及自身的同向列表中。這里采用遞歸的方式構(gòu)建樹，下面給出相應(yīng)偽碼：

2） 通過二叉樹找多邊形求交

構(gòu)建完多邊形的二叉樹后，我們可通過多邊形的二叉樹判斷一條邊是在多邊形內(nèi)部還是外部。這里以下圖中邊a，b，c為例。將邊a與首先樹的根節(jié)點進行判斷，根節(jié)點中存的是邊1，則a在邊1所在直線方向的右側(cè)，將邊a再與根節(jié)點的右子節(jié)點進行判斷，右子節(jié)點中存儲的為邊2，a在邊2所在直線的左側(cè)，將a與其左子樹進行判斷，重復(fù)該過程直到該節(jié)點沒有任何子樹了，可以看到該節(jié)點中存儲為邊7，由于a在邊7左側(cè)，之前已經(jīng)介紹過逆時針方向的多邊形，其內(nèi)部在其邊的方向的左側(cè)，至此可判斷a在多邊形內(nèi)。這里邊b與邊2相交，因此在判斷時需要將邊b截斷，邊2左側(cè)的繼續(xù)和邊2的左子樹進行判斷，邊2右側(cè)的繼續(xù)和邊2的右子樹進行判斷，這里左側(cè)邊與之前邊a的判斷順序一樣，最后判定位于多邊形內(nèi)部，而邊2右側(cè)的的與邊3進行判斷，其位于邊3右側(cè)，而邊3沒有右子樹，所以這里判定其為多邊形外部，邊c的判定與其相仿。

解決了邊與多邊位置的判斷，我們就可以開始進行多邊形的求交運算。兩個多邊形求交本質(zhì)上就是找到各個多邊形在另一個多邊內(nèi)部的邊。因此只需要對將一個多邊形的所有邊與另一個多邊形的二叉樹進行判斷，再將另一多邊形重復(fù)該操作，這樣便可找到所有的公共邊。

3） 其他拓撲運算

之前介紹了多邊形相交，這里定義多邊形P與Q相交為P∩Q。這里再定義多邊形取反，這里只需要將多邊形的所有邊進行取反，也就是將時針方向取反，這里定義多邊形P取反為?P。其余多邊形的拓撲運算均可用這兩種運算表示。

4） 拓撲運算結(jié)果的多邊形重構(gòu)

由于實際計算中出現(xiàn)的情況較多，這里就出現(xiàn)的多種典型的歧義性情況作出分析并給出相應(yīng)的算法。

對于以上出現(xiàn)的一個閉合區(qū)域的情況，只需將得到的邊按照邊的方向連接成環(huán)即可。而實際中往往會出現(xiàn)多個閉合區(qū)域的情況，如下圖。該文給出的方法的是先將得到的邊集合進行連通性分析，以結(jié)果中的頂點為節(jié)點形成無向圖，對各個連通區(qū)間進行單獨處理。

在之前的二叉樹計算時，我們將與邊重合的情況也列入多邊形內(nèi)部的情況，所以在得到的結(jié)果中會出現(xiàn)重合邊情況。對于邊重合的情況通常有兩種，分別為同向邊重合與異向邊重合。下圖給出了兩種不同的邊重合情況。兩種情況的處理方法不同。例如下圖a中，兩個多邊形的邊屬于同向邊重合，在計算時需要將兩條重合邊合并為一條，再加入到之前的連通圖中進行計算，而對于圖b中的情況，由于異向邊重合時，結(jié)果往往就是該邊所在的這條線段，所以出現(xiàn)異向邊重合時，我們將其所在線段作為結(jié)果，并將兩條異向重合邊從之前的中間結(jié)果中剔除。

頂點重合的情況通常分為無鄰邊重合與有鄰邊重合。通常無鄰邊重合出現(xiàn)在多邊形僅一點相交的情況，如圖a，其處理方式也較為簡單，將該頂點作為結(jié)果即可。對于有鄰邊的頂點相交，通常在排除邊重合之后需要做一些處理。如圖b中兩個圖形作并操作，則與頂點相鄰的有6條邊，這里需要確定每條邊通過頂點與哪條邊相連。

對于這種類型的點重合，確定邊成對的關(guān)系主要是通過邊的方向來確定。如下圖，這六條邊有3條是指向重合點，3條由頂點指向外部，我們可將這六條邊按此規(guī)律分為入邊與出邊。這里有三條入邊，指向重合點，另三條出邊由頂點出來，其中每條入邊對應(yīng)著一條出邊，不會出現(xiàn)其他情況。要找到入邊對應(yīng)的出邊，這里通過夾角的方式來判定其對應(yīng)關(guān)系，由于入邊左側(cè)對應(yīng)的是多邊形的內(nèi)部，則按其順時針方向找到的最小轉(zhuǎn)角的邊應(yīng)為其對應(yīng)的出邊，所以這里的處理方法是選擇一條入邊，計算其與所有出邊的順時針轉(zhuǎn)角，選擇最小轉(zhuǎn)角的出邊作為其對應(yīng)邊，然后依次對其余入邊進行處理。

經(jīng)過以上處理后，剩下的邊在方向上只有唯一的一條路徑，將剩余邊按照順序連接成閉合區(qū)域即可。

2 實驗結(jié)果

本文所介紹的基于二叉樹的拓撲運算算法，時間復(fù)雜度為nlogn，與當前使用較多的裁剪算法相比，其時間復(fù)雜度為n^2，效率得到明顯提升，同時本算法對于多種歧義情況均有處理，且在實際應(yīng)用中效果較好。但由于多邊形拓撲運算情況較多，實驗中可能會出現(xiàn)未考慮到的情況，將在之后的實驗中進行修正。

參考文獻：

[1] 潘瑜春，鐘耳順，趙春江.GIS空間數(shù)據(jù)庫的更新技術(shù)[J].地球信息科學(xué)，2004（1）.

[2] 杜爽，陳成永.以節(jié)點操作實現(xiàn)多邊形求交的算法[J].測繪通報，2007（10）.

[3] 宋立明，閆浩文，李茜茜，李雙元.兩個簡單多邊形求交的算法[J].測繪與空間地理信息，2011（6）.

[4] 樊建華，黃有群，劉嘉敏.帶孔洞的多邊形求交算法[J].沈陽工業(yè)大學(xué)學(xué)報，2001（5）.

[5] Philip J Schneider，David H Eberly .Geometric tools for computer graphics[C]. 2005.endprint

摘要：該文提出了一種基于二叉樹的幾何圖形拓撲處理算法，實現(xiàn)幾何圖形間的精確處理。并能有效解決大多數(shù)邊界問題，同時可以按需求設(shè)定不同的精度。

關(guān)鍵詞：二叉樹；拓撲運算；邊界問題

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）34-8191-03

隨著Web技術(shù)的發(fā)展，越來越多的應(yīng)用被從傳統(tǒng)的PC端移植到Web端，用戶只需要通過Web瀏覽器就可以得到所需要的服務(wù)。這些Web上的應(yīng)用不僅方便了用戶，也使得自身變得越來越普及。例如百度地圖每天的定位請求數(shù)就達20億以上，可見其用戶規(guī)模。而百度地圖這類應(yīng)用僅僅是WebGis中的一項小功能，而WebGis同樣在在城市規(guī)劃，交通規(guī)劃提供許多功能支持。

WebGis是Web上的地理信息系統(tǒng)，其功能主要是對空間上采集的地理信息進行分析與處理，例如通過人口統(tǒng)計所得的數(shù)據(jù)得到的城市人口密度分布圖，通過道路車輛統(tǒng)計所得的道路交通流量圖。這類信息通常需要通過對采集信息進行精確的拓撲計算得出，例如要計算一個下圖紅線劃定范圍內(nèi)的建筑面積，就需要拿紅色區(qū)域和A，B，C，D四塊區(qū)域進行邏輯判斷，同時計算相交區(qū)域面積。而當前一些開源的拓撲運算庫如Dotspatial等，存在著邊界問題處理不好，精度值無法確定，效率不高等一些問題。

1 關(guān)鍵技術(shù)

1） 多邊形的二叉樹分割

對平面任意閉合多邊形，若指定其包圍區(qū)域為內(nèi)側(cè)，則邊界與內(nèi)側(cè)相對的另外一側(cè)為外側(cè)，若要判斷內(nèi)外側(cè)，一般通過多邊形的方向進行判斷。通常多邊形的方向分為順時針與逆時針，沿多邊形方向，一般定義左側(cè)為內(nèi)側(cè)，右側(cè)為外側(cè)，所以若指定包圍的閉合區(qū)域為內(nèi)側(cè)，則多邊形為逆時針。如下圖，箭頭方向指定了逆時針的方向。

定義好了多邊形的方向后，我們可以對多邊形進行二叉樹分割，其算法大致思想是將多邊形的邊按照多邊形方向形成邊序列，取出序列中首個邊作為二叉樹的根節(jié)點，將其直線方向作為根節(jié)點的方向，再將剩余的邊與根節(jié)點方向進行拓撲判斷，根據(jù)剩余邊與根節(jié)點方向的拓撲關(guān)系，如左側(cè)相離，右側(cè)相離，相交，共線等，依次存入根節(jié)點的左子節(jié)點，右子節(jié)點，以及自身的同向列表中。這里采用遞歸的方式構(gòu)建樹，下面給出相應(yīng)偽碼：

2） 通過二叉樹找多邊形求交

構(gòu)建完多邊形的二叉樹后，我們可通過多邊形的二叉樹判斷一條邊是在多邊形內(nèi)部還是外部。這里以下圖中邊a，b，c為例。將邊a與首先樹的根節(jié)點進行判斷，根節(jié)點中存的是邊1，則a在邊1所在直線方向的右側(cè)，將邊a再與根節(jié)點的右子節(jié)點進行判斷，右子節(jié)點中存儲的為邊2，a在邊2所在直線的左側(cè)，將a與其左子樹進行判斷，重復(fù)該過程直到該節(jié)點沒有任何子樹了，可以看到該節(jié)點中存儲為邊7，由于a在邊7左側(cè)，之前已經(jīng)介紹過逆時針方向的多邊形，其內(nèi)部在其邊的方向的左側(cè)，至此可判斷a在多邊形內(nèi)。這里邊b與邊2相交，因此在判斷時需要將邊b截斷，邊2左側(cè)的繼續(xù)和邊2的左子樹進行判斷，邊2右側(cè)的繼續(xù)和邊2的右子樹進行判斷，這里左側(cè)邊與之前邊a的判斷順序一樣，最后判定位于多邊形內(nèi)部，而邊2右側(cè)的的與邊3進行判斷，其位于邊3右側(cè)，而邊3沒有右子樹，所以這里判定其為多邊形外部，邊c的判定與其相仿。

解決了邊與多邊位置的判斷，我們就可以開始進行多邊形的求交運算。兩個多邊形求交本質(zhì)上就是找到各個多邊形在另一個多邊內(nèi)部的邊。因此只需要對將一個多邊形的所有邊與另一個多邊形的二叉樹進行判斷，再將另一多邊形重復(fù)該操作，這樣便可找到所有的公共邊。

3） 其他拓撲運算

之前介紹了多邊形相交，這里定義多邊形P與Q相交為P∩Q。這里再定義多邊形取反，這里只需要將多邊形的所有邊進行取反，也就是將時針方向取反，這里定義多邊形P取反為?P。其余多邊形的拓撲運算均可用這兩種運算表示。

4） 拓撲運算結(jié)果的多邊形重構(gòu)

由于實際計算中出現(xiàn)的情況較多，這里就出現(xiàn)的多種典型的歧義性情況作出分析并給出相應(yīng)的算法。

對于以上出現(xiàn)的一個閉合區(qū)域的情況，只需將得到的邊按照邊的方向連接成環(huán)即可。而實際中往往會出現(xiàn)多個閉合區(qū)域的情況，如下圖。該文給出的方法的是先將得到的邊集合進行連通性分析，以結(jié)果中的頂點為節(jié)點形成無向圖，對各個連通區(qū)間進行單獨處理。

在之前的二叉樹計算時，我們將與邊重合的情況也列入多邊形內(nèi)部的情況，所以在得到的結(jié)果中會出現(xiàn)重合邊情況。對于邊重合的情況通常有兩種，分別為同向邊重合與異向邊重合。下圖給出了兩種不同的邊重合情況。兩種情況的處理方法不同。例如下圖a中，兩個多邊形的邊屬于同向邊重合，在計算時需要將兩條重合邊合并為一條，再加入到之前的連通圖中進行計算，而對于圖b中的情況，由于異向邊重合時，結(jié)果往往就是該邊所在的這條線段，所以出現(xiàn)異向邊重合時，我們將其所在線段作為結(jié)果，并將兩條異向重合邊從之前的中間結(jié)果中剔除。

頂點重合的情況通常分為無鄰邊重合與有鄰邊重合。通常無鄰邊重合出現(xiàn)在多邊形僅一點相交的情況，如圖a，其處理方式也較為簡單，將該頂點作為結(jié)果即可。對于有鄰邊的頂點相交，通常在排除邊重合之后需要做一些處理。如圖b中兩個圖形作并操作，則與頂點相鄰的有6條邊，這里需要確定每條邊通過頂點與哪條邊相連。

對于這種類型的點重合，確定邊成對的關(guān)系主要是通過邊的方向來確定。如下圖，這六條邊有3條是指向重合點，3條由頂點指向外部，我們可將這六條邊按此規(guī)律分為入邊與出邊。這里有三條入邊，指向重合點，另三條出邊由頂點出來，其中每條入邊對應(yīng)著一條出邊，不會出現(xiàn)其他情況。要找到入邊對應(yīng)的出邊，這里通過夾角的方式來判定其對應(yīng)關(guān)系，由于入邊左側(cè)對應(yīng)的是多邊形的內(nèi)部，則按其順時針方向找到的最小轉(zhuǎn)角的邊應(yīng)為其對應(yīng)的出邊，所以這里的處理方法是選擇一條入邊，計算其與所有出邊的順時針轉(zhuǎn)角，選擇最小轉(zhuǎn)角的出邊作為其對應(yīng)邊，然后依次對其余入邊進行處理。

經(jīng)過以上處理后，剩下的邊在方向上只有唯一的一條路徑，將剩余邊按照順序連接成閉合區(qū)域即可。

2 實驗結(jié)果

本文所介紹的基于二叉樹的拓撲運算算法，時間復(fù)雜度為nlogn，與當前使用較多的裁剪算法相比，其時間復(fù)雜度為n^2，效率得到明顯提升，同時本算法對于多種歧義情況均有處理，且在實際應(yīng)用中效果較好。但由于多邊形拓撲運算情況較多，實驗中可能會出現(xiàn)未考慮到的情況，將在之后的實驗中進行修正。

參考文獻：

[1] 潘瑜春，鐘耳順，趙春江.GIS空間數(shù)據(jù)庫的更新技術(shù)[J].地球信息科學(xué)，2004（1）.

[2] 杜爽，陳成永.以節(jié)點操作實現(xiàn)多邊形求交的算法[J].測繪通報，2007（10）.

[3] 宋立明，閆浩文，李茜茜，李雙元.兩個簡單多邊形求交的算法[J].測繪與空間地理信息，2011（6）.

[4] 樊建華，黃有群，劉嘉敏.帶孔洞的多邊形求交算法[J].沈陽工業(yè)大學(xué)學(xué)報，2001（5）.

[5] Philip J Schneider，David H Eberly .Geometric tools for computer graphics[C]. 2005.endprint