直线裁剪算法研究Cohen-Sutherland算法和Liang-Barsky算法.doc

《直线裁剪算法研究Cohen-Sutherland算法和Liang-Barsky算法.doc》由会员分享，可在线阅读，更多相关《直线裁剪算法研究Cohen-Sutherland算法和Liang-Barsky算法.doc（9页珍藏版）》请在课桌文档上搜索。

1、word直线裁剪算法研究摘要：直线裁剪是计算机图形学中的一个重要技术，在对常见的直经线裁剪的算法分析的根底上，针对Cohen-Sutherland算法和Liang-Barsky算法进展了分析研究。并对两种算法了计算直线与窗口边界的交点时，进展了有效有比拟。关键词：裁剪；算法；Cohen-Sutherland；LiangBarsky；1引言直线是图形系统中使用最多的一个根本元素。所以对于直线段的裁剪算法是被研究最深入的一类算法，目前在矩形窗口的直线裁剪算法中，出现了许多有效的算法。其中比拟著名的有：Cohen-Sutherland算法、中点分割算法、Liang-Barsky算法、Sobkow-P

2、ospisil-Yang算法，与Nicholl-Lee-Ncholl算法等。2直线裁剪的根本原理图1所示的为直线与窗口边界之间可能出现的几种关系。可以通过检查直线的两个端点是否在窗口之确定如何对此直线裁剪。如果一直线的两个端点均在窗口边界之如图1中P5到P6的直线，如此此直线应保存。如果一条直线的一个端点在窗口外如P9另一个点在窗口如P10，如此应从直线与边界的交点P9处裁剪掉边界之外的线段。如果直线的两个端点均在边界外，如此可分为两种情况：一种情况是该直线全部在窗口之外；另一种情况是直线穿过两个窗口边界。图中从P3到P4的直线属于前一种情况，应全部裁剪掉；从P7到P8的直线属于后一种情况，应

3、保存P7到P8的线段，其余局部均裁剪掉。图1直线相对干窗口边界的栽剪直线裁剪算法应首先确定哪些直线全部保存或全部裁剪，剩下的即为局部裁剪的直线。对于局部裁剪的直线如此首先要求出这些直线与窗口边界的交点，把从交点开始在边界外的局部裁剪掉。一个复杂的画面中可能包含有几千条直线，为了提高算法效率，加快裁剪速度，应当采用计算量较小的算法求直线与窗口边界的交点。3 cohensutherland直线裁剪算法Cohen-Sutherland算法的大意是：对于每条线段P1P2，分为3种情况处理。假如P1P2完全在窗口，如此显示该线段P1P2，简称“取之。假如P1P2明显在窗口外，如此丢弃该线段，简称“弃之。

4、假如线段既不满足“取的条件，也不满足“弃的条件，如此把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。1区域码与其建立Cohen-Sutherland直线裁剪算法的核心是把所有直线的端点均分配一个表示其相对位置的4位二进制代码。此代码称为区域码。区域码按照端点与窗口边界的相对位置编码，即区域码的4位分别代表端点位于窗口的上、下、左、右。区域码从右到左的各位所代表的坐标区如下所示：位 4 3 2 1坐标区 上 下 右 左上述各位中某位为1，如此表示点位于此坐标区。窗口周围各坐标区的区域码如图2所示。由图2可见，位于窗中的点，其区域码应为0000，位于窗口左下方的点，其区域码

5、应为0101，其余类推。区域码各位的值可以通过对端点坐标x，y与窗口边界的比拟求得。如果xyw_ymax) code| =TOP; else if (yxw_xmax) code|=RIGHT; else if (xxw_xmin,&t0,&t1) if (Clip Top(dx,rect-xw_xmax-x1,&t0,&t1)dy=y2-y1; if (Clip Top(-dy,y1-rect-yx_xmin,&t0,&t1) if (Clip Top(dy,rect-xw_xmax-y1,&t0,&t1) Line (int) (x1+t0*dx),(int) (y1+t0*dy) (in

6、t) (x1+t1*dx) (int) (y1+t1*dy);return; writeText(“p1p2完全不可见)； Void Line_Clipping(q,d,*t0,*t1) float q,d,*t0,*t1; float r;if (rt1) return(FALSE); else if (rt0) t0=r; return (TRUE); else if (q0) r=d/q; if (rt0) return (FALSE); else if (rt1) t1=r; return (TRUE); else if (d0)return (FALSE); return (TRUE

7、);5两种算法比拟Cohen-Sutherland直线裁剪算法与LiangBarsky裁剪算法所需的各种运算的次数进展比拟，列表如下：加法次数减法次数乘法次数除法次数Cohen-Sutherland4462Liang-Barsky2422 由上表可知：在求被裁剪计算直线与窗口边界的交点交点时，LiangBarsky算法的效率也高于Cohen-Sutherland算法。6结论区域码直线裁剪算法方法直观方便，速度较快，是一种较好的裁剪方法，但有两个问题还有待进一步解决。(1)由于采用位逻辑乘的运算，这在有些高级语言中是不便进展的。 (2)全部舍弃的判断只适合于那些仅在窗口的线段,对于跨越3个区域的

8、线段(如线段),就不能一次作出判别面舍弃它们。LiangBarsky裁剪算法所需的计算量较小。每修改一次或只需要一次除法，在与。确定后，直线与窗口边界的交点只需计算一次，但该算法只能应用于矩形窗口的情形。而区域码方法要屡次重复计算直线与窗口边界的交点，且每计算一次交点需要一次除法与一次乘法。参考文献1 Donald Hearn.计算机图形学第三版M.,电子工业,20052家广,长贵.计算机图形学根底第三版M.,清华大学,20023钦,徐永安.计算机图形学M.:清华大学,20054孔德惠等.对cohen-sutherland线段裁剪算法的改良J.工业大学学报,20025郭长友等.一种快速的二维线段裁减新算法J.电脑,20069 / 9