【引入】
1. 为什么要裁剪？——使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的知识图形的一部分。因此需要确定图形哪些部分落在显示区之内，哪些落在显示区之外。这个过程就称为裁剪。
2. 点的裁剪——只需判断点的坐标在不在矩形区域内，但判断图形中每个点是否在窗口内，太费时，不可取。
3. 直线段的裁剪——为复杂图形裁剪的基础。
要裁剪一条直线段，首先要判断：
1）它是否完全落在裁剪窗口内？
2）它是否完全在窗口外？
3）如果不满足以上两个条件，则计算它与一个或多个裁剪边界的交点。
常用的裁剪算法有三种：Cohen-Sutherland、中点分割法、Liang-Barsky裁剪算法。
一、Cohen-Sutherland算法（编码裁剪算法）
1. 算法原理：
对每条直线分三种情况处理：
1）若点P1和P2完全在裁剪窗口内，“简取”之。
2）若P1（x1，y1）和P2（x2，y2）均在窗口外，且满足下列四个条件之一，“简弃”。
x1 < xleft 且 x2 < xleft
x1 > xright 且 x2 > xright
y1 < ybottom 且 y2 < ybottom
y1 > ytop 且 y2 > ytop
3）如果直线段既不满足“简取”条件，也不满足“简弃”条件，需要对直线进行分段，然后判断是“简取”还是“简弃”。
2. 编码
1° 每条线段的端点都赋以四位二进制码D3D2D1D0，编码规则如下：
若 x < xleft，则D0 = 1，否则D0 = 0；——对应左边界
若 x > xright，则D1 = 1，否则D1 = 0；——对应右边界
若 y < ybottom，则D2 = 1，否则D2 = 0；——对应下边界
若 y > ytop，则D3 = 1，否则D3 = 0；——对应上边界
窗口及其延长线所构成了9个区域。根据该编码规则：
2° 裁剪一条线段时，先求出端点p1和p2的编码code1和code2，然后进行二进制“或”运算和“与”运算
1）若code1丨code2 = 0，对直线段应简取；
2）若code1 & code2 ≠ 0，对直线应简弃；
3）若上述两条件均不成立，则需求出直线段与窗口边界的交点，在交点处把线段一分为二；
下面根据该算法步骤裁剪如图所示的直线段P1P2，按照左右上下的顺序求出直线段与窗口左边界的交点为P3，P1P3必在窗口外，可简弃。对P2P3重复上述处理。
剩下的直线段P3P4再进一步判断，code1 丨code2 = 0，全在窗口中，简取。
3. 算法评价：比较适合两种情况，一是大部分线段完全可见；二是大部分线段完全不可见。
二、中点分割算法
1. 算法思想：和Cohen-Sutherland算法一样首先对直线段的端点进行编码，然后通过二分逼近来确定直线段与窗口的交点。
2. 步骤：
1° 对直线段的端点进行如Cohen-Sutherland算法一样的编码，符合简取条件简取，符合简弃条件简弃；
2° 如果不符合简取和简弃条件，则二分求中点，分成两条线段，若中点不在窗口内，则把中点里窗口边界最远点构成的线段丢掉，保留另一半；
3° 重复步骤1°2°直到中点与窗口边界的坐标值在规定的误差范围内相等；
三、Liang-Barsky算法
1. 核心思想：
1）直线方程用参数方程表示；
x = x1 + u · (x2 - x1) = x1 + ∆x · u
y = y1 + u · (y2 - y1) = y1 + ∆y · u (0 ≤ u ≤ 1)
2）把被裁剪的直线段看成是一条有方向的线段，把窗口的四条边分成两类：入边和出边。
3）裁剪结果的线段起点就是直线和两条入边的交点以及始端点三个点里参数u最大的点；
裁剪线段的终点是和两条出边的交点以及终端点三个点里参数u最小的点。
如果用u1，u2分别表示线段（u1 ≤ u2）可见部分的开始和结束，则有：
u1 = max(0, ul, ub) u2 = min(1, ut, ur)
2. 参数：
变形得
继续变形得
令：
’3. 步骤：
1° 输入直线段的两端点坐标(x1, y1)、(x2, y2)，以及窗口的四条边界坐标：xl, xr, yt, yb；
2° 若∆x = 0，则P1=P2=0，此时进一步判断是否满足q1<0或q2<0，若满足，则该直线不在窗口内，跳转7°结束；否则，满足q1≥0且q2≥0，则进一步计算Umax和Umin：
Umax = max（0，Uk丨pk<0） Umin = min（1，Uk丨pk>0）
其中Uk = qk / pk （pk ≠ 0，k = 3,4），算法跳转5°；
3° 若∆y = 0，则P3=P4=0，此时进一步判断是否满足q3<0或q4<0，若满足，则该直线不在窗口内，跳转7°结束；否则，满足q3≥0且q4≥0，则进一步计算Umax和Umin：
Umax = max（0，Uk丨pk<0） Umin = min（1，Uk丨pk>0）
其中Uk = qk / pk （pk ≠ 0，k = 1,2），算法跳转5°；
4° 若上述两条均不满足，则有Pk≠0（k=1,2,3,4），此时进一步计算Umax和Umin：
Umax = max（0，Uk丨pk<0） Umin = min（1，Uk丨pk>0）
其中Uk = qk / pk （pk ≠ 0，k = 1,2,3,4）；
5° 求得Umax和Umin后，进行判断：若Umax>Umin，则直线在窗口外，跳转7°；若Umax小于等于Umin，利用直线的参数方程求得所需要取得两端点；
6° 利用直线扫描转换算法绘制在窗口内的直线段；
7° 算法结束。
4. 评价：
1）如果被裁剪的图形大部分线段要么在窗口内或者要么完全在窗口外，很少贯穿窗口的。Cohen-Sutherland算法效果非常好；一般情况下Liang-Barsky算法的效率则优于Cohen-Sutherland算法；
2）Cohen-Sutherland算法和Liang-Barsky算法只能运用于矩形窗口。