王慧青　　崇素文

(1東南大學(xué)儀器科學(xué)與工程學(xué)院, 南京210096)(2展訊通信(上海)有限公司, 上海 201203)

?

一種處理交點(diǎn)退化現(xiàn)象的高效多邊形裁剪算法

王慧青1崇素文2

(1東南大學(xué)儀器科學(xué)與工程學(xué)院, 南京210096)(2展訊通信(上海)有限公司, 上海 201203)

針對復(fù)雜多邊形裁剪中出現(xiàn)的多邊形彼此間重點(diǎn)和重邊現(xiàn)象，提出了一種能夠處理交點(diǎn)退化現(xiàn)象的高效多邊形裁剪算法.該算法利用單向鏈表實(shí)現(xiàn)多邊形的存儲，同時基于單調(diào)鏈的平面掃描法求解多邊形間的交點(diǎn)，減少了多邊形頂點(diǎn)的遍歷次數(shù)和求交次數(shù)；對于重點(diǎn)和重邊現(xiàn)象，通過交點(diǎn)關(guān)聯(lián)的線段間的方向關(guān)系判別交點(diǎn)的進(jìn)出性；最后更新多邊形頂點(diǎn)序列，獲取裁剪結(jié)果.實(shí)驗(yàn)結(jié)果表明，該算法能夠完成對含內(nèi)環(huán)多邊形的裁剪，在交點(diǎn)退化情況下也能獲得準(zhǔn)確的裁剪結(jié)果.且該算法裁剪效率較Greiner-Hormann算法大幅提高，具有很高的執(zhí)行效率和實(shí)用性.

多邊形裁剪;交點(diǎn)退化;單向鏈表;方向關(guān)系

多邊形裁剪算法被廣泛地應(yīng)用于計(jì)算機(jī)圖形學(xué)、地理信息系統(tǒng)(GIS)[1]及相關(guān)領(lǐng)域,其目的是提取裁剪多邊形與主多邊形(被裁剪多邊形)的相交區(qū)域.常用的裁剪算法有Weiler-Atherton算法[2]、Vatti算法[3]及Greiner-Hormann算法[4],后兩者在復(fù)雜性和運(yùn)行效率方面優(yōu)于前者,但都能實(shí)現(xiàn)對一般多邊形的裁剪.為了進(jìn)一步提高裁剪效率及處理復(fù)雜多邊形裁剪問題,劉勇奎等[5]以Greiner-Hormann算法為基礎(chǔ),優(yōu)化了交點(diǎn)數(shù)據(jù)結(jié)構(gòu)和計(jì)算方法,提出了兩多邊形的邊重合或者兩多邊形在頂點(diǎn)處相交的特殊情況的處理思路,但未給出具體實(shí)現(xiàn)方法.張鈞等[6]通過簡化交點(diǎn)和多邊形頂點(diǎn)數(shù)據(jù)結(jié)構(gòu),減少了多邊形間求交次數(shù),能正確裁剪一般多邊形,并提高了裁減效率.王結(jié)臣等[7]提出了基于梯形分割技術(shù)的復(fù)雜多邊形裁剪方法,該方法裁剪效率較高,但未使用實(shí)際復(fù)雜多邊形驗(yàn)證其可行性.綜上,目前多邊形裁剪算法在復(fù)雜多邊形裁剪和重點(diǎn)重邊(又稱為交點(diǎn)退化現(xiàn)象)等問題上需要進(jìn)一步研究.

本文基于Greiner-Hormann算法,提出了一種能夠處理交點(diǎn)退化現(xiàn)象的多邊形裁剪算法.該算法采用單向鏈表實(shí)現(xiàn)多邊形存儲,利用基于單調(diào)鏈的平面掃描法求解多邊形間的交點(diǎn),對于重點(diǎn)重邊問題,基于交點(diǎn)關(guān)聯(lián)的線段間的方向關(guān)系來判別交點(diǎn)的進(jìn)出性,最終依據(jù)交點(diǎn)的進(jìn)出性依次遍歷頂點(diǎn)序列，得到裁剪結(jié)果.該方法不論是對一般多邊形還是復(fù)雜多邊形均能取得正確的剪裁結(jié)果.

1　多邊形裁剪算法的一般流程

多邊形裁剪算法需要能夠完成主多邊形與裁剪多邊形都為任意多邊形時的幾何計(jì)算,其主要過程如下:

① 將多邊形的頂點(diǎn)序列轉(zhuǎn)化為裁剪算法所使用的雙向鏈表數(shù)據(jù)結(jié)構(gòu).

② 采用平面掃描法判別出存在相交關(guān)系的線段,并求解交點(diǎn)值.

③ 判別交點(diǎn)的進(jìn)出性.

④ 將交點(diǎn)插入到頂點(diǎn)序列數(shù)據(jù)結(jié)構(gòu)中,構(gòu)成新的頂點(diǎn)序列.

⑤ 根據(jù)交點(diǎn)的進(jìn)出性依次遍歷頂點(diǎn)序列，得到裁剪結(jié)果.

2　基于線段方向關(guān)系的交點(diǎn)退化現(xiàn)象處理

2.1交點(diǎn)進(jìn)出性判別方法

入點(diǎn)和出點(diǎn)是Greiner-Hormann算法中很重要的2個概念.如圖1所示,入點(diǎn)和出點(diǎn)定義如下:假設(shè)點(diǎn)i為主多邊形A和裁剪多邊形B的一個交點(diǎn),如果沿著A的邊界方向,可在點(diǎn)i處從B外部進(jìn)入B內(nèi)部,則稱點(diǎn)i為一個進(jìn)點(diǎn);如果沿著A的邊界方向,可在點(diǎn)i處從B內(nèi)部出到B外部,則稱點(diǎn)i為一個出點(diǎn)[8].

圖1　兩多邊形相交圖

(1)

圖2　相交矢量線段SnSn+1→和 CmCm+1→

由式(1)得

(2)

2.2交點(diǎn)退化問題分析

交點(diǎn)的退化現(xiàn)象大致可分為2種情況:① 存在一個交點(diǎn)是某個多邊形頂點(diǎn),即圖3中所示多邊形重點(diǎn)現(xiàn)象;② 存在2個及以上且連續(xù)的交點(diǎn)是多邊形頂點(diǎn),即圖4中所示多邊形重邊現(xiàn)象.主多邊形用S={S1,S2,S3,S4}表示,裁剪多邊形用C={C1,C2,…,C5}表示,兩多邊形交點(diǎn)集合用In={I1,I2,…,Ii，…,Ik}表示.

圖3(a)中交點(diǎn)I1與頂點(diǎn)C1重合；圖3(b)中交點(diǎn)I1與頂點(diǎn)C1重合,且邊C1C2和C1C4在邊S1S2的內(nèi)側(cè)；圖3(c)中交點(diǎn)I1與頂點(diǎn)S1和C1重合,且邊C1C2和C1C5在多邊形的外側(cè).以上3種情況都是由于交點(diǎn)與多邊形頂點(diǎn)重合而無法判斷交點(diǎn)的進(jìn)出性,同時也造成了交點(diǎn)的冗余.

(a)

(b)

(c)

圖4(a)中交點(diǎn)I1與頂點(diǎn)S1和C1重合,交點(diǎn)I2與頂點(diǎn)C2重合,從而邊S1S2與邊C1C2的重合部分為I1I2；圖4(b)中交點(diǎn)I1與頂點(diǎn)C1重合,交點(diǎn)I2與頂點(diǎn)C2重合,從而邊S1S2與邊C1C2的重合部分為I1I2；圖4(c)中交點(diǎn)I1與頂點(diǎn)C1和S1重合,交點(diǎn)I2與頂點(diǎn)C2和S2重合,交點(diǎn)I6與頂點(diǎn)C5重合.以上3種情況均存在連續(xù)交點(diǎn)退化而導(dǎo)致的重邊現(xiàn)象.

2.3交點(diǎn)退化問題的解決方法

2.3.1交點(diǎn)的數(shù)據(jù)結(jié)構(gòu)

交點(diǎn)的數(shù)據(jù)結(jié)構(gòu)影響多邊形裁剪中交點(diǎn)進(jìn)出性的判別及裁剪結(jié)果的構(gòu)建.本文設(shè)計(jì)的交點(diǎn)數(shù)據(jù)結(jié)構(gòu)中主要信息包括:交點(diǎn)的坐標(biāo)信息Coordinate,產(chǎn)生交點(diǎn)Ik的相交線段的前一個點(diǎn)在主多邊形和裁剪多邊形頂點(diǎn)的序號SegmentIndex, 交點(diǎn)Ik與該頂點(diǎn)的距離Distance,交點(diǎn)的進(jìn)出性ioAttri(值為1是進(jìn)點(diǎn),值為0是出點(diǎn),默認(rèn)值為-1).

(a)

(b)

(c)

2.3.2基于交點(diǎn)關(guān)聯(lián)線段間的交點(diǎn)進(jìn)出性判別

2.2節(jié)中已經(jīng)表明交點(diǎn)退化現(xiàn)象會導(dǎo)致對交點(diǎn)的進(jìn)出性做出錯誤判斷,本文提出基于交點(diǎn)關(guān)聯(lián)線段間的方向關(guān)系來判別交點(diǎn)進(jìn)出性的方法.方向關(guān)系是指在某個參考框架下,從空間一個目標(biāo)到空間另一個目標(biāo)的方向[9].對圖5中的線段方向關(guān)系判別方法：① 判別交點(diǎn)Ik是否為該主多邊形和裁剪多邊形的頂點(diǎn),如果是則通過交點(diǎn)的SegmentIndex得到該交點(diǎn)主多邊形前一個頂點(diǎn)Sn-1和后一個頂點(diǎn)Sn+1,得到裁剪多邊形前一個頂點(diǎn)Cm-1和后一個頂點(diǎn)Cm+1.② 以Sn-1,Sn和Sn+1為參考邊,根據(jù)線段Cm-1Cm和CmCm+1與線段Sn-1Sn與SnSn+1的方向關(guān)系,判斷線段Cm-1Cm和CmCm+1位于主多邊形的邊界、內(nèi)部還是外部,進(jìn)而判別出該交點(diǎn)的進(jìn)出性.圖5為部分交點(diǎn)與頂點(diǎn)重合的情況,其他重合情況可參考該方法解決.

(a) 　　(b)

(c)

3　改進(jìn)的多邊形裁剪算法

Greiner-Hormann算法采用雙向鏈表的數(shù)據(jù)結(jié)構(gòu),需要存儲多邊形頂點(diǎn)前后關(guān)聯(lián)點(diǎn)的信息,增加了數(shù)據(jù)存儲量,同時雙向鏈表的遍歷操作與單向鏈表相比更為繁瑣.因此，本文采用單向鏈表的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)多邊形裁剪算法,減少了頂點(diǎn)遍歷次數(shù)和求交次數(shù),裁剪效率大幅提高.

3.1多邊形交點(diǎn)求解

將多邊形的邊有規(guī)律地進(jìn)行分割,被分割的邊稱為單調(diào)鏈，即具有某種相同方向關(guān)系的連續(xù)點(diǎn)構(gòu)成的邊,如圖6所示將多邊形A分割成4條單調(diào)鏈.然后采用平面掃描法求解平面線段集的交點(diǎn).平面掃描法判別交點(diǎn)的思路是用一條垂直的掃描線段從左到右掃描過平面,在每個事件點(diǎn)(即線段的頂點(diǎn)和線段之間的交點(diǎn))處修改掃描狀態(tài)表,再檢測相鄰單調(diào)鏈間是否存在相交點(diǎn).若檢測到一個交點(diǎn),則獲取該線段及其交點(diǎn)的坐標(biāo),并將交點(diǎn)橫坐標(biāo)插入到掃描事件中[10-11].

圖6　多邊形單調(diào)鏈分割圖

3.2改進(jìn)多邊形裁剪算法流程

改進(jìn)的多邊形裁剪算法步驟如下:

1) 采用單向鏈表的數(shù)據(jù)結(jié)構(gòu)將裁剪多邊形C和主多邊形S的外環(huán)頂點(diǎn)坐標(biāo)按順時針存儲,內(nèi)環(huán)頂點(diǎn)坐標(biāo)按逆時針存儲.

2) 按順序?qū)Σ眉舳噙呅蜟的邊與主多邊形S的內(nèi)外環(huán)進(jìn)行求交計(jì)算,求出可能存在交點(diǎn)的邊,并確保交點(diǎn)坐標(biāo)的唯一性.

3) 以主多邊形S為參考對象,判斷出將要插入到裁剪多邊形C中的交點(diǎn)的進(jìn)出性,且該交點(diǎn)插入到主多邊形S的進(jìn)出性與之相反.

4) 依據(jù)交點(diǎn)數(shù)據(jù)結(jié)構(gòu)中距離Distance屬性值是否為零,判別交點(diǎn)是否為多邊形的頂點(diǎn),進(jìn)而判別是否存在重點(diǎn)現(xiàn)象.

① 如果交點(diǎn)存在重點(diǎn)現(xiàn)象,采用線段方向關(guān)系判別交點(diǎn)的進(jìn)出性;

② 如果交點(diǎn)不是主多邊形S和裁剪多邊形C的頂點(diǎn),則利用式(2)就可判別出交點(diǎn)的進(jìn)出性.

5) 按順序?qū)⒔稽c(diǎn)添加到多邊形頂點(diǎn)序列中,更新頂點(diǎn)序列表.

6) 交替遍歷更新后裁剪多邊形和主多邊形頂點(diǎn)序列,通過頂點(diǎn)的進(jìn)出性和添加的交點(diǎn)的進(jìn)出性得到裁剪結(jié)果.

4　實(shí)驗(yàn)結(jié)果與分析

本文主要從算法有效性和執(zhí)行效率2個方面進(jìn)行了測試.有效性測試主要針對含有內(nèi)環(huán)的復(fù)雜多邊形和存在重點(diǎn)和重邊現(xiàn)象的2個多邊形裁剪,然后比較了Greiner-Hormann算法與本文優(yōu)化裁剪算法的裁剪時間.因本文提出的改進(jìn)算法采用單鏈表數(shù)據(jù)結(jié)構(gòu),因而鏈表的存儲數(shù)據(jù)量、遍歷頂點(diǎn)次數(shù)和求交次數(shù)均有所減少,內(nèi)存空間消耗也會減少,所以本文未對內(nèi)存消耗做進(jìn)一步測試.

4.1算法有效性測試

4.1.1復(fù)雜多邊形的裁剪測試

含有內(nèi)環(huán)的多邊形被稱為復(fù)雜多邊形,本文通過對含有一個內(nèi)環(huán)和多個內(nèi)環(huán)的主多邊形進(jìn)行裁剪測試,驗(yàn)證所提算法對復(fù)雜多邊形裁剪的有效性.測試裁剪結(jié)果如圖7和圖8所示.實(shí)驗(yàn)結(jié)果表明本文算法可以實(shí)現(xiàn)對含有多個內(nèi)環(huán)的多邊形的裁剪.

(a) 裁剪數(shù)據(jù)

(b) 裁剪結(jié)果

(a) 裁剪數(shù)據(jù)　(b) 裁剪結(jié)果

4.1.2含有重點(diǎn)和重邊的多邊形裁剪測試

存在重點(diǎn)和重邊現(xiàn)象的多邊形裁剪實(shí)驗(yàn)測試結(jié)果如圖9和圖10所示.實(shí)驗(yàn)結(jié)果表明在存在重點(diǎn)和重邊的多邊形裁剪中,采用基于線段方向關(guān)系判別交點(diǎn)進(jìn)出性方法,能夠得到準(zhǔn)確的多邊形裁剪結(jié)果.

(a) 簡單相交多邊形　　(b) 圖(a)裁剪結(jié)果

(c) 復(fù)雜相交多邊形　　(d) 圖(c)裁剪結(jié)果

(c) 復(fù)雜相交多邊形　　(d) 圖(c)裁剪結(jié)果

4.2算法效率測試

本文中算法效率對比測試不考慮交點(diǎn)退化現(xiàn)象.在保持交點(diǎn)個數(shù)不變且裁剪多邊形頂點(diǎn)個數(shù)也不變的情況下,測試用的主多邊形頂點(diǎn)數(shù)逐漸增加, 求得此時改進(jìn)算法與Greiner-Hormann算法所消耗的時間.實(shí)驗(yàn)結(jié)果如表1所示.

表1　Greiner-Hormann算法與改進(jìn)算法的裁剪時間比較

由表1可知, 2種裁剪算法所需要的時間均隨著主多邊形頂點(diǎn)數(shù)目的增加而增加.在頂點(diǎn)數(shù)和交點(diǎn)數(shù)相同的情況下,改進(jìn)算法所需時間要少于Greiner-Hormann算法.隨著主多邊形頂點(diǎn)數(shù)目的增加,改進(jìn)算法的時間消耗增加低于Greiner-Hormann算法,最終改進(jìn)算法相對于Greiner-Hormann算法的時間消耗減少了接近50%.但表1中改進(jìn)算法測試序列3和7不符合上述規(guī)律,即主多邊形頂點(diǎn)個數(shù)增加時,裁剪時間并未有規(guī)律地增加.分析其原因在于這2組試驗(yàn)中所用的主多邊形較復(fù)雜,因而被分割成較多的單調(diào)鏈,增加了處理時間,從而導(dǎo)致裁剪時間較長.

5　結(jié)語

本文在借鑒現(xiàn)有多邊形裁剪算法的思想以及優(yōu)點(diǎn)的基礎(chǔ)上,優(yōu)化了交點(diǎn)數(shù)據(jù)結(jié)構(gòu)和求解方法,提出了一種快速有效的多邊形裁剪算法.該算法適用于復(fù)雜的含有內(nèi)環(huán)的多邊形裁剪,測試表明改進(jìn)算法在剪裁時間上優(yōu)于Greiner-Hormann算法.其中，提出的利用交點(diǎn)關(guān)聯(lián)線段間的分析關(guān)系來判定交點(diǎn)進(jìn)出性的方法,能夠解決存在交點(diǎn)退化現(xiàn)象的多邊形裁剪問題,具有較好的實(shí)用性.

References)

[1]宋樹華, 濮國梁, 羅旭, 等. 簡單多邊形裁剪算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2014, 35(1):192-197.DOI:10.3969/j.issn.1000-7024.2014.01.036.

Song Shuhua, Pu Guoliang, Luo Xu, et al. Algorithm for simple polygon clipping[J].ComputerEngineeringandDesign, 2014, 35(1):192-197. DOI:10.3969/j.issn.1000-7024.2014.01.036.(in Chinese)

[2]Weiler K, Atherton P. Hidden surface removal using polygon area sorting[J].ACMSIGGRAPHComputerGraphics, 1977, 11(2):214-222. DOI:10.1145/965141.563896.

[3]Vatti B R. A generic solution to polygon clipping[J].CommunicationsoftheACM, 1992, 35(7):56-63.DOI:10.1145/129902.129906.

[4]Greiner G, Hormann K. Efficient clipping of arbitrary polygons[J].ACMTransactionsonGraphics, 1998, 17(2):71-83. DOI:10.1145/274363.274364.

[5]劉勇奎, 高云, 黃有群. 一個有效的多邊形裁剪算法[J]. 軟件學(xué)報, 2003, 14(4):845-856.

Liu Yongkui, Gao Yun, Huang Youqun. An efficient algorithm for polygon clipping[J].JournalofSoftware, 2003, 14(4):845-856.(in Chinese)

[6]張鈞, 王鵬. 一種新的矢量數(shù)據(jù)多邊形的快速裁剪算法[J]. 中國圖象圖形學(xué)報, 2008, 13(12):2409-2413.

Zhang Jun, Wang Peng. A new fast polygon clipping algorithm for vector data[J].JournalofImageandGraphics, 2008, 13(12):2409-2413.(in Chinese)

[7]王結(jié)臣, 沈定濤, 陳焱明，等. 一種有效的復(fù)雜多邊形裁剪算法[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 2010,35(3): 369-372,377.

Wang Jiechen,Shen Dingtao,Chen Yanming,et al. An efficient algorithm for complex polygon clipping [J].GeomaticsandInformationScienceofWuhanUniversity, 2010, 35(3): 369-372,377.(in Chinese)

[8]彭杰, 劉南, 唐遠(yuǎn)彬, 等. 一種基于交點(diǎn)排序的高效多邊形裁剪算法[J]. 浙江大學(xué)學(xué)報(理學(xué)版), 2012, 39(1):107-111,122. DOI:10.3785/j.issn.1008-9497.2012.01.022.

Peng Jie, Liu Nan, Tang Yuanbin, et al. An efficient algorithm for polygon clipping based on intersection points sorting[J].JournalofZhejiangUniversity(ScienceEdition), 2012, 39(1):107-111,122. DOI:10.3785/j.issn.1008-9497.2012.01.022.(in Chinese)

[9]鄧敏, 李志林, 吳靜. 空間關(guān)系理論與方法[M]. 北京:科學(xué)出版社, 2013:88-110.

[10]閆浩文, 張黎明, 李茜茜, 等. 復(fù)合多邊形求差的高效矢量算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2013, 30(10):3192-3194. DOI:10.3969/j.issn.1001-3695.2013.10.079.

Yan Haowen, Zhang Liming, Li Qianqian, et al. Vector-based efficient algorithm for computing differences between two complex polygons[J].ApplicationResearchofComputers, 2013, 30(10):3192-3194. DOI:10.3969/j.issn.1001-3695.2013.10.079.(in Chinese)

[11]Chen Z L, Ma L N, Wu L. Polygon overlay analysis algorithm based on monotone chain and STR tree in the simple feature model[C]//2010InternationalConferenceonElectricalandControlEngineering. Harbin, China, 2010: 2905-2909. DOI:10.1109/icece.2010.1420.

A high efficient polygon clipping algorithm for dealing with intersection degradation

Wang Huiqing1Chong Suwen2

(1School of Instrument Science and Engineering, Southeast University, Nanjing 210096, China)(2Spreadtrum Communications (Shanghai) Co., Ltd., Shanghai 201203, China)

Aiming at complex polygon clipping with coincidence points and coincidence edges, a high efficient algorithm for polygon clipping is proposed for dealing with intersection degradation. The algorithm uses singly linked lists to store polygons, and acquires intersection points between polygons based on the planar scanning method with a monotone chain, thus reducing the times of traversing polygon vertices and calculating intersections. Then, it marks the entry and exit points to the clipping polygon’s interior based on the direction relationship between line segments with intersections. Finally, it updates the polygon vertex sequence and obtains cutting results. The experimental results show that the algorithm can clip a polygon with several inner rings, and obtain right clipping results even under the condition of intersection degradation. The cutting efficiency of the algorithm is significantly higher than that of the Greiner-Hormann algorithm. Therefore, it has high efficiency and practicability.

polygon clipping; intersection degradation; singly linked list; direction relationship

10.3969/j.issn.1001-0505.2016.04.005

2015-12-21.作者簡介: 王慧青(1976—),女,博士,副研究員,921394420@qq.com.

“十二五”國家科技支撐計(jì)劃資助項(xiàng)目(2013BAJ13B01).

10.3969/j.issn.1001-0505.2016.04.005.

TP391

A

1001-0505(2016)04-0702-06

引用本文: 王慧青，崇素文.一種處理交點(diǎn)退化現(xiàn)象的高效多邊形裁剪算法[J].東南大學(xué)學(xué)報(自然科學(xué)版),2016,46(4):702-707.