線段與多邊形的裁剪

1、一、實驗?zāi)繕?. 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 線段裁剪、Liang_Barsky 線段裁剪

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

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

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

5、新編碼得到C1，接下來算法轉(zhuǎn)回第2步繼續(xù)對其它邊界進行判別。2 .Liang Barsky 線段裁剪我們知道，一條兩端點為P1（x1，y1）、P2（x2，y2）的線段可以用參數(shù)方程形式表示：式中，x=x2-x1，y=y2-y1，參數(shù)u在01之間取值，P（x，y）代表了該線段上的一個點，其值由參數(shù)u確定，由公式可知，當(dāng)u=0時，該點為P1（x1，y1），當(dāng)u=1時，該點為P2（x2，y2）。如果點P（x，y）位于由坐標（xwmin，ywmin）和（xwmax，ywmax）所確定的窗口內(nèi)，那么下式成立：這四個不等式可以表示為：其中，p、q定義為：從（3-12）式可以知道：任何平行于窗口某邊界的直線

6、，其pk=0，k值對應(yīng)于相應(yīng)的邊界（k=1，2，3，4對應(yīng)于左、右、下、上邊界）。如果還滿足qk<0，則線段完全在邊界外，應(yīng)舍棄該線段。如果pk=0并且qk0，則線段平行于窗口某邊界并在窗口內(nèi)，見圖中所示。公式（3-12）式還告訴我們：1、當(dāng)pk<0時，線段從裁剪邊界延長線的外部延伸到內(nèi)部；2、當(dāng)pk>0時，線段從裁剪邊界延長線的內(nèi)部延伸到外部；當(dāng)x0時，對于左邊界p1<0（p1=-x），線段從左邊界的外部到內(nèi)部；對于右邊界p2>0（p2=x），線段從右邊界的內(nèi)部到外部。當(dāng)y<0時，對于下邊界p3>0（p3=-y），線段從下邊界的內(nèi)部到外部；對于上邊界

7、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的值由線段從內(nèi)到外遇到的矩形邊界所決定（pk>0），對這些邊界計算rk=qk/pk，u2取0和各個r值之中的最小值。3、如果u1>u2，則線段完全落在裁剪窗口之外，應(yīng)當(dāng)被舍棄；否則，被裁剪線段的端點可以由u1和u2計算出來。3 .Suth

8、erland Hodgeman 多邊形裁剪每次用窗口的一條邊界(包括延長線)對要裁剪的多邊形進行裁剪，裁剪時，順序地測試多邊形各頂點，保留邊界內(nèi)側(cè)的頂點，刪除外側(cè)的頂點，同時，適時地插入新的頂點：即交點和窗口頂點，從而得到一個新的多邊形頂點序列。然后以此新的頂點序列作為輸入，相對第二條窗邊界線進行裁剪，又得到一個更新的多邊形頂點序列。依次下去，相對于第三條、第四條邊界線進行裁剪，最后輸出的多邊形頂點序列即為所求的裁剪好了的多邊形。如下圖所示：新的多邊形頂點序列產(chǎn)生規(guī)則：在用窗口一條邊界及其延長線裁剪一個多邊形時，該邊界線把平面分成兩個部分：一部分稱為邊界內(nèi)側(cè)；另一部分稱為邊界外側(cè)。如下圖所示,

9、依序考慮多邊形的各條邊。假設(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è)。則交點Q保存到新多邊形中。4. S、P均在外側(cè)。則沒有點被保存到新多邊形中。三、實驗步驟 1. 打開程序模板，在資源視圖中點擊cgdemo，在下拉文件中點擊menu，然后雙擊IDR_MAINFRAME，在右邊打開的窗口中分別添加Cohen_Sutherland 線段裁剪、Liang_Barsky 線段裁剪、Sutherl

10、and_Hodgeman 多邊形裁剪菜單按鈕并編輯；2. 在解決方案資源管理器中，點擊cgdemo，在下拉文件Header Files中點擊cgdemoView.h，在cgdemoView.h頭文件中添加Cohen_Sutherland 線段裁剪、Liang_Barsky x線段裁剪、Sutherland_Hodgeman 多邊形裁剪的一些定義；再雙擊下拉文件Source Files中的cgdemoView.cpp，在標準打印命令中分別添加ON_COMMAND(ID_COHEN_SUTHERLAND, &CcgdemoView:OnCohenSutherland)ON_COMMAND(

11、ID_LIANG_BARSKY, &CcgdemoView:OnLiangBarsky)ON_COMMAND(ID_SUTHERLAND_HODGEMAN,&CcgdemoView:OnSutherlandHodgeman)3. 在CcgdemoView 繪制中分別添加繪制遞歸種子填充、簡單種子填充、掃描線種子填充，區(qū)域圖案填充的else if語句；在CcgdemoView 消息處理程序中添加Cohen_Sutherland 線段裁剪、Liang_Barsky x線段裁剪、Sutherland_Hodgeman 多邊形裁剪的case語句；CcgdemoView 事件處理程序中分

12、別定義了：void CcgdemoView:OnCohenSutherland()/ TODO: Add your command handler code herem_drawstyle = COHEN_SUTHERLAND;Invalidate(true);void CcgdemoView:OnLiangBarsky()/ TODO: Add your command handler code herem_drawstyle = LIANG_BARSKY;Invalidate(true);void CcgdemoView:OnSutherlandHodgeman()/ TODO: Add

13、your command handler code herem_drawstyle = SUTHERLAND_HODGEMAN;Invalidate(true);4. 在cgdemoView.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

14、SutherlandHodgeman(CDC* pDC, CArray<CPoint,CPoint&>&arr_pt);5. 運行調(diào)試程序。四、實驗遇到的問題及其解決方法(1) 在調(diào)試程序時發(fā)現(xiàn)程序運行完并正確達到裁減效果，可是窗口點擊放大后，裁剪畫面消失；為此將畫圖的程序語句放在裁剪程序框架外，以解決此問題。(2) 在CohenSutherland 線段裁剪程序編寫時，由于k = float (P_end.y - P_begin.y) / float (P_end.x - P_begin.x);求斜率的程序語句未添加float 將k 整型，使得線段短點逐漸靠近裁剪

15、框交點的過程中，誤差變化越來越大，裁減效果不是預(yù)期想要的效果。(3) 在LiangBarsky 線段裁剪程序編寫時，在根據(jù)最后得到的U1和U2求新端點坐標的程序語句編寫如下：P_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);由于求新的裁剪后線段終點坐

16、標時，受到上面已經(jīng)改變的新的起點坐標的影響，使得第二個點求的不正確，在程序運行效果時候表現(xiàn)為：第二個裁剪點明顯不符合預(yù)期的效果。后更改程序如下，則求新的起始點和新的終點坐標互不影響，程序運行正常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)point_pr