線段與多邊形的裁剪題庫

1、、實驗目標1. CohenSutherland 線段裁剪；2. LiangBarsky 線段裁剪；3. SutherlandHodgeman 多邊形裁剪；、實驗內容、實驗內容在給定的 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ù)編碼可以迅速地判明全部在窗口內的線段和全部在某邊界外側的線段。只有不屬于這兩種情況的線段， 才需要求出線段與窗口邊界的交點， 求出交點后， 舍去窗外部分。對剩余部分，把它作為新的線段看待，又從頭開始考慮。兩遍循 環(huán)之后，就能確定該線段是部分截留下來，還是全部舍棄。編碼延長裁剪邊框將二維平面分成九個區(qū)域， 每個區(qū)域各用一個四位二進制代

3、碼標識。各區(qū)代碼值如圖中所示。四位二進制代碼的編碼規(guī)則是：(1) 第一位置 1：區(qū)域在左邊界外側 (2) 第二位置 1：區(qū)域在右邊界外側(3) 第三位置 1：區(qū)域在下邊界外側 (4) 第四位置 1：區(qū)域在上邊界外側81001 ! 1000 ! 1010代碼XXXX位數(shù)第四位第三位第二位第一位某m上下右左csS法分岡編碼圖0101 ! 0100 ! 0110000100000010裁剪窗口內端點為P1 (x1 ,（包括邊界上）的區(qū)域，四位二進制代碼均為0。設線段的兩個y1）和P2 （x2，y2），根據(jù)上述規(guī)則，可以求出 P1和P2所在區(qū)域的分區(qū)代碼C1 和 C2。判別根據(jù)C1和C2的具體值，可以

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

5、側，按照下面的求交公式，進行對左邊界的求交運算。依次類推，對位于右、 下、上邊界外側的判別，應將條件式中的0001分別改為0010、0100、1000即可。求出交點P后，用P仁P來舍去線段的窗外部分，并對 P1重新編碼得到C1，接下來算法轉回第2步繼續(xù)對其它邊界進行判別。與上邊界求交點公式，V =. (e -X,) + 每L 兒北與下邊界求交點公式：yPniin1V X = 口- (丫2 Xj) + X|. 乃M與右邊界求交點公式=1 y =-m) + H 可畫與左邊界求交點公式：工=Tnin1 y = 5 - 片)+ J1 兀一並2 .Liang Barsky 線段裁剪我們知道，一條兩端點為

6、 Pi (xi,yi)、P2 ( X2, y2)的線段可以用參數(shù)方程形式表示:0去芝1 (3-9)滬叫+ U- a尸七1+ y= y/ U = yf式中， x=x-xi, y=y-yi，參數(shù)u在01之間取值，P (x, y)代表了該 線段上的一個點，其值由參數(shù)u確定，由公式可知，當u=0時，該點為Pi (xi，y1)，當u = 1時，該點為P2 (X2, y2)。如果點P (X, y)位于由坐標(XWmin , yWmin)和(XWmax, yWmax)所確定的窗口內，那么下式成立：(3-10)這四個不等式可以表示為:卜Wq#，k=l, 2J 3, 4C3-11)其中，p、q定義為：p產(chǎn)比q產(chǎn)

7、嚴亓 P2= W屯二垃粘住P尸妙q尹廠yw加 P尸注叮(3-12)從(3-12)式可以知道：任何平行于窗口某邊界的直線，其Pk=0, k值對應于相應的邊界(k=1，2，3，4對應于左、右、下、上邊界)。如果還滿足 qkv0, 則線段完全在邊界外，應舍棄該線段。如果pk=0并且qk0則線段平行于窗口某邊界并在窗口內，見圖中所示。公式(3-12 )式還告訴我們：1、當pk0時，線段從裁剪邊界延長線的內部延伸到外部;y.E A Xp,=0的情況對于左邊界pi0(p2= Ax)，線段從左邊界的外部到內部;，線段從右邊界的內部到外部。當Ay0(p3=- Ay（p4=Ay）當PK工0寸，可以計算出參數(shù)U對

8、于上邊界P40，線段從下邊界的內部到外部;，線段從上邊界的外部到內部。的值，它對應于無限延伸的直線與延伸的窗口邊界k的交點，即:3-13)對于每條直線，可以計算出參數(shù)U1和U2,該值定義了位于窗口內的線段部分:1、ui的值由線段從外到內遇到的矩形邊界所決定（pk0） 算rk=qk/pk, U2取0和各個r值之中的最小值。3、如果U1U2，則線段完全落在裁剪窗口之外，應當被舍棄;，對這些邊界計，對這些邊界計否則，被裁剪線段的端點可以由U1和U2計算出來。3 .Sutherland Hodgeman 多邊形裁剪每次用窗口的一條邊界（包括延長線）對要裁剪的多邊形進行裁剪，裁剪時, 順序地測試多邊形各

9、頂點，保留邊界內側的頂點，刪除外側的頂點，同時，適時 地插入新的頂點：即交點和窗口頂點，從而得到一個新的多邊形頂點序列。 然后以此新的頂點序列作為輸入，相對第二條窗邊界線進行裁剪，又得到一個更新的 多邊形頂點序列。依次下去，相對于第三條、第四條邊界線進行裁剪，最后輸出的多邊形頂點序列即為所求的裁剪好了的多邊形。如下圖所示:（a）多邊形與窗口 （匕）左裁剪 （C）上裁剪 Cd）右裁剪 （e）下裁剪新的多邊形頂點序列產(chǎn)生規(guī)則:在用窗口一條邊界及其延長線裁剪一個多邊形時， 該邊界線把平面分成兩個 部分：一部分稱為邊界內側；另一部分稱為邊界外側。如下圖所示，依序考慮多邊形的各條邊。假設當前處理的多邊形

10、的邊為SP（箭頭表示順序關系，S為前一點，P為當前點），邊SP與裁剪線的位置關系只1. S有下面四種情況:在外側，P在內側。則交點Q當前點P保存到新多邊形中2. S、P均在內側，則當前點P保存到新多邊形中。3. S在內側，P在外側。則交點Q保存到新多邊形中。4. S、P均在外側。則沒有點被保存到新多邊形中。外內 保存：Q、P(包)惜況1保存；P(b)情況2匚JuII內匚外 保存：Q(C)惜況3外= 外 不保存(d)情況4按照窗口左辺界連續(xù)處理多邊形頂點對三、實驗步驟1.打開程序模板，在資源視圖中點擊 cgdemo,在下拉文件中點擊 menu,然后雙擊IDR_MAINFRAME，在右邊打開的窗口

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

12、THERLAND, & CcgdemoView:。nCohe nSutherla nd) ON_COMMAND(ID_LIANG_BARSK Y, & CcgdemoView:O nLia ngBarsky) ON_COMMAND(ID_SUTHERLAND_HODGEMAN, &CcgdemoView:O nSutherla ndHodg ema n)3. 在CcgdemoView繪制中分別添加繪制遞歸種子填充、簡單種子填充、掃描線種子填充，區(qū)域圖案填充的 else if語句；在CcgdemoView消息處理程序中添力卩Cohen_Sutherland線段裁剪、Liang_Barsky x

13、線段裁剪、Sutherland_Hodgeman多邊形裁剪的case語句；CcgdemoView事件處理程序中分別定義了：void CcgdemoView:O nCohe nSutherla nd()/ TODO: Add your comma nd han dler code here m_drawstyle = COHEN_SUTHERLAND;In validate(true);void CcgdemoView:OnLiangBarsky()/ TODO: Add your command handler code here m_drawstyle = LIANG_BARSKY;Inva

14、lidate(true);void CcgdemoView:OnSutherlandHodgeman()/ TODO: Add your command handler code here m_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*

15、 pDC, CPoint P_begin, CPoint P_end);Suthela nd_Hodgeman多邊形裁剪程序：void SutherlandHodgeman(CDC* pDC, CArray&arr_pt);5. 運行調試程序。四、實驗遇到的問題及其解決方法(1) 在調試程序時發(fā)現(xiàn)程序運行完并正確達到裁減效果，可是窗口點擊放 大后，裁剪畫面消失； 為此將畫圖的程序語句放在裁剪程序框架外， 以解決此問 題。(2) 在 CohenSutherland 線段裁剪程序編寫時，由于float (P_end.x - P_begin.x);k = float (P_end.y - P_beg

16、in.y) /求斜率的程序語句未添加 float 將 k 整型，使得線段短點逐漸靠近裁剪框 交點的過程中，誤差變化越來越大，裁減效果不是預期想要的效果。 在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

17、- u2 * (P_begin.y - P_end.y);由于求新的裁剪后線段終點坐標時， 受到上面已經(jīng)改變的新的起點坐標的影 響，使得第二個點求的不正確， 在程序運行效果時候表現(xià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)在Sutherla ndHodgeman多邊形裁剪的程序編寫時