基于線段操作的多邊形求交算法研究

鮑其勝，王 慶，何立恒

(1.南京市測(cè)繪勘察研究院有限公司，江蘇南京210005;2.南京林業(yè)大學(xué)土木工程學(xué)院，江蘇南京210037)

兩個(gè)多邊形求交是計(jì)算幾何的基本問(wèn)題之一，應(yīng)用十分廣泛。地圖制圖中的圖面要素壓蓋處理、地理信息系統(tǒng)中不同類別多邊形拓?fù)浏B加分析、計(jì)算機(jī)輔助設(shè)計(jì)中的文字、圖塊消隱等都直接或間接地用到多邊形求交［1-3］。在進(jìn)行土方計(jì)算時(shí)，需要將計(jì)算邊界之外的格網(wǎng)刪剪掉，實(shí)際也是多邊形求交。邊界外框是由邊界點(diǎn)坐標(biāo)系列中(Xmin，Ymin)為左下角、(Xmax，Ymax)為右上角的矩形，計(jì)算邊界包含于邊界外框內(nèi)。對(duì)邊界范圍內(nèi)的區(qū)域計(jì)算，以計(jì)算邊界外框循環(huán)得到的格網(wǎng)跟計(jì)算邊界有相交、包含和分離3種關(guān)系。為了摒棄計(jì)算邊界范圍外的網(wǎng)形，需要進(jìn)行所構(gòu)網(wǎng)形與邊界的相互關(guān)系判別并求交，得到邊界內(nèi)的網(wǎng)形。

一、幾個(gè)關(guān)系判別算法

1.多邊形相互關(guān)系判別

本文所討論的多邊形是在同一水平面或投影到同一水平面上的簡(jiǎn)單多邊形，多邊形相互關(guān)系判別如圖1所示。將多邊形看做是封閉的線實(shí)體，通過(guò)求線實(shí)體的交點(diǎn)個(gè)數(shù)來(lái)判斷兩個(gè)多邊形的相互關(guān)系。若沒(méi)有交點(diǎn)，則為包含或分離(非包含);若有交點(diǎn)，則為交叉關(guān)系。包含和分離關(guān)系的判定實(shí)質(zhì)是點(diǎn)與多邊形的關(guān)系判定，若頂點(diǎn)都在計(jì)算邊界范圍內(nèi)，則是包含關(guān)系;若頂點(diǎn)都不在計(jì)算邊界內(nèi)，則是分離關(guān)系。

圖1 多邊形相互關(guān)系示意圖

2.點(diǎn)和多邊形相互關(guān)系判別

在點(diǎn)與多邊形相互關(guān)系判定中，采用射線交點(diǎn)法進(jìn)行判定［4-5］。以待判定點(diǎn)為起點(diǎn)作任意射線，通過(guò)射線與多邊形邊界交點(diǎn)的奇偶性來(lái)確定，若交點(diǎn)數(shù)為奇數(shù)，則點(diǎn)在多邊形內(nèi);若交點(diǎn)數(shù)為偶數(shù)，則在多邊形外。通常射線由一段超出多邊形范圍的水平線段代替，此線段的一端點(diǎn)為待判定點(diǎn)，另一端點(diǎn)則是水平向右或向左的多邊形范圍外任一點(diǎn)，如圖2所示。但圖3是交點(diǎn)為多邊形頂點(diǎn)的情況，此法則失效。因此，在判定之前，要明確點(diǎn)是否在多邊形的邊界上。圖3中，圖3(a)有1個(gè)交點(diǎn)，圖3(b)有3個(gè)交點(diǎn)，圖3(c)有4個(gè)交點(diǎn)，圖3(d)有2個(gè)交點(diǎn)，僅以交點(diǎn)的奇偶數(shù)進(jìn)行判別，圖3(b)、圖3(d)與事實(shí)不符。因此，在實(shí)際計(jì)算交點(diǎn)個(gè)數(shù)時(shí)，要特別判定交點(diǎn)是否為多邊形的一個(gè)頂點(diǎn)或在多邊形線段上。因此，設(shè)定一原則，多邊形以交點(diǎn)為線段一端點(diǎn)的兩連續(xù)線段位于射線左右來(lái)制定，位于兩側(cè)的為1個(gè)交點(diǎn)，位于同側(cè)或線上的為0個(gè)交點(diǎn)或2個(gè)交點(diǎn)。

圖2 點(diǎn)和多邊形相互關(guān)系示意圖

圖3 點(diǎn)在多邊形內(nèi)外判定交點(diǎn)幾種特殊情況

二、求交叉關(guān)系算法與實(shí)現(xiàn)

1.算法思路

國(guó)內(nèi)外研究人員對(duì)多邊形求交作了深入研究。楊維芳［6］給出兩數(shù)組記錄交點(diǎn)后，對(duì)數(shù)組遍歷求交;朱愛(ài)軍等［7］在交點(diǎn)序列基礎(chǔ)上擴(kuò)充成節(jié)點(diǎn)序列，通過(guò)遍歷序列求交;杜爽等［8］在交點(diǎn)結(jié)構(gòu)中記錄與交點(diǎn)相關(guān)的節(jié)點(diǎn)信息，如出入狀態(tài)、交點(diǎn)位置等來(lái)求解;宋立明等［9］采用雙向鏈表數(shù)據(jù)結(jié)構(gòu)，對(duì)兩簡(jiǎn)單多邊形的頂點(diǎn)及交點(diǎn)進(jìn)行插入存儲(chǔ)，通過(guò)遍歷兩個(gè)頂點(diǎn)、交點(diǎn)混合表來(lái)達(dá)到求交目的。上述研究的核心都是求出多邊形交點(diǎn)，然后進(jìn)一步對(duì)點(diǎn)操作，本文則另辟蹊徑，在求出多邊形交點(diǎn)后，對(duì)由多邊形節(jié)點(diǎn)和交點(diǎn)組成的子線段進(jìn)行操作，判斷所構(gòu)成的子線段是否屬于公共線段，以構(gòu)成公共線段集，遍歷公共線段，連接成閉合多邊形求交。

2.算法過(guò)程

圖4有兩個(gè)多邊形M、N，求交叉公共多邊形需分步進(jìn)行。

1)選擇多邊形并判定兩多邊形的相互關(guān)系。將平面M作為目標(biāo)多邊形，平面N作為源多邊形。利用交點(diǎn)個(gè)數(shù)判斷兩多邊形的相互關(guān)系，若相交，繼續(xù)下一步;若分離，結(jié)束計(jì)算;若包含，留下被包含圖形后結(jié)束計(jì)算。

2)求交點(diǎn)。選取目標(biāo)多邊形M中線段M1M2與源多邊形N的每條線段求交點(diǎn)，若線段M1M2與源多邊形N邊界有交點(diǎn)，將所有交點(diǎn)去掉重復(fù)點(diǎn)后，連同從目標(biāo)多邊形所選定線段M1M2的端點(diǎn)按此線段的一定方向排序，如圖4所示，M1、P1、…、Pn、M2為排序的系列點(diǎn)。其中，M1、M2為目標(biāo)多邊形的線段端點(diǎn);P1、…、Pn為線段M1M2與源多邊形N的所有交點(diǎn)。

圖4 求公共面

兩線段p1p2和q1q2交點(diǎn)一般為圖5幾種情形，本算法中的交點(diǎn)個(gè)數(shù)分別為：圖5(a)為J一點(diǎn)，圖5(b)為p2一點(diǎn)，圖5(c)為p2(或q1)一點(diǎn)，圖5(d)為p2和q1兩點(diǎn)，圖5(e)為p1和p2兩點(diǎn)，圖5(f)為q1(或p1)和q2(或p2)兩點(diǎn)。

圖5 線段交點(diǎn)關(guān)系圖

3)找公共線段。將端點(diǎn)和交點(diǎn)依順序兩兩作子線段，即 M1P1、P1P2、…、PnM2為依次連接的線段，求各線段的中點(diǎn)，根據(jù)點(diǎn)在多邊形內(nèi)外判定方法判斷中點(diǎn)與源多邊形N的相互關(guān)系，若線段的中點(diǎn)在源多邊形內(nèi)或在源多邊形邊界上，則此線段也在源多邊形內(nèi)或在源多邊形邊界上，此線段即為公共線段，將此線段及線段的兩個(gè)端點(diǎn)坐標(biāo)記錄在數(shù)據(jù)選擇集中，直至所有兩兩點(diǎn)連成的線段判定完畢。圖4中線段P1P2和P3P4即為公共線段。

4)選取構(gòu)成目標(biāo)多邊形M的下一個(gè)線段，重復(fù)步驟2)和步驟3)，直至構(gòu)成目標(biāo)多邊形M的所有線段與源多邊形N求交點(diǎn)計(jì)算完畢，然后判斷各相鄰點(diǎn)連成的線段是否在源多邊形內(nèi)或邊界上，若在源多邊形內(nèi)或邊界上，即為公共線段并記錄至公共數(shù)據(jù)選擇集中。

5)將目標(biāo)多邊形和源多邊形對(duì)調(diào)，原源多邊形作為目標(biāo)多邊形，原目標(biāo)多邊形作為源多邊形，重復(fù)步驟2)～步驟4)。進(jìn)行步驟3)操作時(shí)，若線段的中點(diǎn)在源多邊形內(nèi)，記錄至公共線段;若線段的中點(diǎn)在源多邊形邊界上，因目標(biāo)多邊形和源多邊形對(duì)調(diào)前已記錄，對(duì)調(diào)后將不再記錄，避免重復(fù)。

6)遍歷公共線段，構(gòu)建兩多邊形交集。從公共線段數(shù)據(jù)選擇集中取出任一線段，根據(jù)此線段端點(diǎn)坐標(biāo)，在公共線段數(shù)據(jù)選擇集中找與其首尾相連的線段，將它們連接起來(lái)，依次找出與連接圖形端點(diǎn)相同的其他線段并連接，組成封閉多邊形。在尋找過(guò)程中，選中的線段就從公共線段數(shù)據(jù)選擇集中刪掉。

7)若組成一個(gè)封閉多邊形后，公共線段數(shù)據(jù)集中還有線段，重復(fù)步驟6)，直至公共線段數(shù)據(jù)集中沒(méi)有線段，此時(shí)構(gòu)成的所有封閉多邊形即為所求的兩多邊形交集。

三、算法分析比較

1)本算法是在求交點(diǎn)后，組成子線段進(jìn)行判斷并求交，判斷過(guò)程中已考慮重邊或重點(diǎn)等問(wèn)題。楊維芳［6］使用數(shù)組只能表示一個(gè)交點(diǎn)，對(duì)重邊有兩個(gè)交點(diǎn)的不能表示;朱愛(ài)軍、杜爽等［7-8］采用交點(diǎn)序列或出入狀態(tài)判別，過(guò)程復(fù)雜，尤其對(duì)重邊、重點(diǎn)要單獨(dú)考慮，顯得繁瑣;宋立明等［9］采用了雙向鏈表數(shù)據(jù)結(jié)構(gòu)，沒(méi)有解決重邊或重點(diǎn)問(wèn)題。

2)上述已有算法的記錄方式都有兩組數(shù)組、序列或鏈表，探測(cè)對(duì)象是節(jié)點(diǎn)，探測(cè)方向都是在兩組存儲(chǔ)數(shù)據(jù)中轉(zhuǎn)換。本算法采用由節(jié)點(diǎn)和交點(diǎn)組成的子線段為探測(cè)對(duì)象，形成一組公共線段集，遍歷公共線段數(shù)據(jù)集求交，探測(cè)對(duì)象及探測(cè)方法包羅了重邊或重點(diǎn)的情況。

3)從算法的時(shí)間上比較，求交點(diǎn)與已有算法基本一致;在探測(cè)每一線段及交點(diǎn)時(shí)，已有算法只對(duì)交點(diǎn)操作，本算法探測(cè)節(jié)點(diǎn)和交點(diǎn)組成的子線段，每條邊多一次探測(cè)，總共多出兩多邊形邊數(shù)總和;在遍歷時(shí)間上，本算法只對(duì)公共線段數(shù)據(jù)集遍歷，明顯比已有算法要短;總體時(shí)間與已有算法相當(dāng)。

4)在存儲(chǔ)單元上，本算法存儲(chǔ)的是公共線段，已有算法存儲(chǔ)的是節(jié)點(diǎn)和交點(diǎn)，本算法遠(yuǎn)優(yōu)于已有算法。

5)本算法在進(jìn)行子線段探測(cè)時(shí)，只需改變探測(cè)條件，即可實(shí)現(xiàn)兩多邊形的求差和求并。

四、結(jié)束語(yǔ)

本算法過(guò)程簡(jiǎn)單、思路嚴(yán)謹(jǐn)，考慮到地圖的復(fù)雜性和特殊性，運(yùn)算結(jié)果精度和圖形輸出質(zhì)量高。若算法基于AutoCAD平臺(tái)來(lái)實(shí)現(xiàn)，利用二次開(kāi)發(fā)工具VBA中object.IntersectWith函數(shù)的返回值求交點(diǎn)個(gè)數(shù)及交點(diǎn)坐標(biāo)，使得計(jì)算過(guò)程更簡(jiǎn)單，運(yùn)行效率更高。連線利用AutoCAD中的數(shù)據(jù)選擇集，在數(shù)據(jù)存儲(chǔ)空間上和搜尋時(shí)間上效率又一步得到提高。

求公共面算法主要是針對(duì)計(jì)算機(jī)地圖制圖、地理信息系統(tǒng)、計(jì)算機(jī)輔助設(shè)計(jì)等領(lǐng)域中多邊形求交，即著重于地圖上多邊形的交集運(yùn)算。本算法易于編程實(shí)現(xiàn)，計(jì)算工作量小，求交效率高，已成功應(yīng)用在土方計(jì)算軟件開(kāi)發(fā)中，在計(jì)算機(jī)圖形和地理空間信息等方面可以廣泛應(yīng)用。

［1］謝忠，魏東琦，吳亮，等.簡(jiǎn)單矢量數(shù)據(jù)多邊形裁剪問(wèn)題的圖模型［J］.測(cè)繪學(xué)報(bào)，2009，38(4)：369-374.

［2］劉勇奎，高云，黃有群.一個(gè)有效的多邊形裁剪算法［J］.軟件學(xué)報(bào)，2003，14(4)：845-856.

［3］彭杰，劉南，唐遠(yuǎn)彬，等.一種基于交點(diǎn)排序的高效多邊形裁剪算法［J］.浙江大學(xué)學(xué)報(bào)：理學(xué)版，2012，39(1)：107-111，122.

［4］董秀山，劉潤(rùn)濤.判斷點(diǎn)與簡(jiǎn)單多邊形位置關(guān)系的新算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(2)：185-186.

［5］陳瑞卿，周健，虞烈.一種判斷點(diǎn)與多邊形關(guān)系的快速算法［J］.西安交通大學(xué)學(xué)報(bào)，2007，14(1)：59-63.

［6］楊維芳.兩個(gè)復(fù)雜多邊形求交的矢量算法［J］.蘭州鐵道學(xué)院學(xué)報(bào)：自然科學(xué)版，2002，21(1)：108-110.

［7］朱愛(ài)軍，鄧安福，魏艷軍，等.以節(jié)點(diǎn)操作確定兩任意實(shí)心多邊形交集的方法［J］.重慶大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，34(12)：56-59.

［8］杜爽，陳成永.以節(jié)點(diǎn)操作實(shí)現(xiàn)多邊形求交的算法［J］.測(cè)繪通報(bào)，2007(10)：21-24.

［9］宋立明，閆浩文，王邦松，等.兩個(gè)簡(jiǎn)單多邊形求交的算法［J］.測(cè)繪與空間地理信息，2011，34(1)：258-260.

［10］張帆.AutoCAD VBA二次開(kāi)發(fā)教程［M］.北京：清華大學(xué)出版社，2006.