多邊形裁剪算法課件

裁剪裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外,以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個選擇過程稱為裁剪。圖形裁剪算法，直接影響圖形系統(tǒng)的效率。裁剪裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之1點的裁剪圖形裁剪中最基本的問題。假設窗口的左下角坐標為(xL,yB),右上角坐標為(xR,yT)，對于給定點P(x,y),則P點在窗口內(nèi)的條件是要滿足下列不等式：

xL<=x<=xR并且yB<=y<=yT

否則，P點就在窗口外。問題：對于任何多邊形窗口，如何判別？(xL,yB)(xR,yT)點的裁剪圖形裁剪中最基本的問題。(xL,yB)(xR,y25.6直線段裁剪直線段裁剪算法是復雜圖形裁剪的基礎。復雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。主要的四種算法直接求交算法Cohen-Sutherland算法中點算法梁友棟－barskey算法5.6直線段裁剪直線段裁剪算法是復雜圖形裁剪的基礎。復雜的曲35.6直線段裁剪裁剪線段與窗口的關系：(1)線段完全可見；(2)顯然不可見；(3)其它提高裁剪效率： 快速判斷情形(1)(2)， 對于情形(3)，設法減 少求交次數(shù)和每次求 交時所需的計算量。5.6直線段裁剪4直接求交算法直線與窗口邊都寫成參數(shù)形式，求參數(shù)值。直接求交算法直線與窗口邊都5Cohen-Sutherland裁剪基本思想：對于每條線段P1P2分為三種情況處理:（1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2。（2）若P1P2明顯在窗口外，則丟棄該線段。（3）若線段不滿足（1）或（2）的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復上述處理。為快速判斷，采用如下編碼方法：Cohen-Sutherland裁剪基本思想：6實現(xiàn)方法：

將窗口邊線兩邊沿長，得到九個區(qū)域，每一個區(qū)域都用一個四位二進制數(shù)標識，直線的端點都按其所處區(qū)域賦予相應的區(qū)域碼，用來標識出端點相對于裁剪矩形邊界的位置。100100010101100000000100101000100110ABCDCohen-Sutherland裁剪實現(xiàn)方法：1001000101011000000007Cohen-Sutherland算法將區(qū)域碼的各位從右到左編號，則坐標區(qū)

域與各位的關系為：上下右左 XXXX

任何位賦值為1，代表端點落在相應的位置上，否則該位為0。若端點在剪取矩形內(nèi)，區(qū)域碼為0000。如果端點落在矩形的左下角，則區(qū)域碼為0101。Cohen-Sutherland算法將區(qū)域碼的各位從右到左編8Cohen-Sutherland算法一旦給定所有的線段端點的區(qū)域碼，就可以快速判斷哪條直線完全在剪取窗口內(nèi)，哪條直線完全在窗口外。所以得到一個規(guī)律：Cohen-Sutherland算法一旦給定所有的線段端點的9Cohen-Sutherland裁剪若P1P2完全在窗口內(nèi)code1=0,且code2=0,則“取”若P1P2明顯在窗口外code1&code2≠0，則“棄”

在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復上述處理。

編碼線段裁剪Cohen-Sutherland裁剪若P1P2完全在窗口內(nèi)c10Cohen-Sutherland裁剪如何判定應該與窗口的哪條邊求交呢？ 編碼中對應位為1的邊。計算線段P1(x1,y1)P2(x2,y2)與窗口邊界的交點 if(LEFT&code!=0) { x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);} elseif(RIGHT&code!=0) { x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);} elseif(BOTTOM&code!=0){ y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);}elseif(TOP&code!=0){ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);}具體算法見p201Cohen-Sutherland裁剪如何判定應該與窗口的哪條11Cohen-Sutherland

直線裁剪算法小結(jié)本算法的優(yōu)點在于簡單，易于實現(xiàn)?？梢院唵蔚拿枋鰹閷⒅本€在窗口左邊的部分刪去，按左，右，下，上的順序依次進行，處理之后，剩余部分就是可見的了。在這個算法中求交點是很重要的，決定了算法的速度。另外，本算法對于其它形狀的窗口未必同樣有效。特點：用編碼方法可快速判斷線段的完全可見和顯然不可見。Cohen-Sutherland

直線裁剪算法小結(jié)本算法的12中點分割裁剪算法基本思想：從P0點出發(fā)找出離P0最近的可見點，和從P1點出發(fā)找出離P1最近的可見點。這兩個可見點的連線就是原線段的可見部分。與Cohen-Sutherland算法一樣首先對線段端點進行編碼，并把線段與窗口的關系分為三種情況，對前兩種情況，進行一樣的處理；對于第三種情況，用中點分割的方法求出線段與窗口的交點。A、B分別為距P0、P1最近的可見點，Pm為P0P1中點。

中點分割裁剪算法基本思想：從P0點出發(fā)找出離P0最近的可見點13中點分割算法-求線段與窗口的交點從P0出發(fā)找距離P0最近可見點采用中點分割方法先求出P0P1的中點Pm,若P0Pm不是顯然不可見的，并且P0P1在窗口中有可見部分，則距P0最近的可見點一定落在P0Pm上，所以用P0Pm代替P0P1；否則取PmP1代替P0P1。再對新的P0P1求中點Pm。重復上述過程，直到PmP1長度小于給定的控制常數(shù)為止，此時Pm收斂于交點。從P1出發(fā)找距離P1最近可見點采用上面類似方法。中點分割算法-求線段與窗口的交點從P0出發(fā)找距離P0最近可見14中點分割裁剪算法中點分割裁剪算法15對分辯率為2N*2N的顯示器，上述二分過程至多進行N次。主要過程只用到加法和除法運算，適合硬件實現(xiàn)，它可以用左右移位來代替乘除法，這樣就大大加快了速度。中點分割裁剪算法對分辯率為2N*2N的顯示器，上述二分過程至多進行N次。中點16

設要裁剪的線段是P0P1。P0P1和窗口邊界交于A,B,C,D四點，見圖。算法的基本思想是從A,B和P0三點中找出最靠近的P1點，圖中要找的點是P0。從C,D和P1中找出最靠近P0的點。圖中要找的點是C點。那么P0C就是P0P1線段上的可見部分。梁友棟-Barsky算法設要裁剪的線段是P0P1。P0P1和窗口邊界交于A17梁友棟-Barsky算法線段的參數(shù)表示x=x0+t△xy=y0+t△y0<=t<=1

△x=x1-x0

△y=y1-y0窗口邊界的四條邊分為兩類：始邊和終邊。梁友棟-Barsky算法線段的參數(shù)表示18求出P0P1與兩條始邊的交點參數(shù)t0,t1,令tl=max(t0,t1,0)，則tl即為三者中離p1最近的點的參數(shù)求出p0p1與兩條終邊的交點參數(shù)t2,t3,令tu=min(t2,t3,1)，則tu即為三者中離p0最近的點的參數(shù)若tu>tl,則可見線段區(qū)間[tl

,tu]t0t1t2t301梁友棟-Barsky算法：交點計算求出P0P1與兩條始邊的交點參數(shù)t0,t1,令tl=m19梁友棟-Barsky算法始邊和終邊的確定及交點計算：令QL=-△xDL=x0-xLQR=△xDR=xR-x0

QB=-△yDB=y0-yBQT=△yDT=yT-y0交點為ti=Di/

Qii=L,R,B,TQi<0ti為與始邊交點參數(shù)Qi>0ti為與終邊交點參數(shù)Qi=0Di<0時,線段不可見Di>0時,分析另一D,EFAB梁友棟-Barsky算法始邊和終邊的確定及交點計算：EFAB20梁友棟-Barsky算法當Qi=0時若Di<0時,線段不可見（如圖中AB，有QR=0，DR<0）若Di>0時,分析另一D,（如圖中的EF就是這種情況，它使QL=0，DL>0和QR=0，DR>0。這時由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交點，而讓EF和y=yT及y=yB的交點決定直線段上的可見部分。）

EFAB梁友棟-Barsky算法當Qi=0時EFAB21第5章 圖形變換與裁剪5.1齊次坐標5.2窗口到視區(qū)的變換5.3圖形幾何變換5.4三維圖形的基本問題

5.5平面幾何投影5.6直線段裁剪5.7多邊形裁剪第5章 圖形變換與裁剪5.1齊次坐標225.7多邊形裁剪錯覺：直線段裁剪的組合？新的問題：1）邊界不再封閉，需要用窗口邊界的恰當部分來封閉它，如何確定其邊界？5.7多邊形裁剪錯覺：直線段裁剪的組合？235.7多邊形裁剪2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何確定這些小多邊形的邊界？5.7多邊形裁剪2）一個凹多邊形可能被裁剪成幾個小的多邊形，24Sutherland-Hodgman算法分割處理策略：將多邊形關于矩形窗口的裁剪分解為多邊形關于窗口四邊所在直線的裁剪。流水線過程(左上右下)：前邊的結(jié)果是后邊的輸入。亦稱逐邊裁剪算法Sutherland-Hodgman算法分割處理策略：將多邊25Sutherland-Hodgman算法基本思想是一次用窗口的一條邊裁剪多邊形?？紤]窗口的一條邊以及延長線構成的裁剪線該線把平面分成兩個部分:可見一側(cè)；不可見一側(cè)多邊形的各條邊的兩端點S、P。它們與裁剪線的位置關系只有四種Sutherland-Hodgman算法基本思想是一次用窗口26Sutherland-Hodgman算法情況（1）僅輸出頂點P；情況（2）輸出0個頂點；情況（3）輸出線段SP與裁剪線的交點I；情況（4）輸出線段SP與裁剪線的交點I和終點PSutherland-Hodgman算法27

SP與裁剪線相交求SP與裁剪線的交點I輸出IP位于可見一側(cè)輸出頂點PYNYN

處理線段SP過程子框圖開始第一個頂點→S第一個頂點→F頂點輸入完畢輸入頂點P處理線段SPF→P處理線段SP結(jié)束YN逐邊裁剪法算法框圖P→SSP與裁剪線相交求SP與裁剪線的交點I輸出IP位于可見一側(cè)28Sutherland-Hodgman算法上述算法僅用一條裁剪邊對多邊形進行裁剪，得到一個頂點序列，作為下一條裁剪邊處理過程的輸入。對于每一條裁剪邊，算法框圖同上，只是判斷點在窗口哪一側(cè)以及求線段SP與裁剪邊的交點算法應隨之改變。Sutherland-Hodgman算法上述算法僅用一條裁剪29Sutherland-Hodgeman算法對凸多邊形應用本算法可以得到正確的結(jié)果，但是對凹多邊形的裁剪將如圖所示顯示出一條多余的直線。這種情況在裁剪后的多邊形有兩個或者多個分離部分的時候出現(xiàn)。因為只有一個輸出頂點表，所以表中最后一個頂點總是連著第一個頂點。解決這個問題有多種方法，一是把凹多邊形分割成若干個凸多邊形，然后分別處理各個凸多邊形。二是修改本算法，沿著任何一個裁剪窗口邊檢查頂點表，正確的連接頂點對。再有就是Weiler-Athenton算法。Sutherland-Hodgeman算法對凸多邊形應用本算30Sutherland-Hodgman算法思考：如何推廣到任意凸多邊形裁剪窗口？Sutherland-Hodgman算法思考：31Weiler-Athenton算法裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：主多邊形：被裁剪多邊形，記為A裁剪多邊形：裁剪窗口，記為BWeiler-Athenton算法32Weiler-Athenton算法多邊形頂點的排列順序（使多邊形區(qū)域位于有向邊的左側(cè)）外環(huán)：逆時針；內(nèi)環(huán)：順時針主多邊形和裁剪多邊形把二維平面分成兩部分。內(nèi)裁剪：A∩B外裁剪：A-B裁剪結(jié)果區(qū)域的邊界由A的部分邊界和B的部分邊界兩部分構成，并且在交點處邊界發(fā)生交替，即由A的邊界轉(zhuǎn)至B的邊界，或由B的邊界轉(zhuǎn)至A的邊界BAWeiler-Athenton算法多邊形頂點的排列順序（使多33Weiler-Athenton算法如果主多邊形與裁剪多邊形有交點，則交點成對出現(xiàn)，它們被分為如下兩類：進點：主多邊形邊界由此進入裁剪多邊形內(nèi)如，I1,I3,I5,I7,I9,I11出點：主多邊形邊界由此離開裁剪多邊形區(qū)域.如，I0,I2,I4,I6,I8,I10

Weiler-Athenton算法如果主多邊形與裁剪多邊形有34Weiler-Athenton算法1）建頂點表；2）求交點；3）裁剪……1、建立主多邊形和裁剪多邊的頂點表．2、求主多邊形和裁剪多邊形的交點，并將這些交點按順序插入兩多邊形的頂點表中。在兩多邊表形頂點表中的相同交點間建立雙向指針。3、裁剪:如果存在沒有被跟蹤過的交點，執(zhí)行以下步驟：

Weiler-Athenton算法1）建頂點表；1、建立主多35Weiler-Athenton算法Weiler-Athenton算法36Weiler-Athenton算法(1)建立空的裁剪結(jié)果多邊形的頂點表．(2)選取任一沒有被跟蹤過的交點為始點，將其輸出到結(jié)果多邊形頂點表中．(3)如果該交點為進點，跟蹤主多邊形邊邊界；否則跟蹤裁剪多邊形邊界．(4)跟蹤多邊形邊界，每遇到多邊形頂點，將其輸出到結(jié)果多邊形頂點表中，直至遇到新的交點．(5)將該交點輸出到結(jié)果多邊形頂點表中，并通過連接該交點的雙向指針改變跟蹤方向（如果上一步跟蹤的是主多邊形邊界，現(xiàn)在改為跟蹤裁剪多邊形邊界；如果上一步跟蹤裁剪多邊形邊界，現(xiàn)在改為跟蹤主多邊形邊界）．(6)重復(4)、(5)直至回到起點取I7為起點，所得裁剪結(jié)果多邊形I7I0q0I3I4I5I6I7。取I8為起點，所得裁剪結(jié)果多邊形為I8I9I10I11I2q2I1I8。Weiler-Athenton算法(1)建立空的裁剪37Weiler-Athenton算法交點的奇異情況處理1、與裁剪多邊形的邊重合的主多邊形的邊不參與求交點；2、對于頂點落在裁剪多邊形的邊上的主多邊形的邊，如果落在該裁剪邊的內(nèi)側(cè)，將該頂點算作交點；而如果這條邊落在該裁剪邊的外側(cè)，將該頂點不看作交點

Weiler-Athenton算法交點的奇異情況處理38精品課件！精品課件！39精品課件！精品課件！40作業(yè)(1)P156,題5(2)P156,題6作業(yè)(1)P156,題541裁剪裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外,以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個選擇過程稱為裁剪。圖形裁剪算法，直接影響圖形系統(tǒng)的效率。裁剪裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之42點的裁剪圖形裁剪中最基本的問題。假設窗口的左下角坐標為(xL,yB),右上角坐標為(xR,yT)，對于給定點P(x,y),則P點在窗口內(nèi)的條件是要滿足下列不等式：

xL<=x<=xR并且yB<=y<=yT

否則，P點就在窗口外。問題：對于任何多邊形窗口，如何判別？(xL,yB)(xR,yT)點的裁剪圖形裁剪中最基本的問題。(xL,yB)(xR,y435.6直線段裁剪直線段裁剪算法是復雜圖形裁剪的基礎。復雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。主要的四種算法直接求交算法Cohen-Sutherland算法中點算法梁友棟－barskey算法5.6直線段裁剪直線段裁剪算法是復雜圖形裁剪的基礎。復雜的曲445.6直線段裁剪裁剪線段與窗口的關系：(1)線段完全可見；(2)顯然不可見；(3)其它提高裁剪效率： 快速判斷情形(1)(2)， 對于情形(3)，設法減 少求交次數(shù)和每次求 交時所需的計算量。5.6直線段裁剪45直接求交算法直線與窗口邊都寫成參數(shù)形式，求參數(shù)值。直接求交算法直線與窗口邊都46Cohen-Sutherland裁剪基本思想：對于每條線段P1P2分為三種情況處理:（1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2。（2）若P1P2明顯在窗口外，則丟棄該線段。（3）若線段不滿足（1）或（2）的條件，則在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復上述處理。為快速判斷，采用如下編碼方法：Cohen-Sutherland裁剪基本思想：47實現(xiàn)方法：

將窗口邊線兩邊沿長，得到九個區(qū)域，每一個區(qū)域都用一個四位二進制數(shù)標識，直線的端點都按其所處區(qū)域賦予相應的區(qū)域碼，用來標識出端點相對于裁剪矩形邊界的位置。100100010101100000000100101000100110ABCDCohen-Sutherland裁剪實現(xiàn)方法：10010001010110000000048Cohen-Sutherland算法將區(qū)域碼的各位從右到左編號，則坐標區(qū)

域與各位的關系為：上下右左 XXXX

任何位賦值為1，代表端點落在相應的位置上，否則該位為0。若端點在剪取矩形內(nèi)，區(qū)域碼為0000。如果端點落在矩形的左下角，則區(qū)域碼為0101。Cohen-Sutherland算法將區(qū)域碼的各位從右到左編49Cohen-Sutherland算法一旦給定所有的線段端點的區(qū)域碼，就可以快速判斷哪條直線完全在剪取窗口內(nèi)，哪條直線完全在窗口外。所以得到一個規(guī)律：Cohen-Sutherland算法一旦給定所有的線段端點的50Cohen-Sutherland裁剪若P1P2完全在窗口內(nèi)code1=0,且code2=0,則“取”若P1P2明顯在窗口外code1&code2≠0，則“棄”

在交點處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復上述處理。

編碼線段裁剪Cohen-Sutherland裁剪若P1P2完全在窗口內(nèi)c51Cohen-Sutherland裁剪如何判定應該與窗口的哪條邊求交呢？ 編碼中對應位為1的邊。計算線段P1(x1,y1)P2(x2,y2)與窗口邊界的交點 if(LEFT&code!=0) { x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);} elseif(RIGHT&code!=0) { x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);} elseif(BOTTOM&code!=0){ y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);}elseif(TOP&code!=0){ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);}具體算法見p201Cohen-Sutherland裁剪如何判定應該與窗口的哪條52Cohen-Sutherland

直線裁剪算法小結(jié)本算法的優(yōu)點在于簡單，易于實現(xiàn)?？梢院唵蔚拿枋鰹閷⒅本€在窗口左邊的部分刪去，按左，右，下，上的順序依次進行，處理之后，剩余部分就是可見的了。在這個算法中求交點是很重要的，決定了算法的速度。另外，本算法對于其它形狀的窗口未必同樣有效。特點：用編碼方法可快速判斷線段的完全可見和顯然不可見。Cohen-Sutherland

直線裁剪算法小結(jié)本算法的53中點分割裁剪算法基本思想：從P0點出發(fā)找出離P0最近的可見點，和從P1點出發(fā)找出離P1最近的可見點。這兩個可見點的連線就是原線段的可見部分。與Cohen-Sutherland算法一樣首先對線段端點進行編碼，并把線段與窗口的關系分為三種情況，對前兩種情況，進行一樣的處理；對于第三種情況，用中點分割的方法求出線段與窗口的交點。A、B分別為距P0、P1最近的可見點，Pm為P0P1中點。

中點分割裁剪算法基本思想：從P0點出發(fā)找出離P0最近的可見點54中點分割算法-求線段與窗口的交點從P0出發(fā)找距離P0最近可見點采用中點分割方法先求出P0P1的中點Pm,若P0Pm不是顯然不可見的，并且P0P1在窗口中有可見部分，則距P0最近的可見點一定落在P0Pm上，所以用P0Pm代替P0P1；否則取PmP1代替P0P1。再對新的P0P1求中點Pm。重復上述過程，直到PmP1長度小于給定的控制常數(shù)為止，此時Pm收斂于交點。從P1出發(fā)找距離P1最近可見點采用上面類似方法。中點分割算法-求線段與窗口的交點從P0出發(fā)找距離P0最近可見55中點分割裁剪算法中點分割裁剪算法56對分辯率為2N*2N的顯示器，上述二分過程至多進行N次。主要過程只用到加法和除法運算，適合硬件實現(xiàn)，它可以用左右移位來代替乘除法，這樣就大大加快了速度。中點分割裁剪算法對分辯率為2N*2N的顯示器，上述二分過程至多進行N次。中點57

設要裁剪的線段是P0P1。P0P1和窗口邊界交于A,B,C,D四點，見圖。算法的基本思想是從A,B和P0三點中找出最靠近的P1點，圖中要找的點是P0。從C,D和P1中找出最靠近P0的點。圖中要找的點是C點。那么P0C就是P0P1線段上的可見部分。梁友棟-Barsky算法設要裁剪的線段是P0P1。P0P1和窗口邊界交于A58梁友棟-Barsky算法線段的參數(shù)表示x=x0+t△xy=y0+t△y0<=t<=1

△x=x1-x0

△y=y1-y0窗口邊界的四條邊分為兩類：始邊和終邊。梁友棟-Barsky算法線段的參數(shù)表示59求出P0P1與兩條始邊的交點參數(shù)t0,t1,令tl=max(t0,t1,0)，則tl即為三者中離p1最近的點的參數(shù)求出p0p1與兩條終邊的交點參數(shù)t2,t3,令tu=min(t2,t3,1)，則tu即為三者中離p0最近的點的參數(shù)若tu>tl,則可見線段區(qū)間[tl

,tu]t0t1t2t301梁友棟-Barsky算法：交點計算求出P0P1與兩條始邊的交點參數(shù)t0,t1,令tl=m60梁友棟-Barsky算法始邊和終邊的確定及交點計算：令QL=-△xDL=x0-xLQR=△xDR=xR-x0

QB=-△yDB=y0-yBQT=△yDT=yT-y0交點為ti=Di/

Qii=L,R,B,TQi<0ti為與始邊交點參數(shù)Qi>0ti為與終邊交點參數(shù)Qi=0Di<0時,線段不可見Di>0時,分析另一D,EFAB梁友棟-Barsky算法始邊和終邊的確定及交點計算：EFAB61梁友棟-Barsky算法當Qi=0時若Di<0時,線段不可見（如圖中AB，有QR=0，DR<0）若Di>0時,分析另一D,（如圖中的EF就是這種情況，它使QL=0，DL>0和QR=0，DR>0。這時由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交點，而讓EF和y=yT及y=yB的交點決定直線段上的可見部分。）

EFAB梁友棟-Barsky算法當Qi=0時EFAB62第5章 圖形變換與裁剪5.1齊次坐標5.2窗口到視區(qū)的變換5.3圖形幾何變換5.4三維圖形的基本問題

5.5平面幾何投影5.6直線段裁剪5.7多邊形裁剪第5章 圖形變換與裁剪5.1齊次坐標635.7多邊形裁剪錯覺：直線段裁剪的組合？新的問題：1）邊界不再封閉，需要用窗口邊界的恰當部分來封閉它，如何確定其邊界？5.7多邊形裁剪錯覺：直線段裁剪的組合？645.7多邊形裁剪2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何確定這些小多邊形的邊界？5.7多邊形裁剪2）一個凹多邊形可能被裁剪成幾個小的多邊形，65Sutherland-Hodgman算法分割處理策略：將多邊形關于矩形窗口的裁剪分解為多邊形關于窗口四邊所在直線的裁剪。流水線過程(左上右下)：前邊的結(jié)果是后邊的輸入。亦稱逐邊裁剪算法Sutherland-Hodgman算法分割處理策略：將多邊66Sutherland-Hodgman算法基本思想是一次用窗口的一條邊裁剪多邊形。考慮窗口的一條邊以及延長線構成的裁剪線該線把平面分成兩個部分:可見一側(cè)；不可見一側(cè)多邊形的各條邊的兩端點S、P。它們與裁剪線的位置關系只有四種Sutherland-Hodgman算法基本思想是一次用窗口67Sutherland-Hodgman算法情況（1）僅輸出頂點P；情況（2）輸出0個頂點；情況（3）輸出線段SP與裁剪線的交點I；情況（4）輸出線段SP與裁剪線的交點I和終點PSutherland-Hodgman算法68

SP與裁剪線相交求SP與裁剪線的交點I輸出IP位于可見一側(cè)輸出頂點PYNYN

處理線段SP過程子框圖開始第一個頂點→S第一個頂點→F頂點輸入完畢輸入頂點P處理線段SPF→P處理線段SP結(jié)束YN逐邊裁剪法算法框圖P→SSP與裁剪線相交求SP與裁剪線的交點I輸出IP位于可見一側(cè)69Sutherland-Hodgman算法上述算法僅用一條裁剪邊對多邊形進行裁剪，得到一個頂點序列，作為下一條裁剪邊處理過程的輸入。對于每一條裁剪邊，算法框圖同上，只是判斷點在窗口哪一側(cè)以及求線段SP與裁剪邊的交點算法應隨之改變。Sutherland-Hodgman算法上述算法僅用一條裁剪70Sutherland-Hodgeman算法對凸多邊形應用本算法可以得到正確的結(jié)果，但是對凹多邊形的裁剪將如圖所示顯示出一條多余的直線。這種情況在裁剪后的多邊形有兩個或者多個分離部分的時候出現(xiàn)。因為只有一個輸出頂點表，所以表中最后一個頂點總是連著第一個頂點。解決這個問題有多種方法，一是把凹多邊形分割成若干個凸多邊形，然后分別處理各個凸多邊形。二是修改本算法，沿著任何一個裁剪窗口邊檢查頂點表，正確的連接頂點對。再有就是Weiler-Athenton算法。Sutherland-Hodgeman算法對凸多邊形應用本算71Sutherland-Hodgman算法思考：如何推廣到任意凸多邊形裁剪窗口？Sutherland-Hodgman算法思考：72Weiler-Athenton