文档介绍：直线裁剪算法研究
摘要：直线裁剪是计算机图形学中一种重要技术，在对常用直经线裁剪算法分析基本上，针对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直线相对干窗口边界栽剪
直线裁剪算法应一方面拟定哪些直线所有保存或所有裁剪，剩余即为某些裁剪直线。对于某些裁剪直线则一方面规定出这些直线与窗口边界交点，把从交点开始在边界外某些裁剪掉。一种复杂画面中也许包具有几千条直线，为了提高算法效率，加快裁剪速度，应当采用计算量较小算法求直线与窗口边界交点。
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，阐明此两端点均在窗口边界之左，因而，直线在窗口边界之外，应予裁剪。可用将直线两个端点区域码进行与操作办法，判断直线与否在窗口之外，若与操作成果为0000则两端点区域码任何位均不同步为1，此直线不一定被裁剪。
③以上两种状况之外直线，有也许穿过窗口，也有也许不穿过窗口，如图87所示。图中所示两条直线都不符合状况②规定，但一条直线（P1P2）穿过窗口，另始终线（P3P4）不守过窗口。对此类直线可以进行如下解决：取窗口外一种端点与窗口边界比较以拟定可排除直线哪一某些，然后，把直线剩余某些与其她边界比较，这样始终到直线所有被排除或拟定直线哪一某些在窗口之内为止。可按“左