文档介绍：word
word
1 / 11
word
直线裁剪算法研究
摘要：直线裁剪是计算机图形学中的一个重要技术，在对常见的直经线裁剪的算法分析的根底上，针对Cohen-Sutherland算法和Liang-Barsky算法进展了分析研究。并对两种算法了计算直线与窗口边界的交点时，进展了有效有比拟。
关键词：裁剪；算法；Cohen-Sutherland；Liang－Barsky；
1引言
直线是图形系统中使用最多的一个根本元素。所以对于直线段的裁剪算法是被研究最深入的一类算法，目前在矩形窗口的直线裁剪算法中，出现了许多有效的算法。其中比拟著名的有：Cohen-Sutherland算法、中点分割算法、Liang-Barsky算法、Sobkow-Pospisil-Yang算法，与Nicholl-Lee-Ncholl算法等。
2直线裁剪的根本原理
图1所示的为直线与窗口边界之间可能出现的几种关系。可以通过检查直线的两个端点是否在窗口之确定如何对此直线裁剪。如果一直线的两个端点均在窗口边界之〔如图1中P5到P6的直线〕，如此此直线应保存。如果一条直线的一个端点在窗口外〔如P9〕另一个点在窗口〔如P10〕，如此应从直线与边界的交点〔P9〕处裁剪掉边界之外的线段。如果直线的两个端点均在边界外，如此可分为两种情况：一种情况是该直线全部在窗口之外；另一种情况是直线穿过两个窗口边界。图中从P3到P4的直线属于前一种情况，应全部裁剪掉；从P7到P8的直线属于后一种情况，应保存P7到P8的线段，其余局部均裁剪掉。
图1直线相对干窗口边界的栽剪
直线裁剪算法应首先确定哪些直线全部保存或全部裁剪，剩下的即为局部裁剪的直线。对于局部裁剪的直线如此首先要求出这些直线与窗口边界的交点，把从交点开始在边界外的局部裁剪掉。一个复杂的画面中可能包含有几千条直线，为了提高算法效率，加快裁剪速度，应当采用计算量较小的算法求直线与窗口边界的交点。
word
word
3 / 11
word
3 cohen－sutherland直线裁剪算法
Cohen-Sutherland算法的大意是：对于每条线段P1P2，分为3种情况处理。
①假如P1P2完全在窗口，如此显示该线段P1P2，简称“取〞之。
②假如P1P2明显在窗口外，如此丢弃该线段，简称“弃〞之。
③假如线段既不满足“取〞的条件，也不满足“弃〞的条件，如此把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。
1．区域码与其建立
Cohen-Sutherland直线裁剪算法的核心是把所有直线的端点均分配一个表示其相对位置的4位二进制代码。此代码称为区域码。区域码按照端点与窗口边界的相对位置编码，即区域码的4位分别代表端点位于窗口的上、下、左、右。区域码从右到左的各位所代表的坐标区如下所示：
位 4 3 2 1
坐标区上下右左
上述各位中某位为1，如此表示点位于此坐标区。窗口周围各坐标区的区域码如图2所示。由图2可见，位于窗中的点，其区域码应为0000，位于窗口左下方的点，其区域码应为0101，其余类推。
区域码各位的值可以通过对端点坐标〔x，y〕与窗口边界的比拟求得。如果x<xwmin，如此区域码的第一位为1，其余各位确实定与此相似。现在的计算机语言都可以进展位操作，因此，可以通过以下步骤建立区域码：
①计算出端点坐标与窗口边界的差。
②按计算出的各个差的符号把区域码的相应位置为0或1，即
区域码的第一位置为〔x－xwmin〕的符号位；
区域码的第二位置为〔xwmin-x〕的符号位；
图2 区域码
区域码的第三位置为〔y-ywmin〕的符号位；
区域码的第四位置为〔ywmin-y〕的符号位。
2．区域码裁剪算法
对所有直线的端点都建立了区域码之后，就可按区域码判断直线在窗口之或窗口之外。这可分为如下几种情况：
①假如一直线的两个端点的区域码均为0000如此此直线在窗口边界之，应子保存。
②假如一直线的两个端点的区域码的同一位同时为1，如此此直线全部在窗口边界之外，应子裁剪。例如，假如一直线的一个端点的区域码为1001，另一个端点的区域码为0101，如此此两端点的区域码的第一位均为1，说明此两端点均在窗口边界之左，因此，直线在窗口边界之外，应予裁剪。可用将直线两个端点的
word
word
3 / 11
word
区域码进展与操作的方法，判断直线是否在窗口之外，假如与操作的结果为0000如此两端点的区域码任何位均不同时为1，此直线不一定被裁剪。
③以上两种情况之外的直线，有可能穿过窗口，也有可能不