3．直线裁剪实例 例5.1 用编码算法裁剪如图5-3(a)所示中的直线段 AB。
图5-3 AB线段的裁剪过程
例5.2 用编码算法裁剪如图5-4(a)所示中的直线段MN。
图5-4 MN线段的裁剪过程
5.1.2 中点分割算法 算法步骤：输入线段端点p1，p2；对于端点p2： (1) p2是否可见，若可见，则它为离p1最远的可见点， 处理结束。 (2) plp2是否全不可见，若是，没有输出，处理结束。 (3) 让pa = p1，pb = p2。
边 V1V2 V2V3 V3V4 V4V5 V5V1 n (1，1) (4，-3) (-1，-2) (-4，3) (0，1) f (2，0) (3，6) (3，6) (4，0) (2，0) w [-4，1] [-5，-5] [-5，-5] [-6，1] [-4，1] w· n -3 -5 15 27 1 D· n 11 30 -13 -30 2 -1/2 tL 3/11 1/6 15/13 9/10 tu
外裁剪有两个重要的应用。
(1) 应用于凹多边形裁剪窗口的线段裁剪。如图5-9 所示线段p1p2相对于凹多边形vlv2v3v4v5v1进行裁剪。 连接v2v4，v1v2v4v5v1为凸多边形，应用Cyrus-Beck算 法，先将p1p2对此凸多边形作内裁剪得到，再将对多 边形v2v3v4v2作外裁剪，最后得到窗口内部分为和。
(4) 沿vi+1p1将多边形一分为二，一个多边形由vi+1, vi+2,…, p1vi+1组成，另一个多边形由vip1及其余顶点组 成。 (5) 对分割的两个多边形递归地重复以上步骤，直到 所有新产生的多边形均为凸，算法结束。
5.1.7 Sutherland-Hodgman逐次多边形裁剪算法 多边形由顶点表p1, p2,…, pn所定义，于是边表为p1p2, p2p3,…, pn-1pn和pn p1。算法的基本思想是将原多边形和 每次裁剪所生成的多边形逐次对裁剪窗口的每一条边 界进行裁剪。考虑图5-12(a)原多边形被窗口左边界所 裁剪，如图5-12(b)所示；生成的多边形又被窗口顶边 所裁剪，如图5-12(c)所示；继续这一过程，生成的中 间多边形被窗口的右边界，如图5-12(d)所示，直至下 边界裁剪完，如图5-12(e)所示为止。
图5-12 逐次多边形裁剪
依次考虑多边形每条边的两个端点S、P，其中P是边 的终点，S是边的起点。边SP与裁剪线之间只有4种可 能的关系，且仅对点P进行裁剪，如图5-13所示。
图5-13 边与裁剪线之间的关系
例5.7 裁剪图5-14(a)多边形的过程图
图5-14 裁剪多边形的过程
5.1.8 Weiler-Atherton多边形裁剪算法
设线段端点p的坐标为(x, y)，根据编码规则，可求 出其两个端点的编码：
若x < xL，则第1位置1，否则为0；若x > xR，则第2 位置1，否则为0；
若y < yB，则第3位置1，否则为0；若y > yT，则第4 位置1，否则为0。
2．直线裁剪方法
如图5-2所示，根据线段端点的区域编码，很容易对 一条线段的可见性进行测试：
5.1.6 凹多边形的分割算法
假定简单多边形顶点按逆时针方向给定，以单向链表 表示该多边形则算法可描述如下：
(1) 求出多边形顶点中的所有凹点。
(2) 从多边形的任一个顶点出发，沿单向链表搜索到 第1个凹点vi+1。
(3) 从凹点vi+1沿有向边vivi+1作射线，求它与多边形其 余各边的交点，取离vi+1最近的交点p1。
图5-1 二维规则裁剪窗口
点的裁剪十分简单，一个点P(x, y)位于裁 剪窗口之内的条件是： xL≤x≤xR yB≤y≤yT 其中，等号表示点(x, y)位于窗口边界上。
线段的裁剪有多种算法，但算法的基本思想都是基 于以下考虑： (1) 线段是否全不在窗口内，若是，则结束。 (2) 线段是否全在窗口内，若是，则转(4)。 (3) 计算该线段与窗口边界的交点，以此将线段分 成两部分；丢弃不可见的部分，对剩下的部分转(2)。
(4) 保留并显示该线段。
从图5-1中看到，线段ab完全可见，线段ij、kl完全不 可见，线段cd、ef 和gh都是部分可见，其中线段cd 与 窗口只有一个交点，经过一次求交点计算就可确定其 可见部分；而线段gh 和ef则必须经过两次求交计算才 能确定其可见部分。
5.1.1 Cohen-Sutherland端点编码算法
5.1.4 内裁剪与外裁剪
实际上，也可以把直线段相对于窗口外部进行裁 剪，决定线段的哪些部分位于窗口之外，保留并 显示这些位于窗口外面的部分，这样的裁剪是外 裁剪。例如，图5-8中，线段pl p2位于窗口之外的 参数值范围为 0 ≤ t < 3/11 和 9/10 < t ≤ 1 即从点(-2, 1)到(5/11, 17/11)和(61/10, 28/10)到(7, 3)的两段为可见段。
(1) 线段a：两端点编码为全0，是完全可见段； (2) 线段b：两端点编码按位逻辑与不为0，是显 然不可见段。 (3) 线段c：两端点编码按位逻辑与结果为0，用中 点分割法。
图5-6 中点分割
从p2开始，pa=p1，pb=p2，计算中点pm1，pm1pb为显 然不可见段，可抛弃，pm1代替pb；取其中点pm2， pm2pb不是显然不可见段，pm2代替pa；继续分割，直 至在给定精度下可把线段近似为一个点，然后求此 点的编码，可知该点不可见。 再从p1开始，同样得该点不可见，最终线段c为不可 见线段。
图5-7 Cyrus-Beck算法
t = - (ni· i)/(ni· w D)， D 0，i = 1, 2,…, k
(5-6)
式(5-6)可用来计算直线段p1p2与窗口R各边交点的t 值。若t值位于[0, 1]之外，则可抛弃。否则把这些t 值分为两组，一组为下限组，它由ni· > 0决定，其t D 值分布于线段起点一侧；一组为上限组，它由ni· < D 0决定，其t值分布于线段终点一侧。然后，求出下 限组的最大t值tL，上限组的最小t值tu，那么，从点 p(tL)到点p(tu)的线段就是所求的可见线段。
5.1.3 凸多边形窗口的Cyrus-Beck线裁剪算法
考虑一个凸多边形裁剪窗口R，被裁剪线段p1p2。如 图5-7所示说明算法的思想方法。
线段plp2的参数方程为：
p(t) = p1 + (p2 - p1) t (0≤t≤1) (5-1)
t为参数，当t < 0或t > 1时，表明点p(t)位于直线段的 两端点之外，可以舍去。
当凸多边形是矩形窗口，且矩形的边平行于坐标轴 时，上述算法可简化为Liang-Barsky算法，如表5-2 所示。
表5-2 Liang-Barsky算法所用的量
边 左边x=xL 右边x=xR 下边y=yB 下边y=yT n (1，0) (-1，0) (0，1) (0，-1) f (xL ,y) (xR ,y) (x ,yB) (x ,yT) W (x1-xL ,y1 – y) (x1-xR ,y1 – y) (x1-x ,y1 –yB) (x1-x ,y1 –yT) t (x1-xL) / -(x2-x1) -(x1-xR)/ (x2-x1) (y1-yB) /-(y2-y1) -(y1-yT) / (y2-y1)
用一个有内孔的凹多边形去裁剪另一个也有内孔的凹 多边形。为了便于讨论，把被裁剪多边形简称为从属 多边形，裁剪窗口称为裁剪多边形。实际上，从属多 边形被裁剪多边形裁剪后所形成的新的边界就是裁剪 多边形边界的一部分，故无须再生成新的边界。
图5-15 从属多边形与裁剪多边形
图5-10 多重窗口裁剪
5.1.5 凸多边形的判定与内法线的确定
1．多边形凹凸性的判定
设多边形由顶点序列v1, v2,…, vn定义，则其边矢量vivi+1(i = 1, 2,…, n - 1)和vnv1，算法可描述如下： 计算多边形相邻两边矢量的叉积：vnv1 × v1v2，vivi+1 × vi+1vi+2(i=1, 2,…, n - 2)以及vn-1vn × vnv1，若各叉积模的符号： (1) 全部为0，则多边形各边共线。 (2) 一部分为正，一部分为负，则多边形为凹。 (3) 全部大于0或等于0，则多边形为凸，并且沿着边的正向， 内法线指向其左侧。 (4) 全部小于0或等于0，则多边形为凸，并且沿着边的正向， 内法线指向其右侧。 此外，也可取多边形的一顶点为基点，依次计算由该顶点至多 边形相邻两个顶点矢量的叉积，其判定规则与上述相同。
第5章 图 形 裁 剪
5.1 二维裁剪 图5-1所示给出了一个规 则裁剪窗口。裁剪窗口是 左(L)、右(R)、上(T)和 下(B)四条边定义的矩形， 左下角和右上角坐标分别 为(xL, yB)和(xR, yT)。图 形裁剪就是确定哪些点、 线段或线段的一部分位于 裁剪窗口之内。位于窗口 内的点、线段或线段的一 部分保留并显示，其他部 分则被裁去。
2．凸多边形边内法矢量的确定 设多边形边矢量ve = (vex vey)，该边的法矢量为 n=
vey (nx ny) = - vex 1
n 将凸多边形顶点以顺时针方向编号， 取多边形顶点vi至vi+1，则边为vivi+1，若：
n·ivi+1 > 0，则n为内法矢量； v n·ivi+1 < 0，则n为外法矢量。 v
例5.5 Cyrus-Beck裁剪。 图5-8给出了一个五边形的裁剪窗口，其中V1(2, 0)，V2(p1(-2, 1)到p2(7, 3)。
图5-8 凸多边形窗口的线裁剪
表5-1给出了Cyrus-Beck的完整结果。
表5-1 Cyrus-Beck的完整结果
(4) 取pa pb的中点pm，若pmpb为显然不可见段，则让pb = pm，否则让pa = pm。