郭旌巍+杨振州

摘 要：在矩形窗口的二维裁减中，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