1、一、實驗目標1. CohenSutherland 線段裁剪；2. LiangBarsky 線段裁剪；3. SutherlandHodgeman 多邊形裁剪；二、實驗內容一、實驗內容在給定的 MFC 程序模板中添加Cohen_Sutherland 線段裁剪、Liang_Barsky x線段裁 剪、 Sutherland_Hodgeman 多邊形裁剪， 生成 新的程 序窗口中要有Cohen_Sutherland 線段裁剪、Liang_Barsky x 線段裁剪、Sutherland_Hodgeman 多邊形裁剪的菜單 按鈕 ，點 擊按 鈕分 別彈出Cohen_Sutherland 線段裁剪、Lia

2、ng_Barsky 線段裁剪、 Sutherland_Hodgeman 多邊形裁剪的窗口， 通過點擊鼠標操作實現裁剪框和線段以及多邊形的定義和裁剪。二、實驗原理1. Cohen_Sutherland 線段裁剪該算法也稱為編碼算法，首先對線段的兩個端點按所在的區域進行分區編碼，根據編碼可以迅速地判明全部在窗口內的線段和全部在某邊界外側的線段。只有不屬于這兩種情況的線段， 才需要求出線段與窗口邊界的交點， 求出交點后，舍去窗外部分。對剩余部分，把它作為新的線段看待，又從頭開始考慮。兩遍循環之后，就能確定該線段是部分截留下來，還是全部舍棄。編碼延長裁剪邊框將二維平面分成九個區域， 每個區域各用一個四

3、位二進制代碼標識。各區代碼值如圖中所示。四位二進制代碼的編碼規則是：(1) 第一位置 1：區域在左邊界外側 (2) 第二位置 1：區域在右邊界外側(3) 第三位置 1：區域在下邊界外側(4) 第四位置 1：區域在上邊界外側1裁剪窗口內（包括邊界上）的區域，四位二進制代碼均為 0。設線段的兩個端點為 P1（x1，y1）和 P2（x2，y2），根據上述規則，可以求出 P1 和 P2 所在區域的分區代碼 C1 和 C2。判別根據 C1 和 C2 的具體值，可以有三種情況：（1）C1=C20，表明兩端點全在窗口內，因而整個線段也在窗內，應予保留。（2）C1&C20（兩端點代碼按位作邏輯乘不為0

4、），即 C1 和 C2 至少有某一位同時為 1，表明兩端點必定處于某一邊界的同一外側，因而整個線段全在窗外，應予舍棄。（3）不屬于上面兩種情況，均需要求交點。求交點假設算法按照：左、右、下、上邊界的順序進行求交處理，對每一個邊界求完交點，并相關處理后，算法轉向第 2 步，重新判斷，如果需要接著進入下一邊界的處理。為了規范算法，令線段的端點 P1 為外端點，如果不是這樣，就需要 P1 和 P2 交換端點。當條件 (C1&0001 0) 成立時，表示端點 P1 位于窗口左邊界外側，按照下面的求交公式，進行對左邊界的求交運算。依次類推，對位于右、下、上邊界外側的判別， 應將條件式中的0001

5、 分別改為 0010、0100、1000 即可。求出交點 P 后，用 P1=P來舍去線段的窗外部分，并對P1 重新編碼得到 C1，接下來算法轉回第2 步繼續對其它邊界進行判別。22 .Liang Barsky 線段裁剪我們知道，一條兩端點為P1（x1，y1）、 P2（x2，y2）的線段可以用參數方程形式表示：式中，x=x21 ，y=y21，參數 u 在 01 之間取值， P（ x，y）代表了該-x-y線段上的一個點，其值由參數u 確定，由公式可知，當u=0 時，該點為 P1（ x1，y1），當 u=1 時，該點為 P2（x2， y2）。如果點 P（x， y）位于由坐標（ xwmin ，ywmi

6、n）和（ xw max， ywmax）所確定的窗口內，那么下式成立：這四個不等式可以表示為：其中， p、q 定義為：從（3-12）式可以知道：任何平行于窗口某邊界的直線，其pk，k值對應=0于相應的邊界（ k=1，2， 3，4 對應于左、右、下、上邊界）。如果還滿足qk ，<0則線段完全在邊界外，應舍棄該線段。如果pk=0并且 k0，則線段平行于窗口q某邊界并在窗口內，見圖中所示。公式（3-12）式還告訴我們：31、當 pk<0 時，線段從裁剪邊界延長線的外部延伸到內部；2、當 pk>0 時，線段從裁剪邊界延長線的內部延伸到外部；當 x0時，對于左邊界 p1<0（ p1

7、=-x），線段從左邊界的外部到內部；對于右邊界 p2>0（ p2=x），線段從右邊界的內部到外部。當 y<0 時，對于下邊界 p3>0（ p3=-y），線段從下邊界的內部到外部；對于上邊界 p4<0（ p4=y），線段從上邊界的外部到內部。當 pK0時，可以計算出參數 u 的值，它對應于無限延伸的直線與延伸的窗口邊界 k 的交點，即：對于每條直線，可以計算出參數u1 和 u2，該值定義了位于窗口內的線段部分：1、u1 的值由線段從外到內遇到的矩形邊界所決定（pk<0），對這些邊界計算 rk=qk/pk，u1 取 0 和各個 r 值之中的最大值。2、u2 的值由線段

8、從內到外遇到的矩形邊界所決定（pk>0），對這些邊界計算 rk=qk/pk，u2 取 0 和各個 r 值之中的最小值。3、如果 u1>u2，則線段完全落在裁剪窗口之外，應當被舍棄；否則，被裁剪線段的端點可以由u1 和 u2 計算出來。3 .Sutherland Hodgeman 多邊形裁剪每次用窗口的一條邊界 ( 包括延長線 ) 對要裁剪的多邊形進行裁剪，裁剪時，順序地測試多邊形各頂點，保留邊界內側的頂點，刪除外側的頂點，同時，適時地插入新的頂點： 即交點和窗口頂點， 從而得到一個新的多邊形頂點序列。然后4以此新的頂點序列作為輸入， 相對第二條窗邊界線進行裁剪， 又得到一個更新的多

9、邊形頂點序列。依次下去，相對于第三條、第四條邊界線進行裁剪，最后輸出的多邊形頂點序列即為所求的裁剪好了的多邊形。如下圖所示：新的多邊形頂點序列產生規則：在用窗口一條邊界及其延長線裁剪一個多邊形時， 該邊界線把平面分成兩個部分：一部分稱為邊界內側；另一部分稱為邊界外側。如下圖所示 , 依序考慮多邊形的各條邊。假設當前處理的多邊形的邊為SP(箭頭表示順序關系， S 為前一點， P 為當前點 ) ，邊 SP與裁剪線的位置關系只有下面四種情況：1. S 在外側， P 在內側。則交點 Q、當前點 P 保存到新多邊形中2. S 、P 均在內側，則當前點 P 保存到新多邊形中。3. S 在內側， P 在外側

10、。則交點 Q保存到新多邊形中。4. S 、P 均在外側。則沒有點被保存到新多邊形中。5三、實驗步驟1. 打開程序模板，在資源視圖中點擊 cgdemo，在下拉文件中點擊 menu，然后雙擊 IDR_MAINFRAME ，在右邊打開的窗口中分別添加 Cohen_Sutherland線段裁剪、 Liang_Barsky 線段裁剪、 Sutherland_Hodgeman 多邊形裁剪菜單按鈕并編輯；2. 在解決方案資源管理器中，點擊 cgdemo，在下拉文件 Header Files中點擊 cgdemoView.h，在 cgdemoView.h 頭文件中添加 Cohen_Sutherland 線段裁剪

11、、Liang_Barsky x 線段裁剪、 Sutherland_Hodgeman 多邊形裁剪的一些定義；再雙擊下拉文件 Source Files中的 cgdemoView.cpp，在標準打印命令中分別添加ON_COMMAND(ID_COHEN_SUTHERLAND, &CcgdemoView:OnCohenSutherland)ON_COMMAND(ID_LIANG_BARSKY, &CcgdemoView:OnLiangBarsky)ON_COMMAND(ID_SUTHERLAND_HODGEMAN,&CcgdemoView:OnSutherlandHodgeman

12、)3. 在 CcgdemoView 繪制中分別添加繪制遞歸種子填充、簡單種子填充、掃描線種子填充，區域圖案填充的 else if 語句；在 CcgdemoView 消息處理程序中 添 加 Cohen_Sutherland 線 段 裁 剪 、 Liang_Barsky x 線 段 裁 剪 、Sutherland_Hodgeman 多邊形裁剪的 case 語句； CcgdemoView 事件處理程序中分別定義了：void CcgdemoView:OnCohenSutherland()/ TODO: Add your command handler code herem_drawstyle = CO

13、HEN_SUTHERLAND;Invalidate(true);6void CcgdemoView:OnLiangBarsky()/ TODO: Add your command handler code here m_drawstyle = LIANG_BARSKY; Invalidate(true);void CcgdemoView:OnSutherlandHodgeman()/ TODO: Add your command handler code here m_drawstyle = SUTHERLAND_HODGEMAN; Invalidate(true);4. 在 cgdemoVi

14、ew.cpp 的最后分別編寫Cohen_Sutherland 線段裁剪的程序：void CohenSutherland(CDC* pDC, CPoint P_begin, CPoint P_end);Liang_Barsky 線段裁剪的程序：void LiangBarsky(CDC* pDC, CPoint P_begin, CPoint P_end);Sutheland_Hodgeman多邊形裁剪程序：void SutherlandHodgeman(CDC* pDC, CArray<CPoint,CPoint&>&arr_pt);5. 運行調試程序。四、實驗遇到的

15、問題及其解決方法(1) 在調試程序時發現程序運行完并正確達到裁減效果，可是窗口點擊放大后，裁剪畫面消失； 為此將畫圖的程序語句放在裁剪程序框架外，以解決此問題。(2)在 CohenSutherland線段裁剪程序編寫時，由于k = float(P_end.y - P_begin.y) /float(P_end.x - P_begin.x);求斜率的程序語句未添加float將 k 整型，使得線段短點逐漸靠近裁剪框交點的過程中，誤差變化越來越大，裁減效果不是預期想要的效果。(3) 在 LiangBarsky 線段裁剪程序編寫時， 在根據最后得到的 U1 和 U2求新端點坐標的程序語句編寫如下：P_

16、begin.x=P_begin.x - u1 * (P_begin.x - P_end.x);P_begin.y=P_begin.y - u1 * (P_begin.y - P_end.y);P_end.x=P_begin.x - u2 * (P_begin.x - P_end.x);P_end.y=P_begin.y - u2 * (P_begin.y - P_end.y);7由于求新的裁剪后線段終點坐標時， 受到上面已經改變的新的起點坐標的影響，使得第二個點求的不正確， 在程序運行效果時候表現為： 第二個裁剪點明顯不符合預期的效果。后更改程序如下，則求新的起始點和新的終點坐標互不影響，程序運行正常P1.x=P_begin.x - u1 * (P_begin.x - P_end.x);P1.y=P_begin.y - u1 * (P_begin.y - P_end.y);P2.x=P_begin.x - u2 * (P_begin.x - P_end.x);P2.y=P_begin.y - u2 * (P_begin.y - P_end.y);(4) 在SutherlandHodgeman 多邊形裁剪的程序編寫時：if (i =0)poin