1. 裁剪不是切萝卜先认清结果必须是一个闭合环1.1 多边形裁剪到底在算什么先从一个实际场景说起。我之前做地图可视化的时候需要把全国范围的湖泊数据裁剪到北京市边界里任务本身看起来就是一行的需求把多边形A和窗口多边形B求交集。可真正动手之后问题一个接一个冒出来——有的湖泊被切成了两半有的湖泊边界上多出一条奇怪的连线还有的结果多边形面积突然变成了负数。多边形裁剪算法简单说就是给定一个被裁剪多边形和一个裁剪窗口多边形输出窗口内部的部分。应用面比你想象中广GIS里的行政边界切割、CAD的布尔运算、地图编辑器里的遮罩、游戏引擎里的区域遮挡剔除甚至3D渲染流水线里对视锥体裁剪的思想也和它同源。但这个问题的麻烦程度和它的定义完全不成正比。裁剪线段很简单一根线只要算两个交点就能得到可见段裁剪多边形却要保证输出仍是一个或多个有序的闭合顶点环。换句话说裁剪算法输出的不是一堆散点而是具备拓扑关系的多边形边界。1.2 为什么直线裁剪的经验在这里全部失灵我见过很多刚接触这个领域的人第一反应都是逐条边去判断和窗口边的交点然后拼起来结果拼出来的图形千奇百怪。原因在于多边形经过裁剪后可能被切成多个互不相连的区域。比如一个形状像哑铃的多边形中间细窄部分被一个矩形窗口切掉剩下左右两块是独立的环。如果只是简单地把它们串成一个顶点序列中间必然会出现一条幽灵桥——一条实际并不存在的连线把两段区域硬生生连起来。这条线在视觉上是一个自交的伪多边形在面积计算里更是一场灾难。所以一个合格的多边形裁剪算法至少要解决三件事交点的精确计算、交点之间的连接顺序、以及输出多个独立环的能力。评价一个算法好不好很大程度上就是看它在处理边界情况和拓扑关系时靠不靠谱。2. Sutherland-Hodgman最不挑剔的入门算法2.1 把“二维裁剪”降维成四次“半平面测试”Sutherland-Hodgman下简称SH是几乎所有图形学教科书都会讲的第一种多边形裁剪算法。它的核心思想非常优雅二维空间里判断一个点是否在多边形内部很麻烦但判断一个点是否在一条直线的某一侧却极其简单。SH算法把裁剪窗口拆成一条条有向边每次用窗口的一条边对整个被裁剪多边形做一次半平面裁剪。窗口如果有四条边就依次做四次如果窗口是任意凸多边形就依次做N次。每次裁剪的输出是下一次裁剪的输入像流水线一样层层过滤。这里的关键点在于窗口必须预先统一成逆时针方向。这样对任意一条窗口边来说内侧都统一判定为点在边的左侧内部判定只需要计算一次叉积。我之前写过一个版本没做标准化顺时针和逆时针窗口在交替出现时输出就偶尔正确偶尔错误排查了一整天才发现是方向问题。2.2 四种case和实现细节对每个窗口边执行裁剪时需要遍历当前多边形的所有顶点并始终保留上一个顶点作为状态。上一个顶点和当前顶点相对于窗口边的内外关系组合起来只有四种情况上一个顶点在内当前顶点在内直接保留当前顶点上一个顶点在内当前顶点在外保留交点这个点是从内到外的出点上一个顶点在外当前顶点在外什么都不保留上一个顶点在外当前顶点在内保留交点和当前顶点这个点是从外到内的进点。很多人觉得SH实现很简单其实细节都在顺序里。你在输出列表里是先加交点再加当前顶点还是反过来直接决定了结果顶点环的方向和闭合性。我最初照着网上一个简写版本抄顶点顺序是反的最后所有多边形面积都变成负数。2.3 手算演算一个简单三角形拿一个具体例子被裁剪三角形为 A(0,0)、B(10,0)、C(5,8)裁剪窗口为矩形 (2,2) 到 (8,6)。第一步用窗口左边 x2 裁剪三角形会失去左侧的三角形小角输出 A1(2,1.6)、B(10,0)、C(5,8)、A2(2,4)这一步能直观看出SH的裁剪实际上是插入交点并删除外侧顶点。第二步用窗口右边 x8 裁剪上一步的输出中 B(10,0) 在外侧会算出交点并替换掉B。经过三、四步处理后最终得到的是一个由5个顶点组成的闭合多边形顶点顺序保持逆时针。手算一遍的好处是能立刻体会到SH做的事情并不是重新构造边界而是不断用直线切割旧的顶点环。理解了这一点后面看凹窗口为什么出问题就很容易了。3. Weiler-Atherton凹多边形裁剪的正确打开方式3.1 SH算法在凹窗口前失效的原因SH算法有一个硬性前提裁剪窗口必须是凸多边形。原因在于凸多边形的内域可以被表示为一系列半平面的交集逐条边裁剪不会破坏拓扑结构。可一旦窗口凹进去SH的逐边切逻辑就会出问题。举个例子L形窗口有一条凹槽被裁剪多边形横跨凹槽上方。用SH逐边裁剪后输出的顶点环会在凹口附近出现一条直接跨越空洞的连线把实际上分隔开的两块区域错误地连在一起。我第一次遇到这个问题时还以为是精度导致交点算错打印出所有顶点反复看才发现算法逻辑本身就没考虑交点之后该往哪走。SH只在当前窗口边的半空间里做判断它不知道也不关心交点在窗口另一条边上的路由关系。3.2 交点分类进点与出点Weiler-AthertonWA算法换了一个完全不同的思路。它先把两个多边形的所有交点全部求出来并将每个交点同时插入两个多边形的顶点链表中然后给每个交点打标记进点entry或出点exit。进点和出点的判定方法是看被裁剪多边形在这条边上的走向如果被裁剪多边形的一个顶点在裁剪窗口外部而下一个顶点在内部那这两个顶点之间的交点就是进点反过来从内到外的交点就是出点。这个分类是整个算法的核心。一旦知道哪些点是进点、哪些是出点裁剪结果边界的遍历规则就变得非常自然沿着被裁剪多边形走遇到出点时切换到裁剪窗口的边继续走遇到进点时再切回被裁剪多边形的边。3.3 从进点到出点的双向遍历具体遍历时算法从任意一个尚未访问的进点出发沿着被裁剪多边形的顶点走路上遇到的所有顶点都加入结果遇到第一个出点后切换路径沿着裁剪窗口的边继续走直到遇到下一个与之对应的进点再切回被裁剪多边形。这样在一个闭环上走完一圈就得到了一个完整的结果环。如果一个进点走完之后还有其他未访问的进点说明交集有多个独立连通区域需要继续循环处理直到所有进点都被访问过。WA算法能天然处理凹窗口正是因为它维护了交点与交点之间的边归属关系——每个交点同时存在于两条边链表中路径可以在交点处切换不同区域各走各的闭环不会出现SH那种跨空洞的伪连线。4. 从参数化到整数坐标另一条更工程化的路线4.1 Cyrus-Beck用内向法线算交点除了基于顶点遍历思想的SH和WA还有一类基于参数化直线的裁剪方法代表就是Cyrus-Beck算法。它的思路是把多边形的一条边看作参数线段 p(t) p0 t·d然后对窗口的每条边写出一个不等式约束点必须位于该边面向内侧的半平面内。每个约束会给出参数t的一个上限或下限把所有下限取最大值所有上限取最小值得到线段可见部分的参数区间。如果下限大于上限说明整条边完全不可见。这个方法在凸窗口下非常高效但要注意它本质上是线段裁剪裁剪完的可见片段还需要自己拼接成多边形闭合环拼接顺序又是一个图遍历问题。所以实际做多边形裁剪时它更多用于单条边的快速剔除和加速而不是替代WA成为最终方案。4.2 Greiner-Hormann的简化交点配对Greiner-HormannGH算法可以理解为WA的简化版。WA需要在交点插入后维护主多边形和裁剪多边形两套双向链表实现起来比较繁琐GH则直接利用进点/出点的标记在遍历过程中交替选择两条边的后继代码量更小。GH算法不需要显式的双向链表它只需要为每个交点标记它在主多边形中的下一个顶点索引以及在裁剪多边形中的下一个顶点索引然后在遍历时按状态切换用哪个表。这种设计的代价是对退化情况更敏感例如交点恰好落在顶点上时进出的判定可能出现二义性。很多开源项目里GH被当作一个看起来轻巧但需要仔细处理边界的算法来用。如果只是处理一两个简单多边形用它很舒服如果想建立一套稳定长期维护的裁剪库我更倾向于直接用下面要说到的整数坐标方案。4.3 Clipper为什么坚持用整数坐标有工程经验的读者可能听说过Clipper这个开源库它用Vatti算法实现多边形裁剪和布尔运算。Clipper一个非常鲜明的特征是所有坐标都是整数而不是浮点数。这么设计的原因很实际浮点坐标系里的两个线段交点同一个理论交点在不同计算路径下会产生微小的数值差异这些差异在多个裁剪步骤中被不断累积最终导致顶点顺序错乱、面积偏差、甚至NaN。整数坐标彻底绕开了这个问题。代价是需要先把浮点坐标放大到合适的整数范围输出时再缩放回去。我在实际项目里凡是要求结果稳定可复现的场景都会优先考虑整数坐标方案。性能上虽然有缩放开销但换来的确定性非常值。5. 边界情况与坑精度、共线、简并5.1 一次幽灵交点的完整排查过程有一次我做裁剪优化发现某个复杂多边形的输出结果里出现了一个坐标是NaN的顶点。当时我的第一反应是线段交点函数出了bug。单独拿那个多边形测试时问题又稳定复现不了只在数据量大的时候随机出现典型的间歇性故障。顺着调用栈一路排查最终定位到一个我完全没预设的条件两条线段恰好平行且重叠。我的交点函数没有处理平行分支直接进入除法分母接近零就产生了无穷大和NaN。修复方法很简单计算两条线段方向向量的叉积如果绝对值小于一个阈值就先判定平行并返回无交点。但真正让我学到东西的是这个问题暴露了背后更本质的需求——所有几何判断都不能用等于零来表达必须带容差。5.2 浮点误差导致的面目全非容差问题的表现形式多种多样。判断一个点是否在边界上、是否在边的左侧、两条边是否共线都可能因为浮点误差产生错误分类。比如一个点本来应该落在裁剪窗边界的左侧但经过多次变换后误差把它推到了右侧裁剪结果就会多出一块小三角形或者少掉一块。我在实际处理时会把所有关键判断统一封装成带epsilon的比较函数epsilon通常取1e-9到1e-6之间的值具体取决于坐标量级。如果坐标经常是几万百万级别epsilon也要相应放大否则容差就失去意义。5.3 边界上的顶点与半开口径另一类麻烦情况是顶点恰好落在裁剪窗口的边界上。这个问题比想象中频繁因为很多几何数据就是共享边界的。如果一个点同时落在两条相邻窗口边的公共顶点上它可能被重复计算成多个交点导致输出顶点列表出现重复点。为了解决这个问题工程上常用的做法是半开口径约定把每条窗口边的一端视为开放端点另一端视为闭合端点。比如约定下边界和左边界包含在内部上边界和右边界不包含在内部。这样每个边界上的点都只属于唯一一个半平面判断不会产生歧义。5.4 重合边与零面积片段的处理两个多边形共享某一段边界时交点计算会遇到更复杂的退化两条边共线且部分重叠理论上有无穷多个公共点。如果不处理交点函数要么返回false要么返回某个不稳定点结果输出中会出现大量长度为零的边。我的处理方式是在裁剪前先做一次顶点去重和短边过滤裁剪后再次清理删除相邻重复点剔除面积小于阈值的零面积环。这一步虽然看起来是善后工作但它在整个算法里占据的代码量往往比主逻辑还多。这些坑都不是独立存在的。数值误差会触发边界归属混淆边界归属混淆会产生错误交点错误交点又会导致顶点环断裂。所以一个真正可用的裁剪实现一定要把这些边界情况当作第一等公民来对待而不是等bug爆出来再逐个修补。6. 代码骨架与验证手段6.1 核心数据结构和Sutherland-Hodgman实现下面给一个可运行的SH核心实现。为了方便阅读我保留最基本的结构和容差处理#include vector #include cmath struct Pt { double x, y; }; using Polygon std::vectorPt; const double EPS 1e-9; double cross(const Pt O, const Pt A, const Pt B) { return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x); } bool inside(const Pt p, const Pt a, const Pt b) { // 裁剪窗口必须是逆时针方向内侧统一为边的左侧 return cross(a, b, p) -EPS; } bool intersect(const Pt a1, const Pt a2, const Pt b1, const Pt b2, Pt out) { Pt d1{a2.x - a1.x, a2.y - a1.y}; Pt d2{b2.x - b1.x, b2.y - b1.y}; double denom d1.x * d2.y - d1.y * d2.x; if (std::fabs(denom) EPS) return false; // 平行或共线 double t ((b1.x - a1.x) * d2.y - (b1.y - a1.y) * d2.x) / denom; double u ((b1.x - a1.x) * d1.y - (b1.y - a1.y) * d1.x) / denom; if (t -EPS || t 1.0 EPS || u -EPS || u 1.0 EPS) return false; out {a1.x t * d1.x, a1.y t * d1.y}; return true; } Polygon sutherlandHodgman(const Polygon subject, const Polygon clip) { Polygon output subject; for (size_t i 0; i clip.size(); i) { const Pt a clip[i]; const Pt b clip[(i 1) % clip.size()]; Polygon input output; output.clear(); if (input.empty()) break; Pt S input.back(); bool S_in inside(S, a, b); for (const Pt E : input) { bool E_in inside(E, a, b); Pt inter; if (S_in E_in) { output.push_back(E); } else if (S_in !E_in) { if (intersect(S, E, a, b, inter)) output.push_back(inter); } else if (!S_in E_in) { if (intersect(S, E, a, b, inter)) output.push_back(inter); output.push_back(E); } // 两个都在外侧时什么都不输出 S E; S_in E_in; } } return output; }这段代码只处理凸裁剪窗口完整应用还需要在开头做窗口方向标准化在结尾做顶点去重和零面积过滤。6.2 用随机多边形和射线法做回归测试写完算法第一件事是测试但手算的数据量远远不够。我习惯用随机多边形做压力测试随机生成一批凸多边形作为subject一组不同大小的矩形或凸多边形作为窗口裁剪后用射线法验证结果的面积是否正确。射线法本身不复杂判断一个点是否在多边形内部从该点发出一条水平射线统计与多边形边的相交次数奇数为内偶数为外。然后把裁剪结果多边形内部均匀撒点判断每个点是否同时位于subject和窗口内部再反向扫描窗口内部的点判断是否全部在结果内部。这样能在统计意义上确认裁剪结果没有多一块、没有少一块。如果你用SVG把所有测试多边形画出来很多问题一眼就能看到比如出现自交环、出现翻折的顶点顺序、出现本不该出现的尖刺。6.3 性能实测与调优建议关于性能SH对每个窗口边遍历一次当前多边形复杂度基本是O(n·m)n是窗口边数m是当前多边形顶点数。对于大量需要裁剪的多边形最常见的优化是先做外接矩形AABB粗筛subject的外接矩形如果和窗口外接矩形完全不相交直接返回空如果subject完全落在窗口内直接返回原多边形。在我自己的机器上对10万个随机多边形做矩形窗口裁剪不做任何预筛大约是几十毫秒量级加上AABB预筛后能明显看到一个数量级的提升。如果裁剪窗口固定不变还可以把窗口每条边的半平面判定参数提前算好省去每轮重复计算。真正需要处理百万级数据时可以考虑把不同多边形分发给多线程并行处理因为多边形之间完全独立是天然可并行的负载。要注意的是内存分配也很关键——避免在循环内部频繁创建新的vector尽量复用缓冲区这种工程细节对性能的影响有时候比算法本身还大。