1、第35卷第3期2010年3月武漢大學(xué)學(xué)報(bào)信息科學(xué)版 收稿日期:2009201223。項(xiàng)目來(lái)源:國(guó)家基礎(chǔ)科學(xué)人才培養(yǎng)基金資助項(xiàng)目(J 0630535。一種有效的復(fù)雜多邊形裁剪算法王結(jié)臣1沈定濤1陳焱明1李利番1(1南京大學(xué)地理信息科學(xué)系,南京市漢口路22號(hào),210093摘要:提出了一種基于掃描線思想和梯形分割技術(shù)的多邊形裁剪算法,其主要步驟包括:計(jì)算主多邊形(集與窗口多邊形(集的交點(diǎn),提取所有交點(diǎn)和多邊形邊界結(jié)點(diǎn)的縱坐標(biāo)(y 并進(jìn)行排序;以排序后的y 作水平掃描線,分別對(duì)主多邊形和窗口多邊形進(jìn)行梯形分割,獲得兩組梯形集合;對(duì)這兩組梯形集合逐行執(zhí)行梯形單元“交”運(yùn)算,最后對(duì)結(jié)果交集進(jìn)行邊界追蹤建立

2、裁剪多邊形。實(shí)驗(yàn)結(jié)果表明,該算法具有較好的計(jì)算效率,是一種比較實(shí)用的多邊形裁剪算法。關(guān)鍵詞:多邊形裁剪;算法;地理信息系統(tǒng)中圖法分類號(hào):P208多邊形裁剪廣泛應(yīng)用于GIS 、計(jì)算機(jī)圖形學(xué)等領(lǐng)域,其目的是提取出裁剪多邊形之間重合的區(qū)域。其中,較常見(jiàn)和簡(jiǎn)單的應(yīng)用是矩形窗口裁剪,它是不規(guī)則多邊形裁剪的特殊形式,目前已發(fā)展了一些較成熟的算法125;而不規(guī)則多邊形裁剪,由于相對(duì)復(fù)雜且更具一般性,其算法設(shè)計(jì)與優(yōu)化也更受關(guān)注。由于任意多邊形的形態(tài)復(fù)雜性,不難想象,直接基于原始多邊形單元設(shè)計(jì)的裁剪算法亦較為復(fù)雜。因此,本文設(shè)想將復(fù)雜多邊形劃分為形態(tài)簡(jiǎn)單的空間單元,在實(shí)現(xiàn)簡(jiǎn)單空間單元裁剪的基礎(chǔ)上,將計(jì)算結(jié)果“拼

3、貼”起來(lái)獲得完整結(jié)果。本文同時(shí)借鑒了計(jì)算幾何中的掃描線概念,在此基礎(chǔ)上設(shè)計(jì)了一種基于梯形分割技術(shù)的多邊形裁剪算法。1算法原理為便于描述,本文約定,被裁剪的多邊形稱為主多邊形,作為“剪刀”的多邊形稱為窗口多邊形。柵格法是實(shí)現(xiàn)多邊形裁剪的較簡(jiǎn)單的方法之一,盡管其計(jì)算精度受到限制,但柵格法的思想仍可借鑒,它將多邊形分解為簡(jiǎn)單幾何單元(規(guī)則柵格,以這些“基元”為空間運(yùn)算對(duì)象來(lái)設(shè)計(jì)算法。借鑒柵格法的思路,同時(shí)為克服規(guī)則柵格導(dǎo)致的精度不高的缺點(diǎn),本文設(shè)想將復(fù)雜多邊形分解為不規(guī)則的梯形單元。如圖1所示,兩個(gè)多邊形部分重疊,裁剪后要輸出代表重疊區(qū)域的多邊形。借鑒計(jì)算幾何中的掃描線思想,將兩個(gè)多邊形事先進(jìn)行梯形

4、分解,并將這種分解限制在統(tǒng)一的掃描行內(nèi),然后逐行進(jìn)行梯形單元的裁剪,在各行上獲得裁剪結(jié)果(梯形,最后將各行的結(jié)果拼裝起來(lái),即可實(shí)現(xiàn)復(fù)雜多邊形的裁剪。圖1算法原理示意圖Fig.1Diagram of Algorithm Principle條帶劃分是多邊形梯形分解和裁剪的基礎(chǔ)。對(duì)于單個(gè)多邊形圖層的梯形分解,在劃分條帶時(shí)相對(duì)簡(jiǎn)單,僅需根據(jù)全部多邊形頂點(diǎn)縱坐標(biāo)y 繪制水平掃描線,多邊形頂點(diǎn)均位于掃描線上。由于多邊形裁剪中涉及到兩個(gè)多邊形圖層,為保證所劃分的條帶不相互跨越,需事先計(jì)算兩個(gè)圖層的交點(diǎn),將交點(diǎn)視同多邊形頂點(diǎn),同樣地繪制掃描線。利用這些掃描線不難將主多邊形和窗口多邊 武漢大學(xué)學(xué)報(bào)信息科學(xué)版20

5、10年3月形分割為兩個(gè)梯形集合。從縱軸方向看,空間被分割成一條條掃描帶,由多邊形分割成的梯形按其縱坐標(biāo)位置“鑲嵌”在這些掃描帶上。任何一個(gè)梯形都只能被限制在一條掃描帶中,不會(huì)跨越多條掃描帶。若主多邊形與窗口多邊形有重疊區(qū)域,則在某些掃描帶上,主多邊形生成的梯形與窗口多邊形生成的梯形也會(huì)部分重疊。多邊形裁剪運(yùn)算實(shí)際上就是逐行地檢索和計(jì)算梯形間的重疊區(qū)域,或者說(shuō),檢索兩類梯形的“交集”,其結(jié)果是分布在各掃描帶上的“交梯形”的集合。本文設(shè)計(jì)的多邊形裁剪算法,其計(jì)算步驟為:計(jì)算兩個(gè)多邊形圖層的交點(diǎn);針對(duì)全部多邊形頂點(diǎn)和圖層交點(diǎn),對(duì)其縱坐標(biāo)y進(jìn)行排序,得到一個(gè)代表掃描線序列的數(shù)組y1,y2,y n;根據(jù)

6、數(shù)組y1,y2,y n建立水平掃描線,將主多邊形層和窗口多邊形層分別進(jìn)行梯形分割,得到兩個(gè)梯形集合;在各掃描帶上建立“交梯形”的集合;在“交梯形”集合的基礎(chǔ)上通過(guò)邊界追蹤等方法構(gòu)建裁剪多邊形并輸出計(jì)算結(jié)果。2算法的關(guān)鍵過(guò)程2.1計(jì)算兩個(gè)圖層的交點(diǎn)計(jì)算交點(diǎn)是為了能在交點(diǎn)處也建立水平掃描線,從而在后續(xù)多邊形梯形化時(shí)可以將主多邊形和窗口多邊形生成的梯形集控制在統(tǒng)一的掃描帶空間上。聯(lián)想到本文借助掃描線思想實(shí)現(xiàn)多邊形的梯形分割,同樣也可采用這一思想完成多邊形間的線段求交,思路為:分配一個(gè)坐標(biāo)數(shù)組,記錄主多邊形與窗口多邊形上所有結(jié)點(diǎn)的縱坐標(biāo)值,并對(duì)該數(shù)組排序;以數(shù)組中每一個(gè)元素值作水平掃描線,分別將主多邊

7、形和窗口多邊形的邊打斷成小線段,得到兩組線段集合;遍歷掃描帶,在各掃描帶上用窗口多邊形生成的小線段與主多邊形生成的小線段兩兩判斷是否相交,若有交點(diǎn),則求出交點(diǎn)坐標(biāo)。如圖2所示,將主多邊形與窗口多邊形的邊分別打斷成小線段后,在第4條掃描帶上拿窗口多邊形生成的線段A、B分別與主多邊形邊生成的線段1、2作相交判斷,可以得出線段B與線段2相交。2.2多邊形梯形化在多邊形裁剪中,為正確提取出裁剪多邊形,必須對(duì)多邊形完成全梯形化。在多邊形各個(gè)結(jié)點(diǎn)處作水平掃描線是為了將多邊形的邊打斷成小線段,該步驟與多邊形求交算法思路中的前兩步相同。完成上述步驟后, 對(duì)各個(gè)掃描帶上的小線段圖2交點(diǎn)計(jì)算Fig.2Points

8、 of Intersection Calculation從左至右兩個(gè)為一組提取并作為梯形斜邊構(gòu)造梯形。可以證明,無(wú)論多邊形形態(tài)如何復(fù)雜,位于每個(gè)掃描帶上的小線段個(gè)數(shù)必為偶數(shù),且是梯形個(gè)數(shù)的兩倍。如圖3所示,該復(fù)雜多邊形(深色表示包含3個(gè)洞,且其中一個(gè)洞還有島存在,圖中所標(biāo)記的掃描帶上共有10條小線段,正好構(gòu)成5個(gè)梯形,梯形的這種良好特性使得復(fù)雜多邊形間的精確裁剪成為可能。需要指出的是,在多邊形邊的極值點(diǎn)處(該點(diǎn)的縱坐標(biāo)同時(shí)大于或小于多邊形邊界點(diǎn)坐標(biāo)序列中上一點(diǎn)和下一點(diǎn)縱坐標(biāo),多邊形分割成的梯形將退化為三角形,而三角形也可以看成是一種有兩個(gè)點(diǎn)重合的特殊梯形 。圖3帶洞島的復(fù)雜多邊形梯形化Fig.

9、3Trapezium2Split Operation2.3掃描帶內(nèi)的梯形求交算法設(shè)計(jì)中,可以用一個(gè)結(jié)構(gòu)體來(lái)表示梯形單元,結(jié)構(gòu)體中記錄了梯形的4個(gè)頂點(diǎn)坐標(biāo),在每個(gè)掃描帶上用一個(gè)有序鏈表來(lái)存儲(chǔ)該帶上所生成的梯形。在將主多邊形集和窗口多邊形集分別梯形化之后,每條掃描帶上將產(chǎn)生兩個(gè)有序鏈表,因此,只要對(duì)比兩條有序鏈表,找出鏈表之間梯形的交集便可以完成該掃描帶上梯形的求交運(yùn)算。鏈表在執(zhí)行插入和刪除結(jié)點(diǎn)操作時(shí)具有很好的靈活性,可以在每個(gè)掃描帶上固定主多邊形的鏈表(為便于描述,將該鏈表定義為參照鏈表,拿窗口多邊形所在鏈表中的梯形逐個(gè)與參照鏈表的梯形集作比較,判斷是否有梯形相交的情形出現(xiàn)。將上述過(guò)程稱為梯形與

10、參照鏈表的“插入”操作,若待“插入”梯形與鏈表中的梯形不相交,舍棄該操作,否則對(duì)參照鏈表中的梯形執(zhí)行“分裂”運(yùn)算,073 第35卷第3期王結(jié)臣等:一種有效的復(fù)雜多邊形裁剪算法并對(duì)“交梯形”進(jìn)行標(biāo)記。如圖4所示,參照鏈表中的灰色部分表示梯形單元,當(dāng)梯形與參照鏈表完成“插入”操作后,該鏈表中將具有8個(gè)梯形單元,其中黑色部分表示“交梯形”,即主多邊形所在梯形與窗口多邊形所在梯形的“交集”。 圖4梯形單元的分裂Fig.4Split of Trapezium在梯形的“插入”操作中,關(guān)鍵是要判斷出該梯形在參照鏈表中的位置。在算法初期已完成多邊形線段求交運(yùn)算,待“插入”梯形與參照鏈表中梯形之間不會(huì)出現(xiàn)斜邊交

11、叉的情況,梯形位置的判斷將變得容易。具體判斷方法為:計(jì)算梯形兩條斜邊中點(diǎn)的橫坐標(biāo)值x ,參照鏈表中每個(gè)梯形兩斜邊的x 按照從左至右的方式構(gòu)成一個(gè)有序坐標(biāo)序列;通過(guò)折半查找求出待“插入”梯形兩斜邊中點(diǎn)橫坐標(biāo)x 在坐標(biāo)序列中的位置,從而推斷出待“插入”梯形兩斜邊位于參照鏈表中的位置并找出該梯形與鏈表中哪些梯形相交。2.4梯形單元提取與面的構(gòu)建完成掃描帶上梯形求交運(yùn)算后,各帶參照鏈表中“交梯形”已生成并被標(biāo)記。可遍歷掃描帶上的參照鏈表,刪除鏈表中未被標(biāo)記的梯形,最后保留“交梯形”集合。“交梯形”相互拼接生成的多邊形集就是裁剪結(jié)果,需要建立專門(mén)的邊界追蹤算法完成面的構(gòu)建。將面狀多邊形數(shù)據(jù)在空間上劃分為

12、更小的幾何單元,并建立相應(yīng)的邊界追蹤算法。借鑒前人思想,可以將梯形看作一種特殊的矩形,在沿著梯形邊界追蹤時(shí)追蹤方向可以以左上、左下、右上和右下標(biāo)記。圖5顯示了一個(gè)帶洞的多邊形,當(dāng)追蹤到梯形的左斜邊時(shí)追蹤方向?yàn)樽笊匣蜃笙?追蹤到梯形的右斜邊時(shí),追蹤方向?yàn)橛疑匣蛘哂蚁隆Ｒ话闱樾蜗?在追蹤到梯形的某一斜邊時(shí),該梯形所在掃描帶的上一行和下一行掃描帶中必能找到兩個(gè)梯形,且這兩個(gè)梯形的斜邊與當(dāng)前追蹤梯形的斜邊正好相接,從而,沿追蹤方向很容易找到下一追蹤梯形。顯然,只有在多邊形的極值點(diǎn)處其追蹤方向才會(huì)發(fā)生改變,此時(shí)首先判斷追蹤梯形當(dāng)前所追蹤的斜邊是否與其相鄰的梯形斜邊相接,若相接則將該梯形標(biāo)記為新的追蹤梯形

13、并改變追蹤方向;若無(wú)法找到符合條件的梯形,則繼續(xù)追蹤當(dāng)前梯形的另一斜邊,并改變追蹤方向。圖5基于梯形的邊界追蹤Fig.5Boundary Tracing3實(shí)驗(yàn)與分析實(shí)驗(yàn)計(jì)算機(jī)配置為:奔騰IV 1.86G CPU ,1.0G B 內(nèi)存,操作系統(tǒng)為Windows XP Professio nal 。實(shí)驗(yàn)結(jié)果如表1所示,其中記錄了算法3個(gè)主要階段的時(shí)間消耗。結(jié)果表明,邊界追蹤和面的構(gòu)建耗時(shí)很少,相對(duì)于總耗時(shí)而言可忽略不計(jì);多邊形求交約占總耗時(shí)的30%;梯形單元的分裂則占用了大部分計(jì)算時(shí)間,其主要影響因素是數(shù)據(jù)量的大小(坐標(biāo)點(diǎn)總數(shù)。坐標(biāo)點(diǎn)總數(shù)直接影響到水平掃描線所構(gòu)建的掃描帶大小,假定多邊形頂點(diǎn)總數(shù)為

14、N +1,在最壞情形下多邊形被劃分為N 條掃描帶,平均每條掃描帶上有M 個(gè)梯形。在梯形分裂過(guò)程中,將新的梯形插入到梯形鏈表時(shí),必須通過(guò)折半查找進(jìn)行鏈表定位,折半查找的時(shí)間復(fù)雜度為O (lg M ,而總的時(shí)間復(fù)雜度為O (N lg M ,一般地N >>M 。多邊形數(shù)據(jù)量與計(jì)算耗時(shí)的關(guān)系如表2和圖6所示,該實(shí)驗(yàn)符合預(yù)期設(shè)想。為保證不受所選圖形影響,設(shè)定每個(gè)多邊形形狀大致相同,且在圖上均勻分布。表1多邊形裁剪實(shí)驗(yàn)結(jié)果Tab.1Results of Clipping Test主多邊形個(gè)數(shù)/數(shù)據(jù)量窗口多邊形個(gè)數(shù)/數(shù)據(jù)量多邊形求交耗時(shí)/s梯形單元分裂耗時(shí)/s 邊界追蹤耗時(shí)/s總耗時(shí)/s2500

15、/8.24M27.51641.9532.59375.717173 武漢大學(xué)學(xué)報(bào)信息科學(xué)版2010年3月表2多邊形裁剪時(shí)間實(shí)驗(yàn)2Tab.2Processing Time of Clipping主多邊形個(gè)數(shù)/數(shù)據(jù)量窗口多邊形個(gè)數(shù)/數(shù)據(jù)量總耗時(shí)/s25/84K 25/84K 0.094400/1.31M 25/84K 0.578400/2.61M 25/84K 1.0772500/8.24M 25/84K 4.28110000/32.9M25/84K31.061 圖6多邊形坐標(biāo)點(diǎn)個(gè)數(shù)與計(jì)算時(shí)間Fig.6Relation Between Processing Timesand Points Numbe

16、rs在內(nèi)存占用方面,將多邊形分割為梯形單元占用了額外的內(nèi)存。在數(shù)據(jù)組織時(shí),梯形單元分布在各掃描行內(nèi),同一行內(nèi)的所有梯形的上邊共線,下邊也共線(值相同。因此,梯形結(jié)構(gòu)體中僅需存儲(chǔ)4個(gè)頂點(diǎn)的橫坐標(biāo)x ,總計(jì)需要16字節(jié)。根據(jù)多邊形數(shù)據(jù)的復(fù)雜度與掃描行總數(shù),不難估計(jì)梯形單元的總數(shù)據(jù)量。假定掃描帶行數(shù)為20萬(wàn),行均梯形個(gè)數(shù)為20,則總數(shù)據(jù)量為20萬(wàn)×20×16字節(jié)64M ,而目前個(gè)人計(jì)算機(jī)的主流配置為12G 內(nèi)存。目前,Weiler 算法6、Vatti 算法7和Greiner 2Hormann 算法8是公認(rèn)的可以在合理時(shí)間內(nèi)處理一般情況的多邊形裁剪算法。3類算法對(duì)多邊形結(jié)點(diǎn)所采用的

17、數(shù)據(jù)結(jié)構(gòu)有所不同,但多邊形間線段求交及弧段重組是整個(gè)算法的關(guān)鍵,本文以Greiner 2Hormann 算法為例說(shuō)明其算法運(yùn)行速度。Greiner 2Hormann 算法以雙向鏈表記錄多邊形上結(jié)點(diǎn),假定主多邊形和窗口多邊形上結(jié)點(diǎn)數(shù)各為N ,需要遍歷主多邊形每條邊,考察與窗口多邊形上每條邊的相交情況,有線段相交時(shí)需要在主多邊形和窗口多邊形的結(jié)點(diǎn)鏈表中插入交點(diǎn)。該操作在最壞情況下,時(shí)間復(fù)雜度為O (N 2,即使采用最小外接矩形法等進(jìn)行線面關(guān)系初判,也很難避免對(duì)鏈表的多次遍歷。上述3類方法都是針對(duì)兩個(gè)多邊形的裁剪,若用于多邊形集合間的裁剪,因?yàn)槊總€(gè)多邊形需要維護(hù)一個(gè)結(jié)點(diǎn)鏈表,多邊形間線段求交點(diǎn)及交點(diǎn)

18、信息的插入匹配將變得較為復(fù)雜,算法效率也將受到一定的影響。以上測(cè)試與分析表明,本文算法具有較高的計(jì)算效率,內(nèi)存占用也不高,完全可滿足較復(fù)雜的應(yīng)用需求。4結(jié)語(yǔ)本文借鑒計(jì)算幾何中常用的掃描線思想,提出將裁剪多邊形進(jìn)行梯形分割,將復(fù)雜多邊形劃分為由簡(jiǎn)單梯形構(gòu)成的圖元集合,根據(jù)各梯形單元的屬性來(lái)判定它們是否隸屬于裁剪結(jié)果,最后通過(guò)邊界追蹤將離散的梯形單元拼貼為完整的計(jì)算結(jié)果。與現(xiàn)有算法相比,該算法的特點(diǎn)為:采用類似于柵格的方式來(lái)組織數(shù)據(jù),逐行存儲(chǔ)形態(tài)簡(jiǎn)單的梯形單元,同時(shí)又具有矢量算法的計(jì)算精度;可以回避多數(shù)矢量算法中存在的弧段切割重組、出入點(diǎn)關(guān)系判定、包含關(guān)系計(jì)算等復(fù)雜過(guò)程,算法實(shí)現(xiàn)相對(duì)簡(jiǎn)單。實(shí)驗(yàn)與分

19、析表明該算法具有較高的計(jì)算效率,可實(shí)現(xiàn)較大數(shù)據(jù)量的圖形裁剪操作,具有一定的推廣價(jià)值。參考文獻(xiàn)1Sutherland I E ,Hodgeman G W.ReentrantPolygon ClippingJ .Communications of the ACM ,1974,17(1:322422Liang Y ,Barsky B A.An Analysis and Algorithmfor Polygon Clipping J .Communications of the ACM ,1983,26(11:86828773Foley J D ,Dam A ,Feiner S K ,et al.Co

20、mputerGraphics ,Principles and Practice M .Reading ,M A :Addison 2Wesley ,19904Maillot P G.A New ,Fast Method for 2D PolygonClipping :Analysis and Software Implementation J .ACM Transactions on Graphics ,1992,11(3:27622905Andereev R D.Algorithm for Clipping ArbitraryPolygons J .Computer Graphics For

21、um ,1989,8(2:18321916Weiler K ,Atherton P.Hidden Surface RemovalUsing Polygon Area SortingC.The SIGGRA P H 77,New Y ork ,19777Vatti B R.A Generic Solution to Polygon ClippingJ .Communications of the ACM ,1992,35(1:562638Greiner G ,Hormann K.Efficient Clipping ofArbitrary Polygons J .ACM Transactions

22、 onGraphics ,1998,17(2:71283第一作者簡(jiǎn)介:王結(jié)臣,博士,副教授,現(xiàn)主要從事GIS 理論與應(yīng)用研究。E 2mail :wangjiechen hot (下轉(zhuǎn)第377頁(yè)273 第35卷第3期劉啟亮等:一種基于局部分布的空間聚類算法773A Local DistributionB ased Spatial Clustering AlgorithmL I U Qili ang1L I Guangqi ang1D EN G M i n1(1Department of Surveying and G eo2informatics,Central S outh Universit

23、y,932S outh Lushan Road,Changsha410083,China Abstract:All existing spatial clustering met hods only utilize t he spatial distances and t he numbers of entities in t he spatial nearest neighborhood to find t he spatial clusters in t he spatial database,wit hout taking t he spatial local distribution

24、characters into account.Hence,t he clustered result s are unreasonable in many cases.To overcome such limitations, we propo se a new spatial clustering algorit hm based upo n t he local dist ribution among t he entities in certain spatial neighborhood,where median angle for each entity is employed t

25、o measure it s property of local distribution.In t he p rocess of spatial clustering,a series of recursive search were implemented for all t he entities so t hat t hose entities wit h it s median angle being very similar are clustered.Two test s were implemented to demonst rate t hat t he propo sed

26、met hod is more prominent t han DBSCAN,and can be used to find t he clusters wit h arbit rary shapes.K ey w ords:spatial cluster;local distribution;neighborhood;DBSCAN algorit hmAbout the f irst author:LI U Qiliang,postgraduate,majors in spatio2temporal clustering and spatio2temporal outlier detecti

27、on.(上接第372頁(yè)An E ff icient Algorithm for Complex Polygon ClippingW A N G J iechen1S H EN Di n gt ao1C H EN Yanmi ng1L I L i f an1 (1Depart ment of Geographic Information Science,Nanjing University,22Hankou Road,Nanjing210093,China Abstract:We popose an efficient algorit hm for complex polygon clipping by adopting t he t rapezium segmentation technique and scan2line idea.Firstly,we find and comp ute t