改進(jìn)cohen-sutherland線段裁剪算法

《改進(jìn)cohen-sutherland線段裁剪算法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、改進(jìn)的cohen-sutherland線段裁剪算法王艷娟肖剛強(qiáng)任洪海（大連交通大學(xué)軟件學(xué)院116052）摘要：針對目前的conhen-sutherland線段裁剪算法不能有效地判斷出線段是否完全在窗口外的問題，提出了一種改進(jìn)的conhen-sutherland線段裁剪算法，通過添加一個判斷條件，使得所有完全位于窗口外的線段都能快速的過濾出來，從而減少了求交點的次數(shù)，提高了運(yùn)算效率。關(guān)鍵詞：裁剪算法，cohen-sutherland線裁剪算法，求交運(yùn)算0．引言線段裁剪是復(fù)雜圖元裁剪的基礎(chǔ)，各種非線性邊界都可以用

2、直線段來近似，以減少計算量。目前廣泛使用的3種經(jīng)典裁剪算法分別是梁友棟-Barsky參數(shù)裁剪算法、Cohen-sutherland編碼裁剪算法和Nicholl-Lee-Nicholl多區(qū)域判別算法。這些算法各有特色，梁友棟-Barsky裁剪算法利用線段的參數(shù)表示形式，把被裁剪線段所在直線與矩形裁剪窗口邊框線的交點坐標(biāo)的計算，簡化為對交點對應(yīng)的參數(shù)值的計算，再根據(jù)交點參數(shù)與被裁剪線段的參數(shù)定義區(qū)間比較的結(jié)果，確定出有效的交點，從而得到裁剪后應(yīng)保留的部分線段。Cohen-sutherland裁剪算法是一個最早開發(fā)

3、的快速線段裁剪算法，應(yīng)用較為廣泛。該算法通過初始測試來減少交點計算，從而減少線段裁剪算法所用的時間。Nicholl-Lee-Nicholl算法通過在裁剪窗口邊界創(chuàng)立多個區(qū)域，從而避免對一個直線段進(jìn)行多次裁剪。由于Cohen-sutherland線段裁剪算法實現(xiàn)簡單，應(yīng)用廣泛，本文對此算法進(jìn)行了一些改進(jìn)。1．Cohen-sutherland線段裁剪算法描述100000001010001001000110000110010101裁剪窗口Cohen-sutherland線段裁剪算法對每條線段的端點都賦予一個四位二進(jìn)

4、制編碼，稱為‘區(qū)域碼’。區(qū)域碼的每一位用來標(biāo)示端點相對于相應(yīng)裁剪邊界的里面還是外面，分別用‘0’和‘1’表示。這樣，四個窗口邊界一起生成了九個區(qū)域，每個區(qū)域都有一個唯一的區(qū)域碼，如圖1所示。圖1裁剪窗口的九個位置區(qū)域碼一旦給所有的線段端點建立了區(qū)域碼，就可以快速判斷哪條線段完全在裁剪窗口內(nèi)，哪條線段完全在窗口之外。完全在窗口邊界內(nèi)的線段，其兩個端點的區(qū)域碼均為0000，因此保留這些線段。若兩個端點的區(qū)域碼中，有某一相同位置都為1，則該線段完全落在裁剪矩形之外，因此丟棄這些線段。測試線段是否在內(nèi)部或外部的方法是

5、對兩個端點的區(qū)域碼進(jìn)行邏輯操作，如果兩個端點的區(qū)域碼進(jìn)行邏輯或的結(jié)果為0000，則線段完全位于裁剪區(qū)域之內(nèi)。如果兩個端點的區(qū)域碼進(jìn)行邏輯與操作的結(jié)果不是真（不為0000），則線段完全位于裁剪區(qū)域之外。對于不能判斷為完全在窗口外或窗口內(nèi)的線段，則要測試其與窗口邊界的交點。2.Cohen-sutherland線段裁剪算法改進(jìn)線A線B線CCohen-sutherland算法對那些不與邊框相交的線段進(jìn)行裁剪時效率較高，而對與窗口邊界有交點的線段裁剪效率較低，而且很多時候，被裁剪線段僅與窗口邊界的延長線相交，而沒有穿過

6、窗口內(nèi)部，Cohen-sutherland算法計算了所有的交點后，結(jié)果卻是完全舍棄，如圖2中線A。由于求交運(yùn)算是裁剪算法中最耗時的部分，任何的算法都應(yīng)該盡量避免求交運(yùn)算，Cohen-sutherland算法中，這樣無效的交點計算降低了算法的效率。針對這個問題有很多學(xué)者進(jìn)行了改進(jìn)，如文獻(xiàn)[3][4]，這些方法大都是進(jìn)行了較多的區(qū)域劃分和判斷，比較復(fù)雜。本文提出了一種簡單易行的判斷方法，可以快速的判斷出線段是否完全在窗口外，從而減少計算量。圖2線段與裁剪窗口的位置關(guān)系本文算法思想如下：如果線段完全在窗口外，那么有

7、兩種可能：(1)線段兩端點的編碼中有某一相同位置都為1，即兩個端點編碼進(jìn)行邏輯與操作的結(jié)果為真，如圖2中線C。(2)裁剪窗口完全位于線段的同側(cè)，如圖2中線A。對于這種情況可以如下判斷：將裁剪窗口的四個端點代入直線方程，如果符號相同，說明窗口在線段的同側(cè)，即線段完全在窗口外；否則，說明線段和窗口有交點。改進(jìn)的Cohen-sutherland算法可以描述如下：首先對被裁剪線段兩個端點進(jìn)行編碼。然后進(jìn)行如下測試：（1）將兩端點的區(qū)域碼進(jìn)行邏輯或運(yùn)算，如果結(jié)果為0000，說明線段完全在窗口內(nèi)，可以完全保留。（2）將兩

8、端點的區(qū)域碼進(jìn)行邏輯與運(yùn)算，如果結(jié)果為真（不是0000），說明線段完全在窗口外，可以完全舍棄。（3）將窗口的四個頂點代入直線方程，如果符號相同，說明線段完全在窗口外，可以完全舍棄。對于上述情況均不滿足的線段，需要進(jìn)行求交運(yùn)算，這些線段必穿過窗口內(nèi)部。通過添加這樣一個判斷條件將算法的求交次數(shù)大大減少，從而提高了算法的效率。3.算法部分代碼……classPoint{……}Pointpoint1;Intr