多边形裁剪算法
前面我们讲了直线的裁剪算法，现在把问题推广到多边形——如何用一个裁剪窗口去裁切一个多边形，得到窗口内部的多边形部分。
基本概念
多边形裁剪算法按裁剪窗口的复杂程度分为两类：
- 凸窗口裁剪：裁剪窗口是矩形或凸多边形。典型算法有 Sutherland–Hodgman、Weiler–Atherton 等。
- 任意复杂裁剪：裁剪窗口可以是凹多边形、自交多边形甚至带洞区域。典型算法有 Vatti、Greiner–Hormann 等。
下面分别介绍这两类中最经典的算法。
凸窗口裁剪：Sutherland–Hodgman 算法
Sutherland–Hodgman 是图形学中最经典的多边形裁剪算法，适用于凸裁剪窗口（矩形或凸多边形）。
核心思想：逐步约束
矩形窗口可以看作四个半平面的交集：
最终合法区域就是
基于这一点，我们一次只处理窗口的一条边：先用左边界裁剪多边形，得到的结果再用右边界裁剪……依次通过四条边界后，多边形就同时满足了所有约束，完全落在窗口内部。这种逐边处理、逐步收紧约束的思想称为逐步约束（Incremental Clipping）。
裁剪规则
对于窗口的一条边，我们遍历多边形的每条边
| 起点 |
终点 |
输出 |
|---|---|---|
| 内部 | 内部 | |
| 内部 | 外部 | 交点 |
| 外部 | 内部 | 交点 |
| 外部 | 外部 | 无 |
四种情况覆盖了所有可能，处理完所有边后输出的顶点序列就是当前边界裁剪的结果。
算法步骤
- 初始化：将原始多边形的顶点序列作为输入列表。
- 逐边界迭代：依次取出裁剪窗口的每条边界（如左、右、下、上）。
- 逐边裁剪：对于当前边界，新建空的输出列表。遍历输入多边形的每条边
，按上表规则输出顶点到新列表。 - 状态传递：当前边界处理完毕后，将输出列表作为下一条边界裁剪时的输入。
- 循环结束：四条边界全部处理完成后，最终列表就是裁剪后的多边形顶点。
算法示例
裁剪窗口
待裁剪多边形为菱形，顶点为：
第一步：上边界裁剪（
| 边 | 位置 | 输出 |
|---|---|---|
| 外 → 内 | 交点 |
|
| 内 → 内 | ||
| 内 → 内 | ||
| 内 → 外 | 交点 |
结果：[(10,10), (15,5), (5,-5), (-5,5), (0,10)]（顶部尖角被削平）
第二步：右边界裁剪（
| 边 | 位置 | 输出 |
|---|---|---|
| 内 → 外 | 交点 |
|
| 外 → 内 | 交点 |
|
| 其余点均在内部 | 内 → 内 | 原样输出 |
结果：[(10,10), (10,0), (5,-5), (-5,5), (0,10)]（右侧尖角被削平）
第三步：下边界裁剪（
底部
结果：[(10,10), (10,0), (0,0), (-5,5), (0,10)]
第四步：左边界裁剪（
左侧
最终结果：[(10,10), (10,0), (0,0), (0,10)]
经过四次裁剪，菱形被完美裁切为贴合窗口的正方形。
任意复杂裁剪：Weiler–Atherton 算法
当裁剪窗口不再是简单的凸多边形，而是凹多边形、自交多边形甚至带洞区域时，Sutherland–Hodgman 算法就无能为力了。Weiler–Atherton 算法可以处理这类任意多边形之间的裁剪（并集、交集、差集）。
核心思想：降维与换轨
根据若尔当曲线定理（Jordan Curve Theorem），平面上一条不自交的闭合曲线将平面严格划分为内部和外部。
当我们求主多边形
即：
这揭示了一个关键洞察：裁剪问题本质上是一个追踪问题——沿着一条多边形的边走，在交点处判断是否需要”换轨”到另一条多边形的边上。
关键概念
规定多边形的顶点按顺时针排列。根据右手定则，多边形的内部始终在前进方向的右侧。
当
- 进入点（Entering Point）：
的边进入 的内部时产生的交点。 - 离开点（Leaving Point）：
的边离开 的内部时产生的交点。
进入点和离开点会严格交替出现。在相邻两个交点之间，路径的状态（在
算法步骤
- 求交并建链表：计算
和 的所有交点，将两者的顶点分别构建为顺时针双向循环链表。 - 插入交点并标记：将交点按几何顺序插入两个链表，标记每个交点在
上的属性——进入点（In）或离开点（Out）。 - 建立双向指针：
链表和 链表中代表同一几何点的交点持有指向彼此的指针，作为”传送门”。 - 追踪提取轮廓：
- 找到一个未被访问的进入点，从这里出发。
- 沿当前链表顺时针收集顶点。
- 遇到离开点时，跳转到另一链表继续。
- 遇到进入点时，再次跳回原链表。
- 交替进行，直到回到起点的进入点，一条闭合轮廓提取完毕。
- 循环：重复步骤 4，直到所有进入点都被访问。
算法示例
裁剪窗口
主多边形
第一步：求交点并判定性质
| 边 | 穿过的边界 | 交点 | 性质 |
|---|---|---|---|
| 上边界 |
进入点（外 → 内） | ||
| 右边界 |
离开点（内 → 外） | ||
| 右边界 |
进入点（外 → 内） | ||
| 上边界 |
离开点（内 → 外） |
第二步：构建链表
链表： 链表：
第三步：追踪
- 从未访问的进入点
出发，沿 链表顺时针走。 - 收集
，继续走到 （离开点），跳转到 链表。 - 在
链表上沿右边界顺时针向下，遇到 （进入点），跳回 链表。 - 在
链表上顺时针走，收集 ，走到 （离开点），跳转到 链表。 - 在
链表上沿上边界顺时针向右，回到起点 ，路径闭合。
最终结果：[I_1(6,10), I_2(10,6), I_3(10,4), V_3(4,4), I_4(4,10)]
不借助任何复杂的布尔运算，仅凭”沿着边走 + 交点处换轨”，就完美提取出了三角形落在正方形内部的五边形部分。
这次的插图来自画师 Aio
图片地址：https://www.pixiv.net/artworks/130669402