多邊形裁剪算法

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

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

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

4、邊形的內(nèi)部. (2) 進(jìn)點(diǎn)和出點(diǎn)的定義. 設(shè)i是多邊形s和c的一個(gè)交點(diǎn),如果s沿著c的邊界的方向在i點(diǎn)從c的外部進(jìn)入c的內(nèi)部,則稱i為對(duì)于c的一個(gè)進(jìn)點(diǎn).反之,如果s在i點(diǎn)從c的內(nèi)部出到c的外部,則稱i為對(duì)于c的一個(gè)出點(diǎn). 例如,對(duì)于如圖1所示的多邊形c和s及其交點(diǎn)i,若s的方向?yàn)槟鏁r(shí)針方向s1s2s3s4s5,則i5i1i3是對(duì)于c的進(jìn)點(diǎn),i4i2i6是對(duì)于c的出點(diǎn).如果s的方向?yàn)轫槙r(shí)針方向s5s4s3s2s1,則對(duì)于c來說,i2i4i6是進(jìn)點(diǎn),i1i5i3是出點(diǎn). (3) 進(jìn)點(diǎn)和出點(diǎn)的判定. 圖1 進(jìn)點(diǎn)和出點(diǎn)的定義 假設(shè)多邊形s的一條邊sisi+1與另一多邊形c有交點(diǎn).當(dāng)點(diǎn)si是c的外點(diǎn)時(shí),

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

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

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

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

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

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

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

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

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

14、結(jié)點(diǎn)之間; 由sin標(biāo)記插入到實(shí)體多邊形鏈表中的第1個(gè)交點(diǎn)對(duì)于裁剪多邊形的進(jìn)出性,sin=1表示出; 令pf指向第1個(gè)交點(diǎn)結(jié)點(diǎn),以備算法的第3階段使用; 將pc指向該交點(diǎn)在裁剪多邊形上的對(duì)應(yīng)邊; 以pc指向的邊與實(shí)體多邊形進(jìn)行直線裁剪操作; 求出上述第1個(gè)交點(diǎn)對(duì)于實(shí)體多邊形的進(jìn)出性; if(上述第1個(gè)交點(diǎn)對(duì)于實(shí)體多邊形和裁剪多邊形的進(jìn)出性相同) 逆轉(zhuǎn)裁剪多邊形的鏈表; 令ps指向?qū)嶓w多邊形的下一個(gè)邊; 轉(zhuǎn)到算法的第2階段; 令ps指向?qū)嶓w多邊形的下一個(gè)邊; while ps!=heads; if（實(shí)體多邊形的每個(gè)點(diǎn)是否都在裁剪多邊形里）直接輸出實(shí)體多邊形鏈表。else輸出裁剪多邊形鏈表兩個(gè)多邊

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

16、邊的方向?yàn)樾驅(qū)⑦@些交點(diǎn)插入其中.例如,如果該邊的方向是從左向右的斜線,則可按交點(diǎn)的x坐標(biāo)的大小順序插入這些交點(diǎn). 在這個(gè)階段,算法不需要標(biāo)記交點(diǎn)的進(jìn)出性,因?yàn)槿缜八?算法只需在第1階段用變量sin來標(biāo)記實(shí)體多邊形鏈表中的第1個(gè)交點(diǎn)對(duì)于裁剪多邊形的進(jìn)出性,其余交點(diǎn)對(duì)于兩個(gè)多邊形的進(jìn)出性便由如前所述的規(guī)律可知.下面是算法的第2部分的形式描述. do 以ps指向的邊與裁剪多邊形進(jìn)行直線裁剪操作; if (上述直線裁剪操作有交點(diǎn)) 將每個(gè)交點(diǎn)按其在該邊上的順序插入到實(shí)體多邊形鏈表和裁剪多邊形鏈表的對(duì)應(yīng)相交邊的兩個(gè)結(jié)點(diǎn)之間; 令ps指向?qū)嶓w多邊形的下一個(gè)邊; while ps!=heads; 轉(zhuǎn)到算法

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

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

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

20、個(gè)交點(diǎn)結(jié)點(diǎn)(記為n2)之前的裁剪多邊形鏈表中的結(jié)點(diǎn)加入到輸出多邊形鏈表的最后,并使po指向n2; while po!=pp else 使pp指向?qū)嶓w多邊形鏈表中的下一個(gè)出點(diǎn)結(jié)點(diǎn)(即下一個(gè)交點(diǎn)結(jié)點(diǎn)的下一個(gè)交點(diǎn)結(jié)點(diǎn)); until pp=pf; 算法結(jié)束,輸出多邊形鏈表由指針鏈表out的polygon域指出. 5.焦點(diǎn)的計(jì)算和判斷由上述分析可知,多邊形裁剪的交點(diǎn)判斷和計(jì)算是以多邊形窗口的線裁剪為基礎(chǔ)的,因?yàn)樵诙噙呅尾眉糁星蠼稽c(diǎn)時(shí)是用實(shí)體多邊形的每一條邊與裁剪多邊形求交點(diǎn),即為線裁剪.本文采用一個(gè)更有效的、適用于一般多邊形的判斷和計(jì)算交點(diǎn)的方法,我們稱其為錯(cuò)切變換法.下面加以描述. 設(shè)多邊形窗口c有

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

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