学步园

                                                   Cohen－Sutherland线段裁减的改进算法

                                                                      陈玉进 李泉

                             南京跬步科技有限公司 http://www.creable.cn

摘要：Cohen－Sutherland线段裁减算法，对于线段全部落入视口内、或线段位于视口外一侧的情况判断较容易，而除此之外的情况判断裁减较复杂，需要线段与视口边线作多次求交裁减，减少求交裁减的次数是提高算法效率的关键。本文提出一种新的改进算法，先对编码进行“逻辑与”操作排除掉线段位于视口外一侧的情况，再对编码进行“逻辑或”操作，并对其结果分类讨论，以确定不同的相交情形，有效地减少了线段求交裁减次数，提高了算法的效率。

关键词：Cohen－Sutherland线段裁减算法，逻辑与，逻辑或

中图分类号：TP391

Improvement to Cohen－Sutherland Line Clipping Algorithm

Abstract：Cohen－Sutherland Line Clipping Algorithm can easily deal with the case that the line is completely inside of the view, or off to the side of the view, and other cases are complexly dealt with operations between line and view several times .The key of improving the algorithm is reducing the times of the Intersecting and Clipping operations. The paper proposed a new improved algorithm. Firstly, the logical AND operation of the codes eliminates the case that the line is completely inside of the view. Then, the logical OR operation of the codes determines the location relationship between line and view. This way could reduce algorithm complexity effectively.

Key words：Cohen－Sutherland Line Clipping Algorithm，logical AND，logical OR

线段裁减算法，是保留视口范围内的图形部分，裁减掉超出视口范围的图形，很多复杂图形的裁减也都可以归为线段裁减，因此，线段裁减是图形显示的重要环节，算法的效率直接影响图形显示的效果。在计算机图形学中，比较常用的算法有：Cohen－Sutherland编码裁减算法、梁友栋-Barsky算法等。本文对Cohen－Sutherland编码裁减算法提出了一些改进的思路。

1.        Cohen－Sutherland算法概述

1.1   Cohen－Sutherland视口编码

1.1   Cohen－Sutherland求交裁减

设端点编码为code1、code2，如果code1∧code2≠0，则线段位于视口外的同一侧，排除该线段、不予显示，如果code1＝0000且code2＝0000，则线段全部位于视口内，保留该线段、予以显示。如果code1∧code2＝0且code1、code2不全为0000，需要对线段沿视口边线进行裁减，Cohen－Sutherland线段裁减算法，需要线段与视口的四条边线分别作求交运算，逐边进行裁减。求交运算的算法为：

建立直线段与视口边线的线性方程组，求交点坐标，判断此交点是否处于线段延长线或视口边线的延长线上。如图2，求直线段a与视口左边线的交点，设S1的坐标为（x1,y1），S2的坐标为（x2,y2），直线S1S2的直线方程为

,可以转换为

 

已知视口左边线的x值，代入直线方程，即可计算出y值。需要判断该交点是否是真的交点，即需要满足如下不等式，y₁≤y≤y₂且y_min≤y≤y_max（y_min、y_max是视口上下边线的Y值），与其他边线的求交情况依次类推。

2       Cohen－Sutherland算法存在的问题

Cohen－Sutherland线段裁减算法，对于线段全部在视口内或位于视口外一侧的情形判断较容易，而其他情况，判断较复杂，通常需要逐边求交裁减，线段求交次数过多，尤其对一些与视口边线延长线相交，完全位于视口外的线段，经过多次求交裁减后发现应全部丢弃（如图2，线段b），Cohen－Sutherland算法没给出很好的判断方法。因此，增加了很多无效的求交运算。

 

 

 

3       Cohen－Sutherland算法改进的思路

以上分析了Cohen－Sutherland算法存在的一些问题，主要表现在线段求交次数过多，因此，减少不必要的线段求交是提高该算法效率的关键。本文提出了端点编码“逻辑或”，并对其结果进行分类讨论，确定线段与视口的相交形式，以减少线段求交的次数。

线段与视口相交点的个数只有三种：1，零个交点；2，一个交点；3，两个交点。如果code1∧code2＝0且code1、code2不全为0000，则进行code1∨code2运算，利用编码结果数值的唯一性，对其进行分类讨论。

3.1 “逻辑或”结果为1000、0100、0010、0001

1000、0100、0010、0001表明：其中一个端点位于视口内，另一个位于“上下右左”四个区域之一，与视口必有一个交点，只需一次求交。比如，“逻辑或”结果为1000，此线段与视口上边线相交，求交裁减即可，其他三种情况以此类推。

 

 

3.2 “逻辑或”结果为1100、0011

1100、0011表明：线段两端点分别位于对面区域，即“上下”、“左右”，与视口必有两个交点，只需两次求交。比如，“逻辑或”结果为0011，此线段与视口左右两边线相交，求交裁减即可。

 

3.3 “逻辑或”结果为1001、0101、1010、0110

1001、0101、1010、0110，其结果等于四个角区域的编码，分两类情况：一，其中一个端点位于视口内，编码为0000，另一个端点位于角区域，则线段与视口有一个交点，根据“逻辑或”结果确定线段与哪条视口边线求交，求交次数为一次或两次，比如，“逻辑或”结果为1001，一个端点的编码为0000，则此线段与视口上边线或左边线相交，且交点只有一个；二，没有端点位于视口内，则线段与视口有两个交点或没有交点，根据“逻辑或”结果确定线段与哪条视口边线求交，求交次数为一次或两次，再比如，“逻辑或”结果位1001，无端点编码为0000，则此线段两端点分别位于视口的上和左，先与视口左边线求交，如果没有交点，则结束，表明线段与视口不存在交点，如果有交点，那必然也与视口上边线存在交点。

 

3.4 “逻辑或”结果为1101、1011、1110、0111

1101、1011、1110、0111表明：一个端点位于角区域之一，一个端点位于上下左右区域之一，存在两个交点或没有交点，求交次数为一次或两次或三次。比如，“逻辑与”结果为1101，一个端点位于左上角区域，一个端点位于下区域，线段先与视口的下边线求交，如果没有交点，则结束，表明线段与视口没有交点，如果有交点，则视口的上边线或左边线的其中之一与线段有交点。

 

3.5 “逻辑或”结果为1111

1111表明：一个端点位于角区域，另一个端点位于对角的角区域，存在两个交点或没有交点，求交次数为两次或三次或四次。先拿两条相邻的视口边线与线段求交，如果两次求交都没有交点，则结束，表明线段与视口没有交点；如果存在一个交点，则需要另外一对相邻的视口边线再作一次或两次求交运算；如果存在两个交点，则结束，相交的两个交点已找到。

 

以上以“逻辑或”对线段与视口的位置关系、求交顺序、以及求交次数作了系统的分类说明，包括“逻辑或”结果为0000的情况，本文枚举了全部的四比特的16种组合情况，是完备的，通过“逻辑或”分类讨论，有效地减少了线段与视口的求交次数，在具体代码实现上通过Switch－Case选择跳转，改进了Cohen－Sutherland算法的效率。

1        结束语

在嵌入式GIS中，线段裁减是图形显示、地图标注的前提，它的效率在嵌入式图形系统中显得尤为重要，本文提出的Cohen－Sutherland改进算法，已在自主研发的嵌入式GIS平台中得到应用，证明了该算法的效率。

参考文献：

[1] 孙家广,胡事民. 计算机图形学[M ]. 清华大学出版社, 2005年2月.

[2] DAVID JWHEELER, ROBERTM. NEEDHAM. TEA , a Tiny Encryption Algorithm. Technical report [ J ] , Computer Laboratory , University of Cambridge , 1995.

[3] GREINER G, HORMANN K. Efficient Clipping of Arbitrary Polygons[ J ]. ACM Transactions on Graphics, 1998.

[4] 付迎春,袁修孝. 一种有效的任意多边形裁剪算法[ J ]. 计算机工程, 2006年4月.

[5] 王艳娟,肖刚强等. 改进的Cohen－Sutherland线段裁剪算法[ J ]. 现代计算机, 2007年2月.

[6] 郭长友,郑文艳等. 一种快速的二维线段裁减新算法[ J ]. 福建电脑, 2006年1月.

[7] 孔德惠等. 对裁减算法的改进[ J ]. 北京工业大学学报, 2002年12月.

[8] 黄初华,陈孝威. 对Cohen－Sutherland裁剪算法的改进[ J ]. 贵州大学学报（自然科学版） 2008年5月