多邊形裁剪算法

1、多邊形裁剪劉運達 【油源恒業(yè) 北京 2003】摘要： 多邊形裁剪與線剪裁相比具有更廣泛的實用意義,因此它是目前裁剪研究的主要課題.提出了一個多邊形裁剪多邊形的有效算法.其中的多邊形都可以是一般多邊形,也可以是凹多邊形。該算法使用單線性鏈表數(shù)據(jù)結構,與其他使用雙鏈表或樹結構的算法相比,占用的空間小特點。其次,找到了兩個多邊形之間進、出點之間的關系.再通過合理的數(shù)據(jù)結構處理,減少了算法對多邊形鏈表的遍歷次數(shù),而且允許多邊形既可以按順時針方向也可以按逆時針方向輸入.最后,判斷和計算交點是裁剪算法的主要工作.提出了一個具有最少計算量的交點判斷和計算方法。結果表明,新算法具有最簡單的結構。關鍵詞: 計算

2、機圖形學;凹多邊形;多邊形剪裁;交點計算;單鏈表結構 1引言在圖形系統(tǒng)中,二維裁剪是最為基礎、最為常用的操作之一.其典型的應用是在圖形的消隱處理等處理求交操作之中.對裁剪算法的研究主要集中在裁剪直線和裁剪多邊形兩方面.在實用中,多邊形裁剪與線剪裁相比具有更高的使用率,因此它是目前裁剪研究的主要課題.多邊形裁剪用于裁剪掉被裁剪多邊形(又稱為實體多邊形)位于窗口(又稱為裁剪多邊形)之外的部分.多邊形愈復雜,其裁剪算法就愈難以實現(xiàn).現(xiàn)有的解決方案或者局限于某一類多邊形,或者結構復雜、時間消耗大.本文提出了一個新的多邊形裁剪多邊形的有效算法.其中的裁剪多邊形和被裁剪多邊形都可以是一般多邊形,也可以是凹

3、多邊形.該算法只使用單線性鏈表數(shù)據(jù)結構,所以具有數(shù)據(jù)結構簡單、占用空間少的特點,而且無須事先規(guī)定以什么方向輸入圖形的頂點.另外,該算法使用了一個新的具有最少計算量的交點判斷和計算方法,進一步加快了算法的運行速度.算法最終通過簡單的遍歷線性鏈表,可以得到每一個輸出多邊形.2基本概念與定義為了便于下面對算法的講解,本節(jié)首先介紹有關多邊形裁剪的一些基本概念及術語. (1) 多邊形的邊的方向與內外區(qū)域的關系. 如果多邊形的邊的方向是順時針的(即多邊形的頂點是以順時針的順序輸入的),則在沿著多邊形的邊走時,右側區(qū)域為多邊形的內部;相反,如果多邊形的邊的方向是逆時針的,則在沿著多邊形的邊走時,左側區(qū)域為多

4、邊形的內部. (2) 進點和出點的定義. 設i是多邊形s和c的一個交點,如果s沿著c的邊界的方向在i點從c的外部進入c的內部,則稱i為對于c的一個進點.反之,如果s在i點從c的內部出到c的外部,則稱i為對于c的一個出點. 例如,對于如圖1所示的多邊形c和s及其交點i,若s的方向為逆時針方向s1s2s3s4s5,則i5i1i3是對于c的進點,i4i2i6是對于c的出點.如果s的方向為順時針方向s5s4s3s2s1,則對于c來說,i2i4i6是進點,i1i5i3是出點. (3) 進點和出點的判定. 圖1 進點和出點的定義 假設多邊形s的一條邊sisi+1與另一多邊形c有交點.當點si是c的外點時,

5、則沿著s的走向,邊sisi+1與c的第一個交點i必是c的進點;而當si是c的內點時,i必是c的出點.由于沿著s的邊界對于c的進點和出點是交替出現(xiàn)的(兩多邊形的邊重合或者兩多邊形在頂點處相交的情況除外.這類特殊情況的處理將在第5節(jié)進行討論),所以,只需判斷第1個交點是進點還是出點,其他交點的進出性則可依次確定. 對于一個多邊形裁剪另一個多邊形的過程,就是求兩個多邊形的相交區(qū)域(我們稱其為結果多邊形或輸出多邊形).結果多邊形是由實體多邊形位于裁剪多邊形內的邊界和裁剪多邊形位于實體多邊形內的邊界組成的. 3算法的數(shù)據(jù)結構 多邊形裁剪算法需要一個適當?shù)臄?shù)據(jù)結構來存儲多邊形及交點,并能夠在其上進行正確的

6、操作.算法的每個多邊形由一個單鏈表來表示,單鏈表的每一個結點按序(多邊形頂點輸入的順序)存儲著多邊形的一個頂點.最后一個結點的指針指向第1個結點(循環(huán)單鏈表).每個鏈表由一個頭指針指向其第1個結點,實體多邊形鏈表的第1個結點由頭指針heads指示;裁剪多邊形鏈表的第一個結點由頭指針headc指示.結點的結構定義如下:struct vertexdouble x,y;bool inters,used;pointer next;/pointer 表示指針類型;struct intersectiondouble x,y;bool inters,used;pointer next1,next2; /po

7、inter 表示指針類型;其中的指針域用于將交點分別插入到兩個多邊形的單鏈表中,第1指針域next1用于插入實體多邊形鏈表;第2個指針域next2用于插入裁剪多邊形鏈表.這樣的數(shù)據(jù)結構定義使算法在求出一個交點時只需建立1個intersection(交點)類型的結點,并分別插入到兩個多邊形的單鏈表中即可。注意: 實體多邊形鏈表中的交點的進出性是對裁剪多邊形而言的,而裁剪多邊形鏈表中的交點的進出性則是對實體多邊形而言的.在這兩個數(shù)據(jù)結構的定義中,布爾類型域inters用于區(qū)分該結點是否intersection(交點)類型的結點;used域用于有多個輸出多邊形時.所有交點的used域的初值都為0,當

8、一個交點被輸出時,其used域被置為1. 裁剪結果可能得到多個分立的輸出多邊形,因此需要設立一個指針鏈表out,其每個結點有一個指針域polygon指向一個輸出多邊形鏈表的第一個結點.該指針鏈表的結點結構如下: struct out pointer polygon; /pointer 表示指針類型 pointer next; /pointer 表示指針類型;4算法描述新算法分為3個階段.第1個階段,判斷及計算第1個交點,并由其進出性判斷兩個多邊形是否同向.如果不同向,則將裁剪多邊形鏈表反向,然后將該交點插入到兩個多邊形的鏈表中.第2階段,依次以實體多邊形的每一個邊對裁剪多邊形進行直線裁剪操作,

9、判斷及計算其余交點,并以正確的順序插入到兩個多邊形的鏈表中.第3階段,遍歷整個鏈表,輸出最終結果. 我們以下面的引理開始算法第1階段的描述. 引理1. 如果兩個相交多邊形的邊的取向相同(均為順時針或逆時針方向),則對一個多邊形是進點的交點對另一個多邊形必是出點. 證明:設分別屬于兩個相交多邊形s和c的兩個相交邊為se和ce,我們首先考慮兩個相交多邊形的邊的取從下向上穿過s(圖3a的情況),則由圖3顯然可見,c經過交點從多邊形s內走向s外,即該交點是對于多邊形s的出點;而另一方面,邊s向均為順時針方向的情況.在這種情況下,多邊形邊的右側為多邊形內側(在圖3中由陰影表示).考慮兩邊之間的夾角,由于

10、此夾角是由兩邊的相對位置決定的,所以我們可以將一個邊的方向固定而討論另一個邊方向變化的各種情況.在圖3中,設se邊的方向是從左向右固定不變的,如果ce的正向與se的正向的夾角在0o180o之間(即ceeee則是經過該交點從多邊形c外走向c內,即該交點是對于多邊形c的進點. (a) se和ce的正向的夾角在0o和180o之間 (b) se和ce的正向的夾角在180o和360o之間圖3 當兩個多邊形的相交邊se和ce的取向均為順時針方向時,對一個多邊形是進點的交點對另一個多邊形必是出點(陰影表示多邊形內側)如果ce的正向與se的正向的夾角在180o360o之間(即ce從上向下穿過se(如圖3(b)

11、所示),則由圖顯然可見,該交點對于多邊形s是進點,而對于多邊形c則是出點.這就是我們要證明的結論. 對于兩個相交多邊形的邊的取向均為逆時針方向的情況,可用相同的方法證明該引理. 根據(jù)該引理,對其中一個多邊形求出一個進點或出點以后,在兩個多邊形方向相同的情況下,其對另一個多邊形的進出性也就確定了.這樣,如果兩個多邊形的方向相同,則在求出交點時只需判斷和標記它對其中一個多邊形是進點還是出點.它對另一個多邊形的進出性則相反.而由第1節(jié)的討論可知,由于沿著一個多邊形的邊界,在其上的進點和出點是交替出現(xiàn)的.所以只需標記第1個交點是進點還是出點,其他交點的進出性則可依次確定.最終我們得出一個結論:如果兩個

12、多邊形的方向相同,則要標記所有交點對于兩個多邊形的進出性,只需標記任何一個多邊形鏈表中的第1個交點的進出性即可(在后面的算法描述中,我們用變量sin來標記實體多邊形鏈表中的第1個交點對于裁剪多邊形是否為進點).因此,新算法的第1步就要是判斷兩個多邊形是否同向.如果不同向,則將裁剪多邊形鏈表反向,使兩個多邊形的方向相同. 判斷兩個多邊形是否同向,是通過判斷一個交點(如第1個交點)對于兩個多邊形的進出性來完成的.如果該點對于實體多邊形的進出性與對于裁剪多邊形的進出性不同,則可知兩個多邊形取向相同;否則,兩個多邊形的取向相反. 新算法將交點的計算與進出性判斷合成一步進行.當一個多邊形的一個邊對另一個

13、多邊形進行直線裁剪操作之后,如果有交點,即可根據(jù)交點在這個邊上的排序的奇偶性來確定交點對另一個多邊形的進出性.這樣在計算交點的同時也確定了該交點的進出性.詳細的描述見第5節(jié)下面是算法的第1部分的形式描述,其中指針變量ps和pc分別指向實體多邊形鏈表和裁剪多邊形鏈表中正在被處理的當前結點.另外,我們把由結點ps和其下一個結點ps.next定義的邊簡稱為由ps指向的邊. ps=heads; do 以ps指向的邊與裁剪多邊形進行直線裁剪操作(即求交點的操作,見第4節(jié)); if (上述直線裁剪操作有交點) 將每個交點(可能有多個)按其在該邊上的順序插入到實體多邊形鏈表和裁剪多邊形鏈表的對應相交邊的兩個

14、結點之間; 由sin標記插入到實體多邊形鏈表中的第1個交點對于裁剪多邊形的進出性,sin=1表示出; 令pf指向第1個交點結點,以備算法的第3階段使用; 將pc指向該交點在裁剪多邊形上的對應邊; 以pc指向的邊與實體多邊形進行直線裁剪操作; 求出上述第1個交點對于實體多邊形的進出性; if(上述第1個交點對于實體多邊形和裁剪多邊形的進出性相同) 逆轉裁剪多邊形的鏈表; 令ps指向實體多邊形的下一個邊; 轉到算法的第2階段; 令ps指向實體多邊形的下一個邊; while ps!=heads; if（實體多邊形的每個點是否都在裁剪多邊形里）直接輸出實體多邊形鏈表。else輸出裁剪多邊形鏈表兩個多邊

15、形無交點,算法結束; 在第2階段,算法從第1階段求出交點的那個實體多邊形邊的下一個邊開始,用每一個實體多邊形邊與裁剪多邊形求交點,并如圖2所示,給每個交點建立一個包含該交點坐標的新的交點結點,然后將其插入到實體多邊形鏈表和裁剪多邊形鏈表的對應相交邊的兩個結點之間.例如,一個交點是由結點ps和其下一個結點ps.next所定義的實體多邊形的邊與由結點pc和其下一個結點pc.next所定義的裁剪多邊形的邊相交形成的,那么該交點結點就應該被插入到實體多邊形鏈表的結點ps和其下一個結點ps.next之間,同時被插入到裁剪多邊形鏈表的結點pc和其下一個結點pc.next之間.當一個邊上有多個交點時,則以該

16、邊的方向為序將這些交點插入其中.例如,如果該邊的方向是從左向右的斜線,則可按交點的x坐標的大小順序插入這些交點. 在這個階段,算法不需要標記交點的進出性,因為如前所述,算法只需在第1階段用變量sin來標記實體多邊形鏈表中的第1個交點對于裁剪多邊形的進出性,其余交點對于兩個多邊形的進出性便由如前所述的規(guī)律可知.下面是算法的第2部分的形式描述. do 以ps指向的邊與裁剪多邊形進行直線裁剪操作; if (上述直線裁剪操作有交點) 將每個交點按其在該邊上的順序插入到實體多邊形鏈表和裁剪多邊形鏈表的對應相交邊的兩個結點之間; 令ps指向實體多邊形的下一個邊; while ps!=heads; 轉到算法

17、的第3階段; 在算法的第3階段,通過遍歷已插入交點結點的實體多邊形和裁剪多邊形鏈表來跟蹤結果多邊形的邊界,最后產生輸出多邊形鏈表. 跟蹤一個結果多邊形的邊界是以實體多邊形鏈表中的一個進點(對于裁剪多邊形)開始的.從該進點到實體多邊形鏈表中的下一個交點(記為n1)之間的實體多邊形的邊界全部是結果多邊形的邊界.n1既是對于裁剪多邊形的出點也是對于實體多邊形的進點,因此從n1點開始到裁剪多邊形鏈表中的下一個交點之間的裁剪多邊形的邊界全部是結果多邊形的邊界(如圖1所示).輸出這些邊界.重復此過程,一直到回到實體多邊形鏈表中的開始進點為止,便跟蹤輸出了一個結果多邊形.在上述過程中,實體多邊形鏈表中的進點

18、(對于裁剪多邊形)的used域被標記為1,以表明從它開始的邊界已經被輸出過.“used域”用于有多個結果多邊形的情況. 算法第3階段的遍歷是以實體多邊形鏈表的順序進行的.從實體多邊形鏈表中的第1個進點開始,如果該進點(當前進點)的used域為0(表明它未被輸出過),則將其置為1,并執(zhí)行上一段所述的跟蹤過程輸出一個結果多邊形;如果該進點的used域為1,則走到實體多邊形鏈表的下一個進點,即該進點的下一個交點的下一個交點(如前所述,在多邊形鏈表中交點的進出性是相隔分布的).以下一個進點為當前進點,重復此過程,一直到回到實體多邊形鏈表中的第1個進點為止.所有的進點都被訪問過,所有的結果多邊形也都被輸

19、出.至此,算法結束.下面是算法第3階段的形式描述. if sin=0 令pf指向實體多邊形鏈表中的下一個交點結點,以確保pf指向第1個進點; pp=pf; do if pp所指的交點結點的used域為0 po=pp; 建立一個新的輸出多邊形鏈表,并將指向該鏈表的頭指針加入到指針鏈表out的最后(在polygon域當中); repeat 將po所指的交點結點(一定是出點)的used域置為1; 將從po所指的交點結點開始(用next1指針域)到下一個交點結點(記為n1)之前的實體多邊形鏈表中的結點加入到輸出多邊形鏈表的最后,并使po指向n1; 將從po所指的交點結點開始(用next2指針域)到下一

20、個交點結點(記為n2)之前的裁剪多邊形鏈表中的結點加入到輸出多邊形鏈表的最后,并使po指向n2; while po!=pp else 使pp指向實體多邊形鏈表中的下一個出點結點(即下一個交點結點的下一個交點結點); until pp=pf; 算法結束,輸出多邊形鏈表由指針鏈表out的polygon域指出. 5.焦點的計算和判斷由上述分析可知,多邊形裁剪的交點判斷和計算是以多邊形窗口的線裁剪為基礎的,因為在多邊形裁剪中求交點時是用實體多邊形的每一條邊與裁剪多邊形求交點,即為線裁剪.本文采用一個更有效的、適用于一般多邊形的判斷和計算交點的方法,我們稱其為錯切變換法.下面加以描述. 設多邊形窗口c有

21、n條邊,c的頂點vi的坐標為(xi,yi),i=1,2,n;被裁剪線段為l,其端點a和b的坐標分別為(xa,ya)和(xb,yb),如圖6所示. 圖6 多邊形窗口與被裁剪線段 下面以xbxa情況為例,記x=xbxa,y=ybya,并假定x0,y0,否則l將與一條坐標軸平行,而這種情況無須錯切變換,使執(zhí)行過程更為簡單. 在設計裁剪算法時,最主要的考慮是盡可能減少不必要的交點計算.本方法給出了很簡單的判斷條件,可以不計算落在窗口邊的延長線上的非有效交點.對于落在被裁剪直線的延長線上的非有效交點,則只有當它被計算出之后才能確定其是否有效(即在直線的兩端點之間). 首先對c和l施加相同的錯切變換,用沿

22、y軸方向的錯切變換將l變換成與x軸平行(水平)的方向.變換的分量形式是x=x; y=x.d+y,其中x和y表示錯切變換后的坐標值(下面均以這種形式表示變換后的點或坐標).顯然,錯切變換對這些點的x坐標沒有影響,如圖7和圖8所示.設直線l與y軸的交點為i(0, yc),這里yc=xa.d+ya.容易驗證,經錯切變換后,直線ab變?yōu)橹本€y=yc.圖7 錯切變換 圖8 圖6經錯切變換后的裁剪多邊形與被裁剪線段(變?yōu)樗骄€)錯切變換是一種仿射變換,它不能保留圖形的度量性質,會引起圖形形狀的改變,但是直線之間的相對關系(相交關系)是不變的.由于對c和l進行錯切變換后,l變成了水平直線,所以很容易判斷和計算交點.又由于變換前后的相交關系及其交點的x坐標都沒有變化,因此在(錯切變換后)求出交點以后只需對其y坐標進行反錯切變換即可.從上面的錯切變換公式可見,錯切變換及其反變換的計算量是很小的. 經過錯切變換,容易看出,c的一條邊與直線ab相交的條件是該邊兩頂點變換后的點vi1(xi1,yi1)和vi(xi,yi)位于直線y=yc兩側,或至少一個變換后的頂點落在該直線上.我們先討論前一種情況.這時,線段vi1vi與直線y=yc的交點的x坐標可計算如下:上述過程可以形式化地描述如下: (1) 計算x,y,d,yc,ya