欢迎来到天天文库
浏览记录
ID:20551439
大小:44.00 KB
页数:3页
时间:2018-10-10
《改进cohen-sutherland线段裁剪算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、改进的cohen-sutherland线段裁剪算法王艳娟肖刚强任洪海(大连交通大学软件学院116052)摘要:针对目前的conhen-sutherland线段裁剪算法不能有效地判断出线段是否完全在窗口外的问题,提出了一种改进的conhen-sutherland线段裁剪算法,通过添加一个判断条件,使得所有完全位于窗口外的线段都能快速的过滤出来,从而减少了求交点的次数,提高了运算效率。关键词:裁剪算法,cohen-sutherland线裁剪算法,求交运算0.引言线段裁剪是复杂图元裁剪的基础,各种非线性边界都可以用
2、直线段来近似,以减少计算量。目前广泛使用的3种经典裁剪算法分别是梁友栋-Barsky参数裁剪算法、Cohen-sutherland编码裁剪算法和Nicholl-Lee-Nicholl多区域判别算法。这些算法各有特色,梁友栋-Barsky裁剪算法利用线段的参数表示形式,把被裁剪线段所在直线与矩形裁剪窗口边框线的交点坐标的计算,简化为对交点对应的参数值的计算,再根据交点参数与被裁剪线段的参数定义区间比较的结果,确定出有效的交点,从而得到裁剪后应保留的部分线段。Cohen-sutherland裁剪算法是一个最早开发
3、的快速线段裁剪算法,应用较为广泛。该算法通过初始测试来减少交点计算,从而减少线段裁剪算法所用的时间。Nicholl-Lee-Nicholl算法通过在裁剪窗口边界创立多个区域,从而避免对一个直线段进行多次裁剪。由于Cohen-sutherland线段裁剪算法实现简单,应用广泛,本文对此算法进行了一些改进。1.Cohen-sutherland线段裁剪算法描述100000001010001001000110000110010101裁剪窗口Cohen-sutherland线段裁剪算法对每条线段的端点都赋予一个四位二进
4、制编码,称为‘区域码’。区域码的每一位用来标示端点相对于相应裁剪边界的里面还是外面,分别用‘0’和‘1’表示。这样,四个窗口边界一起生成了九个区域,每个区域都有一个唯一的区域码,如图1所示。图1裁剪窗口的九个位置区域码一旦给所有的线段端点建立了区域码,就可以快速判断哪条线段完全在裁剪窗口内,哪条线段完全在窗口之外。完全在窗口边界内的线段,其两个端点的区域码均为0000,因此保留这些线段。若两个端点的区域码中,有某一相同位置都为1,则该线段完全落在裁剪矩形之外,因此丢弃这些线段。测试线段是否在内部或外部的方法是
5、对两个端点的区域码进行逻辑操作,如果两个端点的区域码进行逻辑或的结果为0000,则线段完全位于裁剪区域之内。如果两个端点的区域码进行逻辑与操作的结果不是真(不为0000),则线段完全位于裁剪区域之外。对于不能判断为完全在窗口外或窗口内的线段,则要测试其与窗口边界的交点。2.Cohen-sutherland线段裁剪算法改进线A线B线CCohen-sutherland算法对那些不与边框相交的线段进行裁剪时效率较高,而对与窗口边界有交点的线段裁剪效率较低,而且很多时候,被裁剪线段仅与窗口边界的延长线相交,而没有穿过
6、窗口内部,Cohen-sutherland算法计算了所有的交点后,结果却是完全舍弃,如图2中线A。由于求交运算是裁剪算法中最耗时的部分,任何的算法都应该尽量避免求交运算,Cohen-sutherland算法中,这样无效的交点计算降低了算法的效率。针对这个问题有很多学者进行了改进,如文献[3][4],这些方法大都是进行了较多的区域划分和判断,比较复杂。本文提出了一种简单易行的判断方法,可以快速的判断出线段是否完全在窗口外,从而减少计算量。图2线段与裁剪窗口的位置关系本文算法思想如下:如果线段完全在窗口外,那么有
7、两种可能:(1)线段两端点的编码中有某一相同位置都为1,即两个端点编码进行逻辑与操作的结果为真,如图2中线C。(2)裁剪窗口完全位于线段的同侧,如图2中线A。对于这种情况可以如下判断:将裁剪窗口的四个端点代入直线方程,如果符号相同,说明窗口在线段的同侧,即线段完全在窗口外;否则,说明线段和窗口有交点。改进的Cohen-sutherland算法可以描述如下:首先对被裁剪线段两个端点进行编码。然后进行如下测试:(1)将两端点的区域码进行逻辑或运算,如果结果为0000,说明线段完全在窗口内,可以完全保留。(2)将两
8、端点的区域码进行逻辑与运算,如果结果为真(不是0000),说明线段完全在窗口外,可以完全舍弃。(3)将窗口的四个顶点代入直线方程,如果符号相同,说明线段完全在窗口外,可以完全舍弃。对于上述情况均不满足的线段,需要进行求交运算,这些线段必穿过窗口内部。通过添加这样一个判断条件将算法的求交次数大大减少,从而提高了算法的效率。3.算法部分代码……classPoint{……}Pointpoint1;Intr
此文档下载收益归作者所有