文档介绍：改进的cohen-sutherland线段裁剪算法
王艳娟肖刚强任洪海
(大连交通大学软件学院 116052)
摘要:针对目前的conhen-sutherland线段裁剪算法不能有效地判断出线段是否完全在窗口外的问题,提出了一种改进的conhen-sutherland线段裁剪算法,通过添加一个判断条件,使得所有完全位于窗口外的线段都能快速的过滤出来,从而减少了求交点的次数,提高了运算效率。
关键词:裁剪算法,cohen-sutherland线裁剪算法,求交运算

线段裁剪是复杂图元裁剪的基础,各种非线性边界都可以用直线段来近似,以减少计算量。目前广泛使用的3种经典裁剪算法分别是梁友栋-Barsky参数裁剪算法、Cohen-sutherland编码裁剪算法和Nicholl-Lee-Nicholl多区域判别算法。这些算法各有特色,梁友栋-Barsky裁剪算法利用线段的参数表示形式,把被裁剪线段所在直线与矩形裁剪窗口边框线的交点坐标的计算,简化为对交点对应的参数值的计算,再根据交点参数与被裁剪线段的参数定义区间比较的结果,确定出有效的交点,从而得到裁剪后应保留的部分线段。Cohen-sutherland裁剪算法是一个最早开发的快速线段裁剪算法,应用较为广泛。该算法通过初始测试来减少交点计算,从而减少线段裁剪算法所用的时间。Nicholl-Lee-Nicholl算法通过在裁剪窗口边界创立多个区域,从而避免对一个直线段进行多次裁剪。由于Cohen-sutherland线段裁剪算法实现简单,应用广泛,本文对此算法进行了一些改进。
-sutherland线段裁剪算法描述
1000
0000
1010
0010
0100
0110
0001
1001
0101
裁剪窗口
Cohen-sutherland线段裁剪算法对每条线段的端点都赋予一个四位二进制编码,称为‘区域码’。区域码的每一位用来标示端点相对于相应裁剪边界的里面还是外面,分别用‘0’和‘1’表示。这样,四个窗口边界一起生成了九个区域,每个区域都有一个唯一的区域码,如图1所示。
图1 裁剪窗口的九个位置区域码
一旦给所有的线段端点建立了区域码,就可以快速判断哪条线段完全在裁剪窗口内,哪条线段完全在窗口之外。完全在窗口边界内的线段,其两个端点的区域码均为0000,因此保留这些线段。若两个端点的区域码中,有某一相同位置都为1,则该线段完全落在裁剪矩形之外,因此丢弃这些线段。
测试线段是否在内部或外部的方法是对两个端点的区域码进行逻辑操作,如果两个端点的区域码进行逻辑或的结果为0000,则线段完全位于裁剪区域之内。如果两个端点的区域码进行逻辑与操作的结果不是真(不为0000),则线段完全位于裁剪区域之外。
对于不能判断为完全在窗口外或窗口内的线段,则要测试其与窗口边界的交点。
-sutherland线段裁剪算法改进
线A
线B
线C
Cohen-sutherland算法对那些不与边框相交的线段进行裁剪时效率较高,而对与窗口边界有交点的线段裁剪效率较低,而且很多时候,被裁剪线段仅与窗口边界的延长线相交,而没有穿过窗口内部,Cohen-sutherland算法计算了所有的交点后,结果却是完全舍弃,如图2中线A。由于求交运算是裁剪算