蔡琪

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

關(guān)鍵詞：二叉樹；拓?fù)溥\(yùn)算；邊界問(wèn)題

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8191-03

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

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

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

1） 多邊形的二叉樹分割

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

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

2） 通過(guò)二叉樹找多邊形求交

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

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

3） 其他拓?fù)溥\(yùn)算

之前介紹了多邊形相交，這里定義多邊形P與Q相交為P∩Q。這里再定義多邊形取反，這里只需要將多邊形的所有邊進(jìn)行取反，也就是將時(shí)針?lè)较蛉》?，這里定義多邊形P取反為?P。其余多邊形的拓?fù)溥\(yùn)算均可用這兩種運(yùn)算表示。

4） 拓?fù)溥\(yùn)算結(jié)果的多邊形重構(gòu)

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

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

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

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

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

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

2 實(shí)驗(yàn)結(jié)果

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

參考文獻(xiàn)：

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

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

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

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

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

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

關(guān)鍵詞：二叉樹；拓?fù)溥\(yùn)算；邊界問(wèn)題

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8191-03

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

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

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

1） 多邊形的二叉樹分割

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

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

2） 通過(guò)二叉樹找多邊形求交

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

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

3） 其他拓?fù)溥\(yùn)算

之前介紹了多邊形相交，這里定義多邊形P與Q相交為P∩Q。這里再定義多邊形取反，這里只需要將多邊形的所有邊進(jìn)行取反，也就是將時(shí)針?lè)较蛉》?，這里定義多邊形P取反為?P。其余多邊形的拓?fù)溥\(yùn)算均可用這兩種運(yùn)算表示。

4） 拓?fù)溥\(yùn)算結(jié)果的多邊形重構(gòu)

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

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

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

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

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

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

2 實(shí)驗(yàn)結(jié)果

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

參考文獻(xiàn)：

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

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

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

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

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

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

關(guān)鍵詞：二叉樹；拓?fù)溥\(yùn)算；邊界問(wèn)題

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8191-03

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

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

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

1） 多邊形的二叉樹分割

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

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

2） 通過(guò)二叉樹找多邊形求交

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

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

3） 其他拓?fù)溥\(yùn)算

之前介紹了多邊形相交，這里定義多邊形P與Q相交為P∩Q。這里再定義多邊形取反，這里只需要將多邊形的所有邊進(jìn)行取反，也就是將時(shí)針?lè)较蛉》矗@里定義多邊形P取反為?P。其余多邊形的拓?fù)溥\(yùn)算均可用這兩種運(yùn)算表示。

4） 拓?fù)溥\(yùn)算結(jié)果的多邊形重構(gòu)

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

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

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

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

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

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

2 實(shí)驗(yàn)結(jié)果

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

參考文獻(xiàn)：

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

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

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

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

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