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

1、項目來源:國家863計劃資助項目(2002AA131030。收稿日期:2003 11 12./修回日期:2004 03 03.第一作者簡介:李新雙,碩士研究生,現(xiàn)主要從事遙感圖像處理及GIS 應用等方面的研究。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 文獻標識碼:B任意多邊形裁剪算法的研究及其實現(xiàn)李志濤1李 霖1吳賢良2朱海紅1(1武漢大學資源與環(huán)境科學學院,武漢市珞喻路129號,430079;2湖南省國土資源廳第二測繪院,長沙縣暮云鎮(zhèn)南托,410119摘 要 介紹了一種改

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

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

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

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

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

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

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

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

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

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

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

15、剪線段中,通過判斷裁剪線段的flag 值便可確定線段跟主多邊形的關系,得到最后的裁剪結果。4 結束語:本文所討論的算法是在W eiler Atherton 算法的基礎上所作的了一些改進后在V C+6.0的環(huán)境下實現(xiàn)的。同原算法相比,簡化了實現(xiàn)過程,避免了使用雙向指針等復雜技術,同時還詳細分析了特殊情況的處理,可處理各種復雜的情況,最后生成的多邊形可分塊提取輸出。地圖符號庫的應用實驗表明,改進后的算法對各種復雜情況的裁剪都能精確計算出結果,并且穩(wěn)定可靠。參考文獻1 吳有富.Cohen Sutherlan d 算法的改進及其推廣J.貴州工業(yè)大學學報,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 .北京:機械工業(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.浙江大學學報,1989,23(1:1451528 吳 兵,尹偉強.具有拓撲關系的任意多邊形裁剪算法J.小型微型計算機系統(tǒng),2000,21(1l:116611689 楊維芳.兩個復雜多邊形求交的矢量算法J.蘭州鐵道學院學報(自然科學版,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)主要研究方向為計算機圖形圖像處理在地理信息系統(tǒ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