對Cohen—Sutherland裁剪算法的分析與改進

郭旌巍+楊振州

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

關鍵詞：Cohen-Sutherland裁剪算法 裁剪窗口 求交運算 有向距離符號

中圖分類號：T31 文獻標識碼：A 文章編號：1674-098X（2015）06（a）-0047-01

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

1 Cohen_Sutherland線段裁剪算法的分析

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

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

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

2 改進的Cohen_Sutherland線段裁剪算法

2.1 判斷線段和窗口邊界有無有效交點

如圖2所示，窗口的左上、左下、右上、右下角點分別記為GLT、GLB、GRT、GRB。分別計算角點GLT、GLB到線段所在直線的有向距離，分別記為、。若兩者同號，表明線段與窗口邊界不相交，此時應舍棄被裁剪線段。若兩者異號，則表明兩角點分別在線段的兩側，因而線段與窗口邊界有至少一個有效交點。[4]

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

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

3 結語

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

參考文獻

[1] 陸楓，何云峰.計算機圖形學基礎[M].2版.北京：電子工業出版社，2012.

[2] 陳定鈺，丁有和.基于交點和區域特征的線段裁剪算法[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] 孔德慧，尹寶才，劉媛媛.對Cohen—sutherland線段裁剪算法的改進[J].北京工業大學學報，2002，28（4）：483—486.endprint