簡(jiǎn)單多邊形裁剪算法

宋樹(shù)華，濮國(guó)梁，羅 旭，陳 東，陳潤(rùn)強(qiáng)

（1.北京大學(xué) 遙感與地理信息系統(tǒng)研究所，北京100871；2.中國(guó)資源衛(wèi)星應(yīng)用中心，北京100094；3.中煤科技集團(tuán)公司，北京100013；4.北京應(yīng)用氣象研究所，北京100029）

0 引 言

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

針對(duì)這些問(wèn)題，本文提出了一個(gè)新的多邊形裁剪算法，裁剪多邊形和被裁剪多邊形都可以是一般多邊形，且不需要規(guī)定多邊形輸入方向。本算法采用矢量數(shù)組結(jié)構(gòu)，只需遍歷裁剪多邊形和被裁剪多邊形頂點(diǎn)即完成多邊形的裁剪，具有算法簡(jiǎn)單、運(yùn)行效率高的特點(diǎn)。

1 基本概念與定義

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

1.1 多邊形、頂點(diǎn)及邊

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

1.2 交點(diǎn)、前驅(qū)與后繼

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

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

2 算法的數(shù)據(jù)結(jié)構(gòu)

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

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

交點(diǎn)的前驅(qū)后繼數(shù)據(jù)結(jié)構(gòu)如下：

CrossPointIndex｛

int nPredecessorIndex＝0；／／前驅(qū)序號(hào)

int nSuccessorIndex＝0；／／后繼序號(hào)

｝

線段的數(shù)據(jù)結(jié)構(gòu)如下：

Segment｛

int nStartIndex＝0；／／頂點(diǎn)1序號(hào)

int nEndIndex＝0；／／頂點(diǎn)1序號(hào)

int＊pIndexes；

int nIndexCount；

｝

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

3 算法設(shè)計(jì)

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

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

步驟1 按正方向遍歷S與C并計(jì)算交點(diǎn)集Vector＜Vertex＞CrossPointSet，同時(shí)生成交點(diǎn)在S和C中前驅(qū)、后繼信息Vector＜CrossPointIndex＞ CrossPointIndexSetS和Vector＜CrossPointIndex＞CrossPointIndexSetC。其中，CrossPointSet中元素IsInPolygon的值為true。若Cross－PointSet元素為多邊形的頂點(diǎn)，如圖1（a）中I8與C中序號(hào)為7的點(diǎn)為同一點(diǎn)，則CrossPointIndexSetC中對(duì)應(yīng)的元素nPredecessorIndex與nSuccessorIndex的值相等，均C頂點(diǎn)的序號(hào)7。表1為交點(diǎn)在在S和C中前驅(qū)與后繼信息統(tǒng)計(jì)表。

表1 交點(diǎn)在S和C中前驅(qū)與后繼信息

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

表2 交點(diǎn)集合元素順序調(diào)整后的結(jié)果

步驟3 按倒序?qū)rossPointIndexSetS和CrossPoint－IndexSetC中的元素插入到S和C中，計(jì)算原多邊形頂點(diǎn)的序號(hào)信息，并建立交點(diǎn)在兩個(gè)多邊形中頂點(diǎn)序號(hào)對(duì)應(yīng)關(guān)系集合。

假設(shè)插入交點(diǎn)后的S和C成為S’和C’。插入同時(shí)，建立交點(diǎn)在S’和C’中頂點(diǎn)序號(hào)對(duì)應(yīng)集合Vector＜Cross－PointIndex＞CorrespondingCrossPointIndexSet，并用nPredecessorIndex記錄S’中頂點(diǎn)序號(hào)、nSuccessorIndex記錄C’中頂點(diǎn)序號(hào)。其中，以CrossPointIndexSetS和Cross－PointIndexSetC中前驅(qū)序號(hào)為0的元素開(kāi)始，交點(diǎn)序號(hào)在前驅(qū)序號(hào)的基礎(chǔ)上順序遞增。根據(jù)交點(diǎn)的前驅(qū)后繼集合信息，S和C頂點(diǎn)在S’和C’中的序號(hào)具有如下變化規(guī)律：

式中：nPredecessorIndex ［i］、nSuccessorIndex ［i］——S、C序號(hào)為i的頂點(diǎn)在S’和C’中的序號(hào)，ni——S和C中序號(hào)為i與i＋1之間的交點(diǎn)個(gè)數(shù)。表3是將圖1（b）中的交點(diǎn)插入到S和C后頂點(diǎn)序號(hào)變化統(tǒng)計(jì)表。其中，圖1（b）中括號(hào)前的數(shù)字表示交點(diǎn)插入前頂點(diǎn)序號(hào)，括號(hào)中的數(shù)字表示交點(diǎn)插入后的頂點(diǎn)序號(hào)。

表3 多邊形頂點(diǎn)序號(hào)變化

步驟4 釋放CrossPointIndexSetS和CrossPointIndex－SetC空間，修改交點(diǎn)對(duì)應(yīng)集合CorrespondingCrossPointIndexSet的元素值，見(jiàn)表4。

表4 交點(diǎn)對(duì)應(yīng)集合元素值

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

表5 多邊形線段集元素的頂點(diǎn)序號(hào)表

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

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

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

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

步驟8 遍歷SegmentSetS和SegmentSetC，利用CorrespondingCrossPointIndexSet交點(diǎn)在S’和C’的對(duì)應(yīng)關(guān)系，將S’和C’互為相鄰邊或相交的線段連接起來(lái)。若SegmentSetS中某元素和SegmentSetC中某元素的值相等或交叉相等，則表示為閉合多邊形。線段連接算法如下：

int i＝j(luò)＝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序號(hào)相等頂點(diǎn)的C’序號(hào)，用nStart和nEnd記錄與S’頂點(diǎn)相應(yīng)的C’頂點(diǎn)序號(hào)。此處，可以刪除滿足條件的CorrespondingCross PointIndexSet，減少下次循環(huán)的次數(shù)。

｝

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

｛

Segments seg2＝SegmentSetC［j］；

Segments seg3＝SegmentSetC［j＋1］；

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

｛

若線段seg1的起始節(jié)點(diǎn)與seg2的起始節(jié)點(diǎn)、seg1的終止節(jié)點(diǎn)與seg2的終止節(jié)點(diǎn)相等，表示線段seg1與seg2組成為一個(gè)相交多邊形，那么只需將seg2中的點(diǎn)倒序加入到seg1點(diǎn)的后面即可，即點(diǎn)的順序?yàn)椋簊eg1起始點(diǎn)－seg1中間點(diǎn) （順序）－seg1終止點(diǎn)－seg2中間點(diǎn) （倒序）。其中，括號(hào)中的順序是指按Segment中pIndexes元素序號(hào)從小到大的先后順序插入，括號(hào)中的倒序則是按pIndexes元素序號(hào)從大到小的順序插入。后面的意義相同。

｝

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

｛

若線段seg1的起始節(jié)點(diǎn)與seg2的終止節(jié)點(diǎn)、seg1的終止節(jié)點(diǎn)與seg2的起始節(jié)點(diǎn)相等，表示線段seg1與seg2組成為一個(gè)相交多邊形，那么只需將seg2中的點(diǎn)順序加入到seg1點(diǎn)的后面即可，即點(diǎn)的順序?yàn)椋簊eg1起始點(diǎn)－seg1中間點(diǎn) （順序）－seg1終止點(diǎn)－seg2中間點(diǎn) （順序）。

｝

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

｛

若線段seg1的起始節(jié)點(diǎn)與seg2的終止節(jié)點(diǎn)、seg1的終止節(jié)點(diǎn)與seg3的起始節(jié)點(diǎn)相等，表示線段seg2－seg1－seg3為相交多邊形的一部分，那么只需把線段seg1和seg3頂點(diǎn)和中間點(diǎn)追加到線段seg2后面即可，點(diǎn)的操作順序?yàn)椋簊eg1起始點(diǎn) （或seg2終止點(diǎn)）－seg1中間點(diǎn) （順序）－seg1終止點(diǎn) （或seg3起始點(diǎn)）－seg3中間點(diǎn) （順序）。同時(shí)，將seg3從SegmentSetC中刪除。

｝

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

｛

若線段seg1的起始節(jié)點(diǎn)與seg2的起始節(jié)點(diǎn)、seg1的終止節(jié)點(diǎn)與seg3的終止節(jié)點(diǎn)相等，表示線段seg3－seg1－seg2為相交多邊形的一部分，那么只需把線段seg1和seg2頂點(diǎn)和中間點(diǎn)追加到線段seg3后面即可，點(diǎn)的操作順序?yàn)椋簊eg1終止點(diǎn) （或seg3終止點(diǎn)）－seg1中間點(diǎn) （倒序）－seg1起始點(diǎn) （或seg2起始點(diǎn)）－seg2中間點(diǎn) （順序）。同時(shí)，將seg2從SegmentSetC中刪除。

｝

｝

算法結(jié)束，即可輸出結(jié)果多邊形。根據(jù)上述算法，結(jié)果多邊形形成的過(guò)程見(jiàn)表8。

表8 結(jié)果多邊形形成的過(guò)程

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

4 算法分析

下面從空間復(fù)雜性和時(shí)間復(fù)雜性上對(duì)算法進(jìn)行分析。

首先對(duì)空間復(fù)雜性分析。假設(shè)S和C的頂點(diǎn)數(shù)分別為n和m（m＞n），交點(diǎn)數(shù)為k。根據(jù)文獻(xiàn) ［10］所述，文獻(xiàn)［10］中算法需要5（n＋m）＋6k個(gè)存儲(chǔ)單元，Vatti算法和Greiner－Hormann算法占9（n＋m＋2k）個(gè)存儲(chǔ)單元。

對(duì)于本文的算法，每個(gè)頂點(diǎn)和交點(diǎn)只占用3個(gè)存儲(chǔ)單元，交點(diǎn)前驅(qū)后繼數(shù)據(jù)結(jié)構(gòu)占2個(gè)存儲(chǔ)單元，弧段占用4個(gè)存儲(chǔ)單元。由于交點(diǎn)前驅(qū)后繼數(shù)據(jù)結(jié)構(gòu)在對(duì)每個(gè)多邊形都記錄一次，因此一個(gè)交點(diǎn)的前驅(qū)后繼占用4個(gè)存儲(chǔ)單元；在申請(qǐng)弧段結(jié)構(gòu)時(shí)，前驅(qū)后繼結(jié)構(gòu)是不同時(shí)存在的，那么在整個(gè)算法實(shí)現(xiàn)過(guò)程中，交點(diǎn)前驅(qū)后繼信息和弧段信息始終為4個(gè)存儲(chǔ)單元。因此，本算法總的存儲(chǔ)單位為

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

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

5 結(jié)束語(yǔ)

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

［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，F(xiàn)einer 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］.測(cè)繪科學(xué)，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）.［劉勇奎，高云，黃有群.一個(gè)有效的多邊形裁剪算法 ［J］.軟件學(xué)報(bào)，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）.［彭杰，劉南，唐遠(yuǎn)彬，等.一種基于交點(diǎn)排序的高效多邊形裁剪算法 ［J］.浙江大學(xué)學(xué)報(bào) （理學(xué)版），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）.［趙紅波，張涵.一種等值線圖的任意復(fù)雜多邊形窗口裁剪算法 ［J］.計(jì)算機(jī)工程與應(yīng)用，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）.［周清平，陳學(xué)工.大規(guī)模等值線圖任意多邊形裁剪算法 ［J］.計(jì)算機(jī)與現(xiàn)代化，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）.［陳占龍，吳亮，劉煥煥.基于排序邊表的簡(jiǎn)單要素模型多邊形裁剪算法 ［J］.微電子學(xué)與計(jì)算機(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）.［劉雪娜，侯寶明.復(fù)雜多邊形窗口的多邊形裁剪的改進(jìn)算法 ［J］.計(jì)算機(jī)與現(xiàn)代化，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）.［王結(jié)臣，沈定濤，陳焱明，等.一種有效的復(fù)雜多邊形裁剪算法 ［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），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）.［江平，劉民士.射線法判斷點(diǎn)與包含簡(jiǎn)單曲線多邊形 關(guān)系 的完善 ［J］.測(cè) 繪科學(xué)，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）.［劉民士，王春.射線法判斷點(diǎn)與多邊形內(nèi)外關(guān)系的改進(jìn)算法 ［J］.滁州學(xué)院學(xué)報(bào)，2010，12 （2）：14－16.］