1、改進(jìn)的cohen-sutherland線段裁剪算法王艷娟肖堅(jiān)強(qiáng)任洪海大連交通大學(xué)軟件學(xué)院116052摘要：針對(duì)目前的conhen-sutherland線段裁剪算法不能有效地判斷出線段是否完全在窗口外的問題，提出了一種改進(jìn)的conhen-sutherland線段裁剪算法，通過添加一個(gè)判斷條件，使得所有完全位于窗口外的線段都能快速的過濾出來，從而減少了求交點(diǎn)的次數(shù)，進(jìn)步了運(yùn)算效率。關(guān)鍵詞：裁剪算法，cohen-sutherland線裁剪算法，求交運(yùn)算0引言線段裁剪是復(fù)雜圖元裁剪的根底，各種非線性邊界都可以用直線段來近似，以減少計(jì)算量。目前廣泛使用的3種經(jīng)典裁剪算法分別是梁友棟-Barsky參數(shù)裁剪

2、算法、Cohen-sutherland編碼裁剪算法和Nicholl-Lee-Nicholl多區(qū)域判別算法。這些算法各有特色，梁友棟-Barsky裁剪算法利用線段的參數(shù)表示形式，把被裁剪線段所在直線與矩形裁剪窗口邊框線的交點(diǎn)坐標(biāo)的計(jì)算，簡(jiǎn)化為對(duì)交點(diǎn)對(duì)應(yīng)的參數(shù)值的計(jì)算，再根據(jù)交點(diǎn)參數(shù)與被裁剪線段的參數(shù)定義區(qū)間比較的結(jié)果，確定出有效的交點(diǎn)，從而得到裁剪后應(yīng)保存的部分線段。Cohen-sutherland裁剪算法是一個(gè)最早開發(fā)的快速線段裁剪算法，應(yīng)用較為廣泛。該算法通過初始測(cè)試來減少交點(diǎn)計(jì)算，從而減少線段裁剪算法所用的時(shí)間。Nicholl-Lee-Nicholl算法通過在裁剪窗口邊界創(chuàng)立多個(gè)區(qū)域，從而

3、防止對(duì)一個(gè)直線段進(jìn)展屢次裁剪。由于Cohen-sutherland線段裁剪算法實(shí)現(xiàn)簡(jiǎn)單，應(yīng)用廣泛，本文對(duì)此算法進(jìn)展了一些改進(jìn)。Cohen-sutherland線段裁剪算法描繪Cohen-sutherland線段裁剪算法對(duì)每條線段的端點(diǎn)都賦予一個(gè)四位二進(jìn)制編碼，稱為區(qū)域碼。區(qū)域碼的每一位用來標(biāo)示端點(diǎn)相對(duì)于相應(yīng)裁剪邊界的里面還是外面，分別用0和1表示。這樣，四個(gè)窗口邊界一起生成了九個(gè)區(qū)域，每個(gè)區(qū)域都有一個(gè)唯一的區(qū)域碼，如圖1所示。圖1裁剪窗口的九個(gè)位置區(qū)域碼一旦給所有的線段端點(diǎn)建立了區(qū)域碼，就可以快速判斷哪條線段完全在裁剪窗口內(nèi)，哪條線段完全在窗口之外。完全在窗口邊界內(nèi)的線段，其兩個(gè)端點(diǎn)的區(qū)域碼均

4、為0000,因此保存這些線段。假設(shè)兩個(gè)端點(diǎn)的區(qū)域碼中，有某一一樣位置都為1，那么該線段完全落在裁剪矩形之外，因此丟棄這些線段。測(cè)試線段是否在內(nèi)部或外部的方法是對(duì)兩個(gè)端點(diǎn)的區(qū)域碼進(jìn)展邏輯操作，假設(shè)兩個(gè)端點(diǎn)的區(qū)域碼進(jìn)展邏輯或的結(jié)果為0000，那么線段完全位于裁剪區(qū)域之內(nèi)。假設(shè)兩個(gè)端點(diǎn)的區(qū)域碼進(jìn)展邏輯與操作的結(jié)果不是真不為0000，那么線段完全位于裁剪區(qū)域之外。對(duì)于不能判斷為完全在窗口外或窗口內(nèi)的線段，那么要測(cè)試其與窗口邊界的交點(diǎn)。裁剪算法改進(jìn)Cohen-sutherland算法對(duì)那些不與邊框相交的線段進(jìn)展裁剪時(shí)效率較高，而對(duì)與窗口邊界有交點(diǎn)的線段裁剪效率較低，而且很多時(shí)候，被裁剪線段僅與窗口邊界的

5、延長(zhǎng)線相交，而沒有穿過窗口內(nèi)部，Cohen-sutherland算法計(jì)算了慚有的交點(diǎn)后，結(jié)果卻是完全舍棄，如圖2中線A。由于求交運(yùn)算是裁剪算法中最耗時(shí)的部分，任何的算法都應(yīng)該盡量防止求交運(yùn)A致L線b算，Cohen-sutherland算法中，這樣無效的交點(diǎn)計(jì)算降低了算法的效率。針對(duì)這個(gè)問題有很多學(xué)者進(jìn)展了改進(jìn)，如文獻(xiàn)34，這些方法大都是進(jìn)展了較多的區(qū)域劃分和判斷，比較復(fù)雜。本文提出了一種簡(jiǎn)單易行的判斷方法，可以快速的判斷出線段是否完全在窗口外，從而減少計(jì)算量。直線段P1P2的編碼裁剪圖2線段與裁剪窗口的位置關(guān)系本文算法思想如下:假設(shè)線段完全在窗口外，那么有兩種可能：(1)線段兩端點(diǎn)的編碼中有某

6、一一樣位置都為1,即兩個(gè)端點(diǎn)編碼進(jìn)展邏輯與操作的結(jié)果為真，如圖2中線C。(2)裁剪窗口完全位于線段的同側(cè)，如圖2中線A。對(duì)于這種情況可以如下判斷：將裁剪窗口的四個(gè)端點(diǎn)代入直線方程，假設(shè)符號(hào)一樣，說明窗口在線段的同側(cè)，即線段完全在窗口外；否那么，說明線段和窗口有交點(diǎn)。改進(jìn)的Cohen-sutherland算法可以描繪如下：首先對(duì)被裁剪線段兩個(gè)端點(diǎn)進(jìn)展編碼。然后進(jìn)展如下測(cè)試：(1)將兩端點(diǎn)的區(qū)域碼進(jìn)展邏輯或運(yùn)算，假設(shè)結(jié)果為0000,說明線段完全在窗口內(nèi)，可以完全保存。(2)將兩端點(diǎn)的區(qū)域碼進(jìn)展邏輯與運(yùn)算，假設(shè)結(jié)果為真不是0000，說明線段完全在窗口外，可以完全舍棄。(3)將窗口的四個(gè)頂點(diǎn)代入直線方

7、程，假設(shè)符號(hào)一樣，說明線段完全在窗口外，可以完全舍棄。對(duì)于上述情況均不滿足的線段，需要進(jìn)展求交運(yùn)算，這些線段必穿過窗口內(nèi)部。通過添加這樣一個(gè)判斷條件將算法的求交次數(shù)大大減少，從而進(jìn)步了算法的效率。部分代碼classPointPointpoint1;Intreject2(pointp1,point1p2)If(winMin.y-p1.y)/(winMin.x-p1.x)-(p2.y-p1.y)/(p2.x-p1.x)0)&)intdone=false,plotLine=false;while(!done)code1=encode(p1,winMin,winMax);code2=encode(p2,winMin,winMax);if(accept(code1,code2)done=true;plotLine=true;elseif(reject1(code1,code2)done=true;elseif(reject2(p1,p2)done=true;else直線裁剪算法是計(jì)算機(jī)圖形學(xué)領(lǐng)域的一個(gè)根本問題，進(jìn)步線裁剪算法的效率在計(jì)算機(jī)圖形學(xué)的各個(gè)應(yīng)用領(lǐng)域中都有著重大的意義。線段與窗口邊界的交點(diǎn)計(jì)算是線裁剪函數(shù)的耗時(shí)部分，本文通過對(duì)cohen-sutherland線裁剪算法進(jìn)展了改進(jìn)，從而減少了求交次數(shù)，進(jìn)步了算法的效率。參考文獻(xiàn)DonaldHearn,計(jì)算機(jī)圖形學(xué)M，第三版，北京，電子