線段與多邊形的裁剪

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

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

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

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

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

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

7、p4<0（p4=y），線段從上邊界的外部到內(nèi)部。當(dāng)pK0時(shí)，可以計(jì)算出參數(shù)u的值，它對(duì)應(yīng)于無限延伸的直線與延伸的窗口邊界k的交點(diǎn)，即：對(duì)于每條直線，可以計(jì)算出參數(shù)u1和u2，該值定義了位于窗口內(nèi)的線段部分：1、u1的值由線段從外到內(nèi)遇到的矩形邊界所決定（pk<0），對(duì)這些邊界計(jì)算rk=qk/pk，u1取0和各個(gè)r值之中的最大值。2、u2的值由線段從內(nèi)到外遇到的矩形邊界所決定（pk>0），對(duì)這些邊界計(jì)算rk=qk/pk，u2取0和各個(gè)r值之中的最小值。3、如果u1>u2，則線段完全落在裁剪窗口之外，應(yīng)當(dāng)被舍棄；否則，被裁剪線段的端點(diǎn)可以由u1和u2計(jì)算出來。3 .Suth

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

9、依序考慮多邊形的各條邊。假設(shè)當(dāng)前處理的多邊形的邊為SP(箭頭表示順序關(guān)系，S為前一點(diǎn)，P為當(dāng)前點(diǎn))，邊SP與裁剪線的位置關(guān)系只有下面四種情況：1. S在外側(cè)，P在內(nèi)側(cè)。則交點(diǎn)Q、當(dāng)前點(diǎn)P保存到新多邊形中2. S、P均在內(nèi)側(cè)，則當(dāng)前點(diǎn)P保存到新多邊形中。3. S在內(nèi)側(cè)，P在外側(cè)。則交點(diǎn)Q保存到新多邊形中。4. S、P均在外側(cè)。則沒有點(diǎn)被保存到新多邊形中。三、實(shí)驗(yàn)步驟 1. 打開程序模板，在資源視圖中點(diǎn)擊cgdemo，在下拉文件中點(diǎn)擊menu，然后雙擊IDR_MAINFRAME，在右邊打開的窗口中分別添加Cohen_Sutherland 線段裁剪、Liang_Barsky 線段裁剪、Sutherl

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

11、ID_LIANG_BARSKY, &CcgdemoView:OnLiangBarsky)ON_COMMAND(ID_SUTHERLAND_HODGEMAN,&CcgdemoView:OnSutherlandHodgeman)3. 在CcgdemoView 繪制中分別添加繪制遞歸種子填充、簡(jiǎn)單種子填充、掃描線種子填充，區(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. 運(yùn)行調(diào)試程序。四、實(shí)驗(yàn)遇到的問題及其解決方法(1) 在調(diào)試程序時(shí)發(fā)現(xiàn)程序運(yùn)行完并正確達(dá)到裁減效果，可是窗口點(diǎn)擊放大后，裁剪畫面消失；為此將畫圖的程序語句放在裁剪程序框架外，以解決此問題。(2) 在CohenSutherland 線段裁剪程序編寫時(shí)，由于k = float (P_end.y - P_begin.y) / float (P_end.x - P_begin.x);求斜率的程序語句未添加float 將k 整型，使得線段短點(diǎn)逐漸靠近裁剪

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

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