点剪裁

$P=(x,y)$ 满足 $x_{w\min}\leq x\leq xw_{\max},y_{w\min}\leq y\leq yw_{\max}$ 则保存

线段剪裁

Cohen-Sutherland 剪裁算法

• 使用编码测试减少要计算交点的次数
• 区域码
  • 位一：左边界，$x<x_{w\min}$
  • 位二：右边界，$x>x_{w\max}$
  • 位三：下边界，$y<y_{w\min}$
  • 位四：上边界，$y>y_{w\max}$
• 两端点区域码均为 0000：完全区域内
• 两端点与运算结果不为 0000：完全区域外
• 其它：求交后按左右上下顺序检测线段端点

梁友栋-Barsky 参数剪裁算法

• 诱导窗口：线段所在直线与裁剪窗口的交点线段
• 一维参数表示
  • $P_1P_2$: $P=P_1+u(P_2-P_1)$
  • $Q_1:u_1$
  • $Q_2:u_2$
• 判断参数
  • $\Delta x=x_2-x_1,\Delta y = y_2-y_1$
  • $p_1=-\Delta x,q_1=x_1-x_{w\min}$
  • $p_2=\Delta x,q_2=x_{w\max}-x_1$
  • $p_3=-\Delta y,q_3=y_1-y_{w\min}$
  • $p_4=\Delta y,q_4=y_{w\max}-y_1$
  • $r_i=\frac{q_i}{p_i}$
• $p_k$：
  • $0$: 平行
  • $<0$: 从外到内，更新 $u_1=\max(0,r_k)$
  • $>0$: 从内到外，更新 $u_2=\min(1,r_k)$
• 若 $u_1>u_2$，舍弃线段；否则根据 $u$ 求出交点

Nicholl-Lee-Nicholl 剪裁算法

• 仅适用于二维直线剪裁
• 确定 $P_1$ 与窗口相对位置（9宫格）
• 确定 $P_2$ 所在区域（$P_1$对窗口四个顶点做射线）
• 确定交点
• 比较和除法次数较少，减少了求交运算

非矩形剪裁窗口剪裁处理

• 凸多边形：参数化线段裁剪算法可以扩充
• 圆等曲线边界：涉及非线性方程
  • 圆：先舍弃外接矩形之外，再通过如到圆心距离判断
• 凹多边形：分解为一组凸多边形
  • 凹多边形判别：绕多边形叉乘出现异号
  • 向量法分解：沿出现异号的叉乘矢量对中第一条边延长线分解多边形
  • 旋转法分解：绕逆时针处理顶点，将某顶点平移到原点，顺时针顺转多边形使下一顶点落在 $x$ 轴上，若再下一点落在 $x$ 下，则多边形为凹多边形，沿 $x$ 轴分解

多边形剪裁

Sutherland-Hodgman 算法

• 按序逆时针遍历个顶点
  • 起始点和终止点都在窗口边界外侧：不增加
  • 都在内测：输出终止点
  • 外到内，增加交点和终止点
  • 内到外，增加交点
• 改进：增加点剪裁
• 缺点：凹多边形剪裁出现多余的线

Weilerr-Atherton 算法

• 预处理
  • 建立多边形顶点表和裁剪窗口顶点表
  • 求出所有交点
  • 两顶点表中相同交点间建立双向指针
• 裁剪过程：任选一交点为起点
  • 若为进点，跟踪多边形边界
  • 若为出点，跟踪窗口边界

多边形裁剪的相关问题

• 多边形窗口
  • Liang-Barskey 线段裁剪
  • Weiler 算法
• 曲线边界区域
• 文字裁剪
  • 字符串裁剪策略
  • 字符取舍策略
  • 单字符裁剪
• 外部裁剪