郭旌巍+楊振州

摘 要：在矩形窗口的二維裁減中，Cohen-Sutherland線段裁剪算法既不能有效地判斷出線段是否完全在窗口外又可能求解出無效交點(diǎn)，因此本文提出一種基于Cohen-Sutherland線段裁剪算法的改進(jìn)算法，給定一個(gè)線段，由計(jì)算剪裁窗口頂點(diǎn)到線段的有向距離符號(hào)來判斷線段與窗口相對(duì)位置關(guān)系，避免求取無效交點(diǎn)的操作。改進(jìn)算法可以迅速判斷哪些線段與裁剪窗口有真正的交點(diǎn)，再通過距離大小的比較，確定直線與窗口的哪條邊相交，最終將被裁剪線段快速、準(zhǔn)確輸出。實(shí)驗(yàn)表明， 改進(jìn)的Cohen-Sutherland算法比原算法有更高的執(zhí)行效率。

關(guān)鍵詞：Cohen-Sutherland裁剪算法 裁剪窗口 求交運(yùn)算 有向距離符號(hào)

中圖分類號(hào)：T31 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2015）06（a）-0047-01

線段裁剪是計(jì)算機(jī)圖形學(xué)中最基本的技術(shù)之一，目前常用的三種經(jīng)典直線裁剪算法為：Cohen-Sutherland編碼算法；中點(diǎn)分割算法和Liang-Barsky算法等，傳統(tǒng)算法影響線段裁剪算法效率的主要原因有兩點(diǎn)：（1）是否完全丟棄與窗口不相關(guān)的線段。（2）能否快速簡單地求出線段與窗口的交點(diǎn)。[1]針對(duì)上述問題，該文提出了改進(jìn)的C_S編碼裁剪算法，該算法能迅速判斷哪些線段與裁剪窗口有真正的交點(diǎn)，使線段與窗口交點(diǎn)的計(jì)算量降到最低水平，提高裁剪的效率。

1 Cohen_Sutherland線段裁剪算法的分析

Cohen-Sutherland算法基本原理描述為：矩形窗口中顯示直線。

依據(jù)算法的基本思想，設(shè)Start和end分別是是直線端點(diǎn)的起始和終止編碼。若start==0且end==0，完全顯示這條線段。若start&end！=0，完全舍棄這條線段。若上述兩條件均不成立，則求線段和可見窗口的邊的交點(diǎn)，在交點(diǎn)處把線段一分為二，完全在窗口外的部分，棄之；另一部分重復(fù)上述操作。[2]

從圖1可以得到，線段AB與窗口邊界相交，以圖可知只需計(jì)算與上邊界和左邊界的交點(diǎn)即可。線段CD和線段AB的處理類似。線段EF與可見窗口不想交，簡棄之，但算法前兩種情況無法實(shí)現(xiàn)此種操作。線段EF與可見窗口下邊界和右邊界計(jì)算交點(diǎn)后，才可舍棄。[3]因此，如果可以對(duì)那些與邊框線有交的線段再進(jìn)行精確的判斷，舍棄實(shí)際落在矩形窗口外的線段，同時(shí)準(zhǔn)確地判斷出有效交點(diǎn)產(chǎn)生的邊界，就可以極大的提高線段裁剪的運(yùn)算效率。

2 改進(jìn)的Cohen_Sutherland線段裁剪算法

2.1 判斷線段和窗口邊界有無有效交點(diǎn)

如圖2所示，窗口的左上、左下、右上、右下角點(diǎn)分別記為GLT、GLB、GRT、GRB。分別計(jì)算角點(diǎn)GLT、GLB到線段所在直線的有向距離，分別記為、。若兩者同號(hào)，表明線段與窗口邊界不相交，此時(shí)應(yīng)舍棄被裁剪線段。若兩者異號(hào)，則表明兩角點(diǎn)分別在線段的兩側(cè)，因而線段與窗口邊界有至少一個(gè)有效交點(diǎn)。[4]

2.2 判斷線段和窗口的哪條邊界相交

通過3.1已經(jīng)判斷出直線和窗口邊界至少有一個(gè)交點(diǎn)。如上圖3所示假設(shè)在窗口邊界外，如果在窗口外，交換、。過分別連接角點(diǎn)GRT、GRB。分別過GLT、GLB向線段和線段作垂線，距離記作。分別比較與和與的距離。如果>且>，則線段分別與窗口的左邊界和右邊界相交。否則如果<，線段與窗口的左邊界和下邊界相交。如果<，線段和窗口的左邊界和上邊界相交。

3 結(jié)語

該算法在原算法編碼思想的基礎(chǔ)上加以改進(jìn)，提出了基于C-S算法裁剪的新思路。通過徹底排除與窗口不相交的線段來提高執(zhí)行效率，并且可直接求得與窗口相交的有效交點(diǎn)，避免了冗余交點(diǎn)的計(jì)算，這樣不僅縮短了程序運(yùn)行的時(shí)間，而且還提高了線段裁剪的執(zhí)行效率。

參考文獻(xiàn)

[1] 陸楓，何云峰.計(jì)算機(jī)圖形學(xué)基礎(chǔ)[M].2版.北京：電子工業(yè)出版社，2012.

[2] 陳定鈺，丁有和.基于交點(diǎn)和區(qū)域特征的線段裁剪算法[J].現(xiàn)代計(jì)算機(jī)，2014（26）：51-53，57.

[3] Jingjing Han.“Improvement in the Cohen-Sutherland Line Segment Clipping Algorithm[C]//2013 IEEE International Conference on Granular Computing（GrC）.2013.

[4] 孔德慧，尹寶才，劉媛媛.對(duì)Cohen—sutherland線段裁剪算法的改進(jìn)[J].北京工業(yè)大學(xué)學(xué)報(bào)，2002，28（4）：483—486.endprint