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

王慧青　　崇素文

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

?

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

王慧青1崇素文2

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

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

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

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

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

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

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

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

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

③ 判別交點的進出性.

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

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

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

2.1交點進出性判別方法

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

圖1　兩多邊形相交圖

(1)

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

由式(1)得

(2)

2.2交點退化問題分析

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

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

(a)

(b)

(c)

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

2.3交點退化問題的解決方法

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

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

(a)

(b)

(c)

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

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

(a) 　　(b)

(c)

3　改進的多邊形裁剪算法

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

3.1多邊形交點求解

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

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

3.2改進多邊形裁剪算法流程

改進的多邊形裁剪算法步驟如下:

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

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

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

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

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

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

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

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

4　實驗結(jié)果與分析

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

4.1算法有效性測試

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

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

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

(b) 裁剪結(jié)果

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

4.1.2含有重點和重邊的多邊形裁剪測試

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

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

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

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

4.2算法效率測試

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

表1　Greiner-Hormann算法與改進算法的裁剪時間比較

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

5　結(jié)語

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

References)

[1]宋樹華, 濮國梁, 羅旭, 等. 簡單多邊形裁剪算法[J]. 計算機工程與設(shè)計, 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]. 軟件學報, 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]. 中國圖象圖形學報, 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]. 武漢大學學報(信息科學版), 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]彭杰, 劉南, 唐遠彬, 等. 一種基于交點排序的高效多邊形裁剪算法[J]. 浙江大學學報(理學版), 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]. 北京:科學出版社, 2013:88-110.

[10]閆浩文, 張黎明, 李茜茜, 等. 復(fù)合多邊形求差的高效矢量算法[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.

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

10.3969/j.issn.1001-0505.2016.04.005.

TP391

A

1001-0505(2016)04-0702-06

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