《直线裁剪算法研究(Cohen-Sutherland算法和Liang-Barsky算法)》由会员分享，可在线阅读，更多相关《直线裁剪算法研究(Cohen-Sutherland算法和Liang-Barsky算法)（9页珍藏版）》请在金锄头文库上搜索。
1、 直线裁剪算法研究摘要：直线裁剪是计算机图形学中的一个重要技术，在对常见的直经线裁剪的算法分析的基础上，针对Cohen-Sutherland算法和Liang-Barsky算法进行了分析研究。并对两种算法了计算直线与窗口边界的交点时，进行了有效有比较。关键词：裁剪；算法；Cohen-Sutherland；LiangBarsky；1 引言直线是图形系统中使用最多的一个基本元素。所以对于直线段的裁剪算法是被研究最深入的一类算法，目前在矩形窗口的直线裁剪算法中，出现了许多有效的算法。其中比较著名的有：Cohen-Sutherland算法、中点分割算法、Liang-Barsky算法、Sobkow-Pos
2、pisil-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) code|=LEFT; return code; 4 LiangBarsky算法Liang（梁友栋)-Barsky算法又称为参数方程法。首先写出端点及之间连线的参数方程如下：其中，。参数u可取0 1之间的值，坐标表示此围的u值定义的直线上的一个点。当u0时，直线的另一端u0时，。我们发现，如果直线上的某点处于及及所定义的窗口之，则满足以下条：这四个不等式可以表示为：， k=1,2,3,4其中，参数定义为； 按照直线与窗口边界的相对位置，可分为以下几种倩况。任何一条与
