簡單多邊形裁剪算法

宋樹華，濮國梁，羅 旭，陳 東，陳潤強

（1.北京大學 遙感與地理信息系統研究所，北京100871；2.中國資源衛星應用中心，北京100094；3.中煤科技集團公司，北京100013；4.北京應用氣象研究所，北京100029）

0 引 言

在多邊形裁剪算法中，根據裁剪處理的對象不同，裁剪可分為線段裁剪和多邊形裁剪。多邊形裁剪較線段裁剪具有更高的使用頻率，且多邊形越復雜，多邊形裁剪算法的難度也越大。經典的多邊形裁剪算法，如Sutherland－Hodgeman［1］、 梁－Barsky［2］、 Foley［3］、 Maillot［4］、 Andereev［5］等算法要求裁剪多邊形是矩形，羅畏［6］提出的算法則要求裁剪多邊形是圓形，而一般多邊形裁剪更加實用。Weiler算法［7］、Vatti算法［8］以及 greiner－Hormann算法［9］、劉永奎［10］和彭杰［11］提出的多邊形裁剪算法可對處理一般多邊形。同時，趙紅波［12］和周清平［13］對等值線圖的任意多邊形窗口裁剪進行研究，陳占龍［14］采用基于要素模型實現多邊形裁剪，劉雪娜［15］、王結臣［16］對復雜多邊形裁剪進行了探討。其中，Weiler算法采用樹形數據結構，Vatti和greiner－Hormann算法采用雙線性鏈表數據結構，劉永奎、周清平、陳占龍和劉雪娜等的裁剪算法采用單線性鏈表，彭杰、趙紅波和王結臣等的裁剪算法則采用單鏈表、單指針的數據結構。雖然后兩種在復雜性上優于前幾種算法，但必須判斷多邊形頂點的順時針和逆時針性，增加了多邊形裁剪算法的難度。

針對這些問題，本文提出了一個新的多邊形裁剪算法，裁剪多邊形和被裁剪多邊形都可以是一般多邊形，且不需要規定多邊形輸入方向。本算法采用矢量數組結構，只需遍歷裁剪多邊形和被裁剪多邊形頂點即完成多邊形的裁剪，具有算法簡單、運行效率高的特點。

1 基本概念與定義

為了便于下文對算法的描述，本節將介紹多邊形裁剪中涉及的一些概念。

1.1 多邊形、頂點及邊

由平面上閉合多線段S：｛E0，E1，…，En－1｝（n≥3）稱為多邊形，其中連接相鄰頂點的線段n－1）稱為S的邊，Pi為頂點。Ei－1，Ei稱作Pi的鄰邊，并規定i的增序方向為S的正方向，否則為反方向。若多邊形中不相鄰的邊不相交，則稱該多邊形為簡單多邊形。

1.2 交點、前驅與后繼

對于S，若沿著S正方向，則Pi為I在S中的前驅（predecessor），Pi＋1為I在S中的后繼 （successor）；若沿著S反方向，則Pi＋1為I在S中的前驅，Pi為I在S中的后繼。同理，對于C，若沿著C正方向，則Pj為I在C中的前驅，Pj＋1為I在S中的后繼；若沿著C反方向，則Pj＋1為I在S中的前驅，Pj為I在S中的后繼。若Ei與Ej交點I為Pj，則在C中，I的前驅和后繼均為Pj，如圖1（a）中的I8點。

圖1 裁剪多邊形S和被裁剪多邊形C

2 算法的數據結構

多邊形裁剪算法的核心是數據結構，它決定了算法的復雜度和計算效率。目前，多邊形裁剪常用數據結構為線性鏈表結構、雙向鏈表結構和樹形結構。在算法的復雜性上，線性鏈表最簡單，樹形結構最復雜。同時，線性鏈表比雙向鏈表少一個指針域而節省了存儲空間，但指針依然占用空間。因此，兼顧數據結構簡單和節省存儲空間的目的，本文提出了基于矢量數組vector的數據結構。多邊形矢量數組的每個元素表示多邊形頂點，且按頂點輸入的順序存儲。頂點或交點的數據結構如下：

Vertex＝ ｛double x，y；bool IsInPolygon；｝

交點的前驅后繼數據結構如下：

CrossPointIndex｛

int nPredecessorIndex＝0；／／前驅序號

int nSuccessorIndex＝0；／／后繼序號

｝

線段的數據結構如下：

Segment｛

int nStartIndex＝0；／／頂點1序號

int nEndIndex＝0；／／頂點1序號

int＊pIndexes；

int nIndexCount；

｝

Vertex用來存儲多邊形的頂點或交點，x，y表示頂點的坐標，IsInPolygon為true表示該點在多邊形內部或在多邊形的邊上，否則，表示該點在多邊形外部。CrossPointIndex用于記錄交點在多邊形中的前驅與后繼的序號信息，以及記錄同一交點在兩個多邊形中頂點序號。即若P為多邊形S與多邊形C的交點，為了表示P在S和C中為同一點，則可用CrossPointIndex記錄用nPredecessorIndex記錄P在S中的序號、用nSuccessorIndex記錄P在C中序號。Segment表示多邊形在另一個多邊形內 （外）的線段，nStartIndex為Segment起始頂點的序號，nEndIndex為Segment終止頂點的序號，pIndexes為起始頂點與終止頂點之間的頂點序號集合，nIndexCount為pIndexes中元素個數。

3 算法設計

多邊形裁剪算法分為3個階段。第1個階段，采用射線法［17，18］計算并判斷S （或C）在C （或S）內，并修改S（或C）頂點Vertex的IsInPolygon的值。第2個階段，按正方向遍歷S與C，計算S與C的交點集，交點的前驅后繼信息、交點在S和C中對應關系，以及相交多邊形弧段集。此階段是本算法的核心部分。第3個階段，對弧段集進行合并，生成并輸出結果多邊形。

第1個階段文獻 ［17，18］討論的很充分，這里就不再贅述了。下面從第2個階段開始介紹，以圖1為例，具體步驟如下。

步驟1 按正方向遍歷S與C并計算交點集Vector＜Vertex＞CrossPointSet，同時生成交點在S和C中前驅、后繼信息Vector＜CrossPointIndex＞ CrossPointIndexSetS和Vector＜CrossPointIndex＞CrossPointIndexSetC。其中，CrossPointSet中元素IsInPolygon的值為true。若Cross－PointSet元素為多邊形的頂點，如圖1（a）中I8與C中序號為7的點為同一點，則CrossPointIndexSetC中對應的元素nPredecessorIndex與nSuccessorIndex的值相等，均C頂點的序號7。表1為交點在在S和C中前驅與后繼信息統計表。

表1 交點在S和C中前驅與后繼信息

步驟2 判斷CrossPointIndexSetS或CrossPointIndex－SetC中首尾元素的nPredecessorIndex與nSuccessorIndex值是否相等。若相等，則將尾部元素放置到首部位置。重復判斷操作，直到首尾元素值不相等為止。表2為表1調整后的結果。

表2 交點集合元素順序調整后的結果

步驟3 按倒序將CrossPointIndexSetS和CrossPoint－IndexSetC中的元素插入到S和C中，計算原多邊形頂點的序號信息，并建立交點在兩個多邊形中頂點序號對應關系集合。

假設插入交點后的S和C成為S’和C’。插入同時，建立交點在S’和C’中頂點序號對應集合Vector＜Cross－PointIndex＞CorrespondingCrossPointIndexSet，并用nPredecessorIndex記錄S’中頂點序號、nSuccessorIndex記錄C’中頂點序號。其中，以CrossPointIndexSetS和Cross－PointIndexSetC中前驅序號為0的元素開始，交點序號在前驅序號的基礎上順序遞增。根據交點的前驅后繼集合信息，S和C頂點在S’和C’中的序號具有如下變化規律：

式中：nPredecessorIndex ［i］、nSuccessorIndex ［i］——S、C序號為i的頂點在S’和C’中的序號，ni——S和C中序號為i與i＋1之間的交點個數。表3是將圖1（b）中的交點插入到S和C后頂點序號變化統計表。其中，圖1（b）中括號前的數字表示交點插入前頂點序號，括號中的數字表示交點插入后的頂點序號。

表3 多邊形頂點序號變化

步驟4 釋放CrossPointIndexSetS和CrossPointIndex－SetC空間，修改交點對應集合CorrespondingCrossPointIndexSet的元素值，見表4。

表4 交點對應集合元素值

步驟5 按正方向分別連接S’和C’中Vertex的IsInPolygon為true且相鄰的頂點，生成線段集Vector＜Segment＞SegmentSetS和 Vector＜Segment＞ Segment－SetC，見表5。

表5 多邊形線段集元素的頂點序號表

步驟6 遍歷SegmentSetS元素并取第i號元素的中點Pi，采用射線法判斷Pi是否在C中，若不在C中，則刪除SegmentSetS中第i號元素。同理，刪除SegmentSetC中元素的中點不在S’中的項。表6為SegmentSetS和Segment－SetC按照步驟6操作后的結果。

表6 線段集合刪除在多邊形外元素后的結果

步驟7 分別合并SegmentSetS和SegmentSetC中為相鄰邊的元素。表7是表6線段合并后的結果。

表7 S’和C’的線段合并后的集合

步驟8 遍歷SegmentSetS和SegmentSetC，利用CorrespondingCrossPointIndexSet交點在S’和C’的對應關系，將S’和C’互為相鄰邊或相交的線段連接起來。若SegmentSetS中某元素和SegmentSetC中某元素的值相等或交叉相等，則表示為閉合多邊形。線段連接算法如下：

int i＝j＝0；

while（i＜SegmentSetS.Size（））

｛

Segment seg1＝ SegmentSetS［i＋＋］；

int nStart＝seg1.nStartIndex；

int nEnd＝seg1.nEndIndex；

for（j＝0；j＜CorrespondingCrossPointIndexSet.Size（）；j＋＋）

｛

遍歷CorrespondingCrossPointIndexSet，得到與S’的nStart、nEnd序號相等頂點的C’序號，用nStart和nEnd記錄與S’頂點相應的C’頂點序號。此處，可以刪除滿足條件的CorrespondingCross PointIndexSet，減少下次循環的次數。

｝

for（j＝0；j＜ Polygon2segments.Count；j＋＋）

｛

Segments seg2＝SegmentSetC［j］；

Segments seg3＝SegmentSetC［j＋1］；

if （（nStart＝ ＝ seg2.nStartIndex ＆ nEnd＝ ＝seg2.nEndIndex））

｛

若線段seg1的起始節點與seg2的起始節點、seg1的終止節點與seg2的終止節點相等，表示線段seg1與seg2組成為一個相交多邊形，那么只需將seg2中的點倒序加入到seg1點的后面即可，即點的順序為：seg1起始點－seg1中間點 （順序）－seg1終止點－seg2中間點 （倒序）。其中，括號中的順序是指按Segment中pIndexes元素序號從小到大的先后順序插入，括號中的倒序則是按pIndexes元素序號從大到小的順序插入。后面的意義相同。

｝

else if （（nStart＝ ＝ seg2.nEndIndex ＆ nEnd ＝＝seg2.nStartIndex））

｛

若線段seg1的起始節點與seg2的終止節點、seg1的終止節點與seg2的起始節點相等，表示線段seg1與seg2組成為一個相交多邊形，那么只需將seg2中的點順序加入到seg1點的后面即可，即點的順序為：seg1起始點－seg1中間點 （順序）－seg1終止點－seg2中間點 （順序）。

｝

else if （（nStart＝ ＝ seg2.nEndIndex ＆ nEnd ＝＝seg3.nStartIndex））

｛

若線段seg1的起始節點與seg2的終止節點、seg1的終止節點與seg3的起始節點相等，表示線段seg2－seg1－seg3為相交多邊形的一部分，那么只需把線段seg1和seg3頂點和中間點追加到線段seg2后面即可，點的操作順序為：seg1起始點 （或seg2終止點）－seg1中間點 （順序）－seg1終止點 （或seg3起始點）－seg3中間點 （順序）。同時，將seg3從SegmentSetC中刪除。

｝

else if （（nStart＝＝ seg2.nStartIndex ＆ nEnd ＝＝seg3.nEndIndex））

｛

若線段seg1的起始節點與seg2的起始節點、seg1的終止節點與seg3的終止節點相等，表示線段seg3－seg1－seg2為相交多邊形的一部分，那么只需把線段seg1和seg2頂點和中間點追加到線段seg3后面即可，點的操作順序為：seg1終止點 （或seg3終止點）－seg1中間點 （倒序）－seg1起始點 （或seg2起始點）－seg2中間點 （順序）。同時，將seg2從SegmentSetC中刪除。

｝

｝

算法結束，即可輸出結果多邊形。根據上述算法，結果多邊形形成的過程見表8。

表8 結果多邊形形成的過程

該算法不僅可以求多邊形的 “交” （多變形的裁剪），而且也可以求多邊形的 “并”和 “差”。例如，在求多邊形的 “并”時，只需將交點與被裁減多邊形和裁剪多邊形的外點 （IsInPolygon為false）連接，即為結果多邊形；而對于多邊形的 “差”，只需將交點與被裁減多邊形外點 （IsIn－Polygon為false）連接，即可結果多邊形。

4 算法分析

下面從空間復雜性和時間復雜性上對算法進行分析。

首先對空間復雜性分析。假設S和C的頂點數分別為n和m（m＞n），交點數為k。根據文獻 ［10］所述，文獻［10］中算法需要5（n＋m）＋6k個存儲單元，Vatti算法和Greiner－Hormann算法占9（n＋m＋2k）個存儲單元。

對于本文的算法，每個頂點和交點只占用3個存儲單元，交點前驅后繼數據結構占2個存儲單元，弧段占用4個存儲單元。由于交點前驅后繼數據結構在對每個多邊形都記錄一次，因此一個交點的前驅后繼占用4個存儲單元；在申請弧段結構時，前驅后繼結構是不同時存在的，那么在整個算法實現過程中，交點前驅后繼信息和弧段信息始終為4個存儲單元。因此，本算法總的存儲單位為

因此，本算法中的頂點占用的空間比文獻 ［10］的頂點所占用的空間將盡少一半，交點占用存儲空間比文獻［10］算法多k個單元。而相對于 Vatti算法和Greiner－Hormann算法，則節約6（n＋m）＋11k個存儲單元，幾乎少用了2／3的存儲空間。

其次，時間復雜度分析。第1階段生成交點以及點是否在多邊形內，遍歷多邊形1次，其時間復雜度為o（m×n）；第2階段步驟1，判斷多邊形交點對應關系，遍歷交點前驅后繼集1次，時間復雜度為o（k×k）；步驟6判斷線段集合元素的有效性，遍歷線段集合和多邊形1遍，其中線段集合元素最多不超過k、多邊形邊數不超過 （m＋k），因此最壞情況下的時間復雜度為o（（m＋k）×k）；步驟7和步驟8，分別是線段合并和線段連接，遍歷線段集合1遍，由于線段集合、頂點對應集合的元素的個數均不超過k，所以最壞情況的時間復雜度為o（k×k）。因此，本算法的時間復雜度為o（（m＋k）×k）。

5 結束語

本文綜合考慮現有多邊形裁剪算法的優缺點，提出了一種基于多邊形頂點遍歷的簡單多邊形裁剪算法。本算法通過采用矢量數組結構、遍歷多邊形頂點并記錄裁剪多邊形和被裁減多邊形交點及其前驅、后繼信息，而無需考慮輸入多邊形的方向、形狀等，即可很好地處理多邊形邊重合、邊頂點相交等特殊的情況，實現多邊形裁剪。結果表明，本算法具有算法簡單、易于實現、運行效率高的特點。

［1］Sutherland I E，Hodgeman G W.Reentrant polygon clipping［J］.Communications of the ACM，1974，17 （1）：32－42.

［2］Liang Y，Barsky B A.An analysis and algorithm for polygon clipping ［J］.Communications of the ACM，1983，26 （11）：868－877.

［3］Foley J D，Dam A，Feiner S K，et al.Computer graphics，principles and practice［M］.MA：Addison－Wesley，1990.

［4］Maillot P G.A new，fast method for 2Dpolygon clipping：Analysis and software implementation ［J］.ACM Transactions on Graphics，1992，11 （3）：276－290.

［5］Andereev R D.Algorithm for clipping arbitrary polygons ［J］.Computer Graphics Forum，1989，8 （2）：183－191.

［6］LUO Wei，ZOU Zhengrong.An algorithm of polygon clipping against a circular window ［J］.Science of Surveying and Mapping，2011，36 （3）：234－235 （in Chinese）.［羅畏，鄒崢嶸.一種基于圓形窗口的多邊形裁剪新算法 ［J］.測繪科學，2011，36 （3）：234－235.］

［7］Weiler K，Atherton P.Hidden surface removal using polygon area sorting ［C］／／Proceedings of the SIGGRAPH.New York：ACM Press，1977：214－222.

［8］Vatti B R.A generic solution to polygon clipping ［J］.Communications of the ACM，1992，35 （1）：56－63.

［9］Greiner G，Hormann K.Efficient clipping of arbitrary polygons［J］.ACM Transactions on Graphics，1998，17 （2）：71－83.

［10］LIU Yongkui，GAO Yun，HUANG Youqun.An efficient algorithm for polygon clipping ［J］.Journal of Software，2003，14 （4）：845－856 （in Chinese）.［劉勇奎，高云，黃有群.一個有效的多邊形裁剪算法 ［J］.軟件學報，2003，14（4）：845－856.］

［11］PENG Jie，LIU Nan，TANG Yuanbin，et al.An efficient algorithm for polygon clipping based on intersection points sorting ［J］.Journal of Zhejiang University （Science Edition），2012，39 （1）：107－111 （in Chinese）.［彭杰，劉南，唐遠彬，等.一種基于交點排序的高效多邊形裁剪算法 ［J］.浙江大學學報 （理學版），2012，39 （1）：107－111.］

［12］ZHAO Hongbo，ZHANG Han.Algorithm for contour clipping against general polygon window ［J］.Computer Engineering and Applications，2012，48 （32）：170－175 （in Chinese）.［趙紅波，張涵.一種等值線圖的任意復雜多邊形窗口裁剪算法 ［J］.計算機工程與應用，2012，48 （32）：170－175.］

［13］ZHOU Qingping，CHEN Xuegong.Algorithm for contour clipping against general polygon ［J］.Computer and Modernization，2012 （4）：196－200 （in Chinese）.［周清平，陳學工.大規模等值線圖任意多邊形裁剪算法 ［J］.計算機與現代化，2012 （4）：196－200.］

［14］CHEN Zhanlong，WU Liang，LIU Huanhuan.Simple feature model polygon clipper algorithm base on sorting edges table ［J］.Microelectronics ＆ Computer，2012，29 （9）：145－148（in Chinese）.［陳占龍，吳亮，劉煥煥.基于排序邊表的簡單要素模型多邊形裁剪算法 ［J］.微電子學與計算機，2012，29 （9）：145－148.］

［15］LIU Xuena，HOU Baoming.An improved algorithm for polygon clipping in complex polygon window ［J］.Computer and Modernization，2009 （11）：36－38 （in Chinese）.［劉雪娜，侯寶明.復雜多邊形窗口的多邊形裁剪的改進算法 ［J］.計算機與現代化，2009 （11）：36－38.］

［16］WANG Jiechen，SHEN Dingtao，CHEN Yanming，et al.An efficient algorithm for complex polygon clipping ［J］.Geomatics and Information Science of Wuhan University，2010，53 （3）：369－372 （in Chinese）.［王結臣，沈定濤，陳焱明，等.一種有效的復雜多邊形裁剪算法 ［J］.武漢大學學報（信息科學版），2010，53 （3）：369－372.］

［17］JIANG Ping，LIU Minshi.Improved ray method to judge the relation of point and polygon including simple curve ［J］.Science of Surveying and Mapping，2009，34 （5）：220－222（in Chinese）.［江平，劉民士.射線法判斷點與包含簡單曲線多邊形 關系 的完善 ［J］.測 繪科學，2009，34 （5）：220－222.］

［18］LIU Minshi，WANG Chun.The improved algorithm to determine the inside and outside relationships between point and polygon by ray method ［J］.Journal of Chuzhou University，2010，12 （2）：14－16 （in Chinese）.［劉民士，王春.射線法判斷點與多邊形內外關系的改進算法 ［J］.滁州學院學報，2010，12 （2）：14－16.］