線段與多邊形的裁剪題庫

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

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

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

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

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

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

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

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

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

10、。則交點 Q保存到新多邊形中。4. S 、P 均在外側(cè)。則沒有點被保存到新多邊形中。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，在標(biāo)準(zhǔn)打印命令中分別添加ON_COMMAND(ID_COHEN_SUTHERLAND, &CcgdemoView:OnCohenSutherland)ON_COMMAND(ID_LIANG_BARSKY, &CcgdemoView:OnLiangBarsky)ON_COMMAND(ID_SUTHERLAND_HODGEMAN,&CcgdemoView:OnSutherlandHodgeman

12、)3. 在 CcgdemoView 繪制中分別添加繪制遞歸種子填充、簡單種子填充、掃描線種子填充，區(qū)域圖案填充的 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. 運行調(diào)試程序。四、實驗遇到的

15、問題及其解決方法(1) 在調(diào)試程序時發(fā)現(xiàn)程序運行完并正確達(dá)到裁減效果，可是窗口點擊放大后，裁剪畫面消失； 為此將畫圖的程序語句放在裁剪程序框架外，以解決此問題。(2)在 CohenSutherland線段裁剪程序編寫時，由于k = float(P_end.y - P_begin.y) /float(P_end.x - P_begin.x);求斜率的程序語句未添加float將 k 整型，使得線段短點逐漸靠近裁剪框交點的過程中，誤差變化越來越大，裁減效果不是預(yù)期想要的效果。(3) 在 LiangBarsky 線段裁剪程序編寫時， 在根據(jù)最后得到的 U1 和 U2求新端點坐標(biāo)的程序語句編寫如下：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由于求新的裁剪后線段終點坐標(biāo)時， 受到上面已經(jīng)改變的新的起點坐標(biāo)的影響，使得第二個點求的不正確， 在程序運行效果時候表現(xiàn)為： 第二個裁剪點明顯不符合預(yù)期的效果。后更改程序如下，則求新的起始點和新的終點坐標(biāo)互不影響，程序運行正常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