任意多邊形裁剪算法的研究及其實(shí)現(xiàn)

1、項(xiàng)目來源:國家863計(jì)劃資助項(xiàng)目(2002AA131030。收稿日期:2003 11 12./修回日期:2004 03 03.第一作者簡介:李新雙,碩士研究生,現(xiàn)主要從事遙感圖像處理及GIS 應(yīng)用等方面的研究。E mail :lixinshuang03DESIG N OF GROU ND OBJECT SPECTRAL LIBRARYLI Xinshuang ZH AN G Liangpei LI Pingxian g(Sta te Key L ab ora tory of In fo rmation En gin e erin g in su rve ying ,Ma ppin g an d

2、 R e mote Se n sin g,Wuh a n U n iversity,129Lu oyu R oa d,Wuh a n 430079,Ch in a ABSTRA CT It is an effective method to establish a gr ound object spectral library ,for manag ing and analyze v ar ied typical objects spectra date.This paper discusses the design of spectral library includ ing the dat

3、a standardizati on,system structure design and function composition as well.KE Y WORDS spectral library ;ground object spectra;hyperspectral data文章編號:1007 3817(200405 0008 03中圖分類號:P283.7 文獻(xiàn)標(biāo)識碼:B任意多邊形裁剪算法的研究及其實(shí)現(xiàn)李志濤1李 霖1吳賢良2朱海紅1(1武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院,武漢市珞喻路129號,430079;2湖南省國土資源廳第二測繪院,長沙縣暮云鎮(zhèn)南托,410119摘 要 介紹了一種改

4、進(jìn)的W eiler A therton 裁剪算法,簡化了算法的實(shí)現(xiàn)過程,完善了細(xì)節(jié)處理,通過在地圖符號庫設(shè)計(jì)系統(tǒng)進(jìn)行實(shí)驗(yàn),獲得了滿意的結(jié)果。關(guān)鍵詞 地理信息系統(tǒng);裁剪;多邊形;算法;研究與實(shí)現(xiàn) 按照處理對象的不同,裁剪可以分為線段裁剪和多邊形裁剪。線段裁剪算法,主要有線段細(xì)分裁剪算法1、中點(diǎn)分割算法、梁友棟 Barsky 算法2等,這些算法的缺陷就是裁剪區(qū)域必須為規(guī)則的凸多邊形或者矩形窗口3。多邊形裁剪算法除了梁友棟 Barsky 算法外,還有Suther Hodg man 算法4及Weiler At herton5算法。Suther Ho dgman 算法是用矩形窗口邊界直線作為邊界對給定多

5、變形進(jìn)行逐次裁剪,可能產(chǎn)生邊界退化的問題,需要進(jìn)行特殊處理6。梁友棟Barsky 多邊形裁剪算法是其線段裁剪算法的增強(qiáng),可以擴(kuò)展到任意的凸裁剪窗口7。在實(shí)際應(yīng)用中所涉及的可能是任意多邊形,Weiler A therton 算法可以處理凹多邊形裁剪區(qū)域,實(shí)現(xiàn)任意多邊形的裁剪,但是其缺點(diǎn)就是實(shí)現(xiàn)過程復(fù)雜,同時(shí)在細(xì)節(jié)處理方面不夠完善。1 Weiler Atherton 算法主要思想在Weiler Ather ton 算法中,多邊形采用有序、有方向的頂點(diǎn)環(huán)形表描述。當(dāng)用裁剪區(qū)域裁剪被裁剪多邊形時(shí),裁剪多邊形與被裁剪多邊形邊界相交的交點(diǎn)成對出現(xiàn)且分為兩類,分別稱為入點(diǎn)和出點(diǎn)。由入點(diǎn)開始沿被裁剪多邊形追蹤

6、,當(dāng)遇到出點(diǎn)時(shí)跳轉(zhuǎn)至裁剪多邊形繼續(xù)追蹤,如果再次遇到入點(diǎn)則跳轉(zhuǎn)至被裁剪多邊形繼續(xù)追蹤。重復(fù)以上過程,直至回到起始入點(diǎn),即完成一個(gè)多邊形的追蹤過程8。2 對Weiler Atherton 算法的改進(jìn)及實(shí)現(xiàn)Weiler Ather to n 算法的實(shí)現(xiàn)過程較為復(fù)雜,需要建立層層線表、點(diǎn)表及雙向指針等。而且有些入點(diǎn)、出點(diǎn)的判斷也較繁瑣。現(xiàn)對這一算法進(jìn)行了改進(jìn),簡化了實(shí)現(xiàn)過程,同時(shí)在細(xì)節(jié)處理如兩線段的交點(diǎn)、內(nèi)點(diǎn)外點(diǎn)的判斷以及最后獲取輸出多邊形的過程也作了相應(yīng)的改進(jìn)。以內(nèi)裁剪為例,算法描述如下:第一步,對主多邊形及裁剪多邊形進(jìn)行排序。使之按順時(shí)針方向排列,并且確定其首末點(diǎn)相同,亦即閉合的;然后將兩多邊形

7、由點(diǎn)結(jié)構(gòu)轉(zhuǎn)化為自定義的線段結(jié)構(gòu),記錄每條線段的首末點(diǎn)。第二步,求多邊形的交點(diǎn)。如果要將上一步轉(zhuǎn)化來的兩個(gè)線段數(shù)組中每一項(xiàng)兩兩求交,則比較耗時(shí),所以就首先對兩個(gè)線段進(jìn)行一個(gè)外接矩形的比較9,如果兩者不可能相交,就跳過。任意兩條線段之間的交點(diǎn)情況又可細(xì)分如下10。1當(dāng)兩線段都為垂直線時(shí),可能出現(xiàn)交點(diǎn)的情況如圖1所示。交點(diǎn)的記錄情況是:在圖1(a中線段a 記錄b 1點(diǎn),線段b 記錄a 2點(diǎn);在圖1(b中,線段a 記錄b 1點(diǎn),線段b 無交點(diǎn)記錄;在圖1(c中,線段a 記錄b 1,b 2點(diǎn),線段b 無交點(diǎn)記錄;在圖1(d中,線段a 無交點(diǎn)記錄,線段b 記錄a 2點(diǎn);在圖1(e中,線段a 記錄b 2點(diǎn),

8、線段b 無交點(diǎn)記錄;在圖1(f中,線段8測繪信息與工程 Jour nal of Geomatics 2004 Oct.;29(5 圖1 兩線段都垂直時(shí)可能出現(xiàn)交點(diǎn)的情況a 無交點(diǎn)記錄,線段b 記錄a 1,a 2點(diǎn);在圖1(g中,線段a 無交點(diǎn)記錄,線段b 記錄a 1點(diǎn);在圖1(h中,線段a 記錄b 2點(diǎn),線段b 記錄a 1點(diǎn)。2當(dāng)兩線段一條是垂直線,另一條不是垂直線時(shí),可能出現(xiàn)交點(diǎn)的情況如圖2所示。交點(diǎn)的記錄情況是:在圖2(a中,線段a 記錄b 1點(diǎn),線段b 無交點(diǎn)記錄;在圖2(b中,線段a 無交點(diǎn)記錄,線段b 記錄a 1點(diǎn);在圖2(c中,線段a 記錄交點(diǎn),線段b 記錄交點(diǎn);在圖2(d中,線段

9、a 無交點(diǎn)記錄,線段b 記錄a 2點(diǎn);在圖2(e中,線段a 記錄b 2點(diǎn),線段b 無交點(diǎn)記錄;在圖2(f中,線段a 無交點(diǎn)記錄,線段b 記錄a 1點(diǎn);在圖2(g中,線段a 記錄b 1點(diǎn),線段b 無交點(diǎn)記錄;在圖2(h中,線段a 記錄交點(diǎn),線段b 記錄交點(diǎn);在圖2(i中,線段a 記錄b 2點(diǎn),線段b 無交點(diǎn)記圖2 兩線段一個(gè)垂直另一個(gè)不垂直時(shí)可能出現(xiàn)交點(diǎn)的情況錄;在圖2(j中,線段a 無交點(diǎn)記錄,線段b 記錄a 2點(diǎn)。3當(dāng)兩線段皆不是垂直線時(shí),有兩種情況。兩者互相平行。此時(shí),若兩者有部分重合,則兩線段的空間關(guān)系及交點(diǎn)的記錄情況類似于1。若無重合部分,則沒有交點(diǎn)。兩者不平行。處理情況類似于2。記錄

10、交點(diǎn)的結(jié)構(gòu)為自定義類型。structfloat x ;/交點(diǎn)x 坐標(biāo) float y ;/交點(diǎn)y 坐標(biāo)int flag ;/標(biāo)識符 int index ;/標(biāo)識符Float Point ;為主多邊形及裁剪多邊形各開辟一個(gè)數(shù)組,分別紀(jì)錄落在其上的交點(diǎn)。記錄交點(diǎn)時(shí)flag 全部賦為0,而index 則保存記錄此交點(diǎn)所在線段L inei的序號i,為下一步的插入操作做準(zhǔn)備。第三步,將交點(diǎn)數(shù)組插入到原始多邊形中。將求得的交點(diǎn)數(shù)組分別插入到主多邊形及裁剪多邊形中,其操作過程如圖3 所示。圖3 交點(diǎn)插入到原始多邊形根據(jù)交點(diǎn)的index 值得到產(chǎn)生其線段的序號,而每一線段都對應(yīng)著原多邊形頂點(diǎn)數(shù)組的相鄰的兩項(xiàng),

11、因此只需將交點(diǎn)插入到頂點(diǎn)數(shù)組中這相鄰兩項(xiàng)之間即可。當(dāng)同時(shí)有幾個(gè)點(diǎn)需要插入時(shí),需對這些交點(diǎn)進(jìn)行排序。進(jìn)行這一步操作時(shí)要將原多邊形由普通的點(diǎn)轉(zhuǎn)化為自定義的F loatPoint 型,其flag 全部賦為0;記插入交點(diǎn)后的主多邊形及裁剪多邊形分別為Clipping List 及ClippedList 。第四步,內(nèi)點(diǎn)外點(diǎn)的判斷。不再是單純判斷其為內(nèi)點(diǎn)外點(diǎn)并存到不同數(shù)組中,而是通過每一個(gè)點(diǎn)結(jié)構(gòu)中的flag 值來標(biāo)識每一個(gè)點(diǎn)的狀態(tài),內(nèi)點(diǎn)外點(diǎn)的判斷如圖4所示。其中圖4(a點(diǎn)落在多邊形的內(nèi)部,其flag 為1;圖4(b點(diǎn)落在多邊形外部,其flag 為0;圖4(c點(diǎn)落在多邊形邊上,并且與下一點(diǎn) 的中點(diǎn)落在多邊形

12、邊上,其flag 為1;圖4(d點(diǎn)落在多邊形邊上,并且與下一點(diǎn)的中點(diǎn)落在多邊形邊內(nèi)部,其flag 為1;圖4(e點(diǎn)落在多邊形邊上,并且與下一點(diǎn)的中點(diǎn)落在多邊形外部,其flag 為 1。圖4 內(nèi)點(diǎn)外點(diǎn)的判斷按上述原則對兩多邊形Clipping List 和ClippedList 上每個(gè)點(diǎn)進(jìn)行上述的flag 賦值操作。第五步,裁剪。經(jīng)過以上各步處理,每個(gè)點(diǎn)都有一個(gè)flag 9測繪信息與工程 Jour nal of Geomatics 2004 Oct.;29(5值,并且是根據(jù)特定規(guī)則得出的,只要在主多邊形和裁剪多邊形間依次追蹤flag 值為1的點(diǎn),最后使區(qū)域閉合,就得到了所要的多邊形。開辟兩數(shù)組,

13、一個(gè)用以紀(jì)錄裁剪所得的多邊形的頂點(diǎn),另一個(gè)用來紀(jì)錄裁剪所得各個(gè)多邊形的分界點(diǎn)的位置,用以實(shí)現(xiàn)分塊提取。兩個(gè)簡單多邊形內(nèi)裁剪如圖5 所示。圖5 多邊形裁剪示意圖在圖5中兩多邊形裁剪時(shí),首先裁出的是區(qū)域b ,由主多邊形起始點(diǎn)開始遍歷,從第一個(gè)flag 為1的點(diǎn)開始記錄,此后在主多邊形和裁剪多邊形中跳轉(zhuǎn),依次記錄flag 值為1的點(diǎn),最后封閉區(qū)域b 。然后再跳回到主多邊形,從第一次跳轉(zhuǎn)到裁剪多邊形處開始遍歷,裁出區(qū)域a 。當(dāng)再次跳回到主多邊形并進(jìn)行遍歷時(shí),主多邊形中已經(jīng)沒有flag 值為1且沒有記錄過的點(diǎn)。這時(shí)裁剪便結(jié)束了。這只是兩個(gè)簡單多邊形的內(nèi)裁剪,還可以擴(kuò)展到裁剪多邊形和被裁剪多邊形都帶孔的情

14、況。帶有孔的任意多邊形進(jìn)行裁剪時(shí),需要將孔按照逆時(shí)針排序,同時(shí)flag 值的設(shè)置也有相應(yīng)的改動。外裁剪獲取的是裁剪多邊形落在主多邊形外部的部分,需要將主多邊形按照逆時(shí)針排序,若主多邊形包含孔,則孔按順時(shí)針排序。裁剪多邊形不作改變,同時(shí)設(shè)置各點(diǎn)flag 時(shí)要做對應(yīng)的改動。3 在地圖符號庫中的應(yīng)用實(shí)驗(yàn)在地圖符號庫中,由于地圖符號本身不僅有封閉的多邊形,還有不封閉的線段,因此還需要對線段進(jìn)行裁剪。同樣因?yàn)橹鞫噙呅蔚娜我庑?前面提到的線段裁剪算法不能適用?？梢酝ㄟ^對Weiler Atherton 算法作一些改動便可實(shí)現(xiàn)。同多邊形裁剪相比較,線段的裁剪較為簡單,不需要將主多邊形作處理,只要將交點(diǎn)插入到裁

15、剪線段中,通過判斷裁剪線段的flag 值便可確定線段跟主多邊形的關(guān)系,得到最后的裁剪結(jié)果。4 結(jié)束語:本文所討論的算法是在W eiler Atherton 算法的基礎(chǔ)上所作的了一些改進(jìn)后在V C+6.0的環(huán)境下實(shí)現(xiàn)的。同原算法相比,簡化了實(shí)現(xiàn)過程,避免了使用雙向指針等復(fù)雜技術(shù),同時(shí)還詳細(xì)分析了特殊情況的處理,可處理各種復(fù)雜的情況,最后生成的多邊形可分塊提取輸出。地圖符號庫的應(yīng)用實(shí)驗(yàn)表明,改進(jìn)后的算法對各種復(fù)雜情況的裁剪都能精確計(jì)算出結(jié)果,并且穩(wěn)定可靠。參考文獻(xiàn)1 吳有富.Cohen Sutherlan d 算法的改進(jìn)及其推廣J.貴州工業(yè)大學(xué)學(xué)報(bào),1998,27(4:692 梁友棟,Barsky

16、 B A.An Analysis and Algorithem for PolygonClipping J.Communications of the ACM ,1983,26(11:8688773 Rogers D F.Procedural Elements for Computer Graphics (2E M .北京:機(jī)械工業(yè)出版社,20024 Suth erland E E,Hodgeman G W.Reentrant Pol ygon ClippingJ.Communicati ons of the ACM ,1974,17(1:32425 Kevin W,Peter A.Hidde

17、n S urface Removal Using Polygon AreaSorti ng J.Computer Graphics,1977,11(2:2142226 Hearn D,Baker M P.Computer Graphics (2EM .北京:電子工業(yè)出版社,20027 沈紀(jì)桂,蔡英平,程 剛.凹多邊形裁剪J.浙江大學(xué)學(xué)報(bào),1989,23(1:1451528 吳 兵,尹偉強(qiáng).具有拓?fù)潢P(guān)系的任意多邊形裁剪算法J.小型微型計(jì)算機(jī)系統(tǒng),2000,21(1l:116611689 楊維芳.兩個(gè)復(fù)雜多邊形求交的矢量算法J.蘭州鐵道學(xué)院學(xué)報(bào)(自然科學(xué)版,2002,21(1:10811010Va

18、tti B R.A Generic S oluti on to Polygon ClippingJ.Commun ications of the ACM ,1992,35(7:5663收稿日期:2003 11 28./修回日期:2004 02 27.第一作者簡介:李志濤,碩土研究生,現(xiàn)主要研究方向?yàn)橛?jì)算機(jī)圖形圖像處理在地理信息系統(tǒng)中的應(yīng)用。E mail :leezhitao_tureRESEARCH AND IMPLEMENTATION OF POLYG ON CLIPPING ALGORITHMLI Zhitao 1 LI Lin 1 WU XianLiang 2 ZH U HaiH ong 1(1Sch oo l of R e sou rce an d Enviro nme n t Scie n ce,Wu h a n U n iversity,129Lu oyu R oa d,Wu h an 430079,Ch in a ;2Th e 2n d Su rveyin g an d Ma ppin g In stitu