“多边形拆分”这个需求最初是在做一套游戏编辑器工具时被逼出来的。美术在场景里用鼠标随手画了一个不规则的石头形状离线生成碰撞体的时候物理引擎压根不吃凹多边形碰撞体直接变成一个大包围盒游戏里手感怪到没法看。查了一圈引擎文档发现不管是Box2D还是Unity的碰撞逻辑底层对凸多边形的支持才是完备的凹多边形必须自己先拆成若干个凸多边形再喂给引擎。顺着这条线往深了挖才发现“多边形拆分”在计算几何里是一个覆盖面很广的经典问题三角剖分、凸分解、带孔多边形处理、单调多边形拆分全部属于这个范畴。当时网上资料不少但要么是纯论文口吻的伪代码要么是算法库的一行调用真正能让我照着落地的中文资料很少最后只能自己一步步实现顺手把过程中踩过的坑记了下来。这篇内容会从“为什么要拆分”讲起把算法选型、核心实现、边界情况处理、性能权衡这些点全部过一遍最后还会分享几个我在实际项目中遇到的典型问题。无论你是游戏开发、GIS方向还是写Canvas/SVG可视化工具只要你手头有“把一个多边形变成多个更简单的多边形”的需求这篇应该能帮你少走不少弯路。1. 为什么要做“多边形拆分”1.1 从凹凸多边形说起先从最基础的概念说起。一个多边形如果任意两点连线都在图形内部那它就是凸多边形反过来只要有一条边向着图形内部凹陷进去就是凹多边形。听起来很简单但“凹”这个字在图形学里带来的麻烦远比想象中大。物理引擎的碰撞检测就是一个特别典型的例子。像GJK这类高效的碰撞检测算法前提条件就是碰撞体必须是凸的。一旦输入凹多边形算法会直接给出错误结果或者为了求稳退化成包围盒效果惨不忍睹。渲染的时候也有类似问题很多图形API和着色器对多边形的填充要求三角形复杂多边形必须先三角化才能画出来。除了游戏和渲染地图引擎里也会遇到多边形拆分。一个复杂的地块边界经常是凹多边形需要拆分成多个区域做聚合展示或面积计算。3D打印的切片、CAD建模里的布尔运算、UI设计里的不规则图形裁剪底层都会涉及把复杂多边形拆分成简单多边形的过程。说白了这是一个很通用的“降维处理”思路目的是让后续算法处理起来更容易、更稳定。1.2 拆完之后能解决什么实际问题以我做的碰撞体生成工具为例。输入是一个凹多边形的顶点序列输出会变成一组凸多边形每个凸多边形独立作为碰撞体再由物理引擎统一管理。实测下来拆分后的碰撞效果和原形状几乎一致游戏里的角色踩在不规则石头上时不再出现“悬空”或“卡住”的违和感。另一个实际场景是Canvas绘制。把复杂多边形拆成三角形或者凸多边形之后填充、贴图、阴影处理都变得简单了。尤其在做地图可视化的时候要将一个行政区域的复杂边界以渐变填充呈现出来直接拿原始多边形去填会非常容易出现颜色溢出或者路径重叠的问题拆分之后每个子多边形独立填充效果稳定得多。还有一点容易被忽略拆分后的结果往往还能继续做用途。比如三角剖分之后可以基于三角形做面积计算、形心计算、路径规划凸分解之后可以做更可靠的射线检测和空间分区。所以“多边形拆分”不只是“把图形切碎”它实际上是一个让复杂几何对象变得可计算、可操作的关键步骤。2. 算法选型的全盘考虑2.1 三角剖分到底在解决什么问题先厘清一个概念三角剖分和凸分解是同一条路上的两个节点。三角剖分就是把一个多边形拆成若干个三角形这是图形学里最常用的处理方式。耳切法Ear Clipping是经典中的经典原理直观从多边形中不断找出一个“耳朵”一个由相邻三个顶点组成且完全位于多边形内部的三角形把它“剪掉”然后继续处理剩下的多边形直到剩下三个顶点为止。这个方法写起来简单适合中小规模的多边形。凸分解则是更进一步的拆分。它把一个凹多边形拆成若干个凸多边形凸多边形数量通常远少于三角形数量这对物理碰撞检测特别友好因为凸体数量越少物理引擎的计算压力就越小。凸分解的实现思路之一就是先用三角剖分再把相邻三角形合并成更大的凸多边形或者说从三角剖分中删除那些“多余”的对角线让多边形尽可能变大同时保持凸性。两者的关系可以这样理解三角剖分是最“细”的拆分保证稳定性和通用性凸分解是在三角剖分基础上做“聚合优化”追求更少的拆分结果。实际选型时要根据用途来决定用哪种。碰撞检测需要凸分解渲染填充只需要三角剖分就够了。2.2 为什么我选择了“耳切三角形合并”的方案选型的时候我认真比较过几种方案。Delaunay三角剖分看起来很香O(n log n)的时间复杂度生成的三角形质量也高但它的实现复杂度明显更高而且对输入多边形的合法性和顶点分布有要求。单调多边形拆分法也有它的限制需要先把多边形分解成单调片步骤更多。对我当时的需求来说输入多边形的顶点数通常不会超过几百个耳切法O(n²)的复杂度完全够用实现起来又好调试。更重要的是耳切的中间产物是三角形天然方便让我继续做“合并成凸多边形”这一步。我最后选定的方案就是预处理多边形 → 耳切法三角剖分 → 按贪心策略合并三角形 → 输出凸多边形组。整个过程像一个流水线每个环节都可以单独验证排查问题非常方便。最后补充一句如果你是在浏览器里处理几万甚至几十万个顶点那耳切法确实有点吃力可以考虑直接用Earcut这种成熟的库或者实现更复杂的扫描线算法。但作为自研工具从耳切入手理解整套计算几何思路是最扎实、也最不容易出错的路径。2.3 数据结构与方向约定动手写代码前先把约固定好不然后面全是坑。我用的是最常见的顶点数组表示方式每两个浮点数组成一个二维坐标点所有顶点按顺序排列隐含首尾相连形成封闭多边形。这样一来多边形、三角形和凸多边形都可以统一用Vec2[]表示代码里不需要为每类形状设计不同的数据结构。方向约定至关重要。同一个多边形顶点顺时针排列和逆时针排列在算法里会被当成两个完全不同的形状。耳朵检测依赖叉积的正负号判断凹凸性如果方向不统一结果会完全反过来。我的做法是在输入入口用鞋带公式计算有向面积如果面积为负就把顶点数组反转保证进入算法的多边形统一是逆时针方向。后面做的所有凸点判断、三角形面积判断都基于这个约定展开。还有一个细节要区分“闭合多边形”和“开路径”。很多人传入顶点时习惯把首尾点重复一份导致多边形看起来多了一个顶点。计算耳切时会在这里出各种莫名其妙的错。我实现里统一要求传入首尾不重复的顶点数组如果传入了就在预处理阶段删除最后一个顶点。3. 核心实现与实操细节3.1 输入预处理清理重复点、共线点和方向预处理是整个流程最容易偷懒但绝对不能偷懒的部分。我见过太多算法跑着跑着卡死最后查出来是输入里混了重复顶点或者共线顶点。重复顶点的处理很简单遍历顶点数组如果两个相邻点距离小于阈值保留其中一个删除另一个。注意这里不是只删除完全相同的点而是把所有距离过近的点都合并因为浮点计算里“完全相等”本来就不太可靠。共线点处理要更小心。共线点指的是有两个相邻边完全在一条直线上形成180度角。耳切法遇到这种顶点往往会检测成一个“平耳朵”导致三角剖分产生退化三角形面积为0后续的凸合并也会出错。我的做法是遍历每个顶点检查它和前一个点、后一个点组成的叉积绝对值是否接近0如果是就删除中间这个点同时保留首尾两个关键顶点。方向统一我用的是calculateSignedArea函数先算出有向面积负数就反转数组。这个函数后续在验证结果时也会用到所以提前写成一等公民很重要type Vec2 { x: number; y: number }; function cross(o: Vec2, a: Vec2, b: Vec2): number { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); } function signedArea(poly: Vec2[]): number { let area 0; const n poly.length; for (let i 0; i n; i) { const p poly[i]; const q poly[(i 1) % n]; area p.x * q.y - q.x * p.y; } return area / 2; }预处理之后多边形将满足三个条件顶点数大于等于3、没有重复点、没有共线点、方向为逆时针。这三个条件保证后面的步骤可以稳定运行。3.2 第一步两个字学会判断“耳朵”耳切法的核心就一句话从一个凹多边形里不断剪掉“耳朵”直到剩下一个三角形。但要真正实现“找一个真正的耳朵”这个动作需要做两件事判断一个顶点是凸点判断该顶点组成的三角形不包含其他顶点。判断凸点在逆时针方向的凸多边形里中间顶点的内角小于180度此时计算前一个点、当前点、后一个点的叉积结果应该为正。反过来叉积为负说明该顶点是凹点凹点不能作为耳朵。这里要注意浮点误差建议用一个极小阈值我习惯用1e-7而不是直接与0比较。判断三角形内是否包含其他顶点即使顶点是凸点它和前后两个顶点围成的三角形也可能包含了多边形的其他顶点那它就不是“真耳朵”。这个检查点是我最开始忽略的只判断了凸点就急着剪耳结果在稍复杂的凹多边形上直接剪碎了图形。具体实现可以这样封装const EPS 1e-7; function isConvex(a: Vec2, b: Vec2, c: Vec2): boolean { return cross(a, b, c) EPS; } function isEar(poly: Vec2[], i: number): boolean { const n poly.length; const p0 poly[(i n - 1) % n]; const p1 poly[i]; const p2 poly[(i 1) % n]; if (!isConvex(p0, p1, p2)) return false; for (let j 0; j n; j) { const v poly[j]; if (v p0 || v p1 || v p2) continue; if (pointInTriangle(v, p0, p1, p2)) return false; } return true; }这里还需要一个比较稳定的pointInTriangle实现。我比较推荐基于叉积符号统一判断的方式因为它在遇到边界点时的表现可控function pointInTriangle(p: Vec2, a: Vec2, b: Vec2, c: Vec2): boolean { const c1 cross(a, b, p); const c2 cross(b, c, p); const c3 cross(c, a, p); const hasNeg c1 -EPS || c2 -EPS || c3 -EPS; const hasPos c1 EPS || c2 EPS || c3 EPS; // 全正或全负才说明在内部边界点按外部处理 return !(hasNeg hasPos); }主循环也很直接复制一份顶点数组不断扫描第一个符合条件的耳朵顶点记录三角形然后把该顶点从数组里删除继续扫描。最终数组剩三个点时把这三个点也记录为最后一个三角形function triangulate(poly: Vec2[]): Vec2[][] { const vs poly.slice(); const triangles: Vec2[][] []; while (vs.length 3) { let found false; for (let i 0; i vs.length; i) { if (isEar(vs, i)) { const p0 vs[(i vs.length - 1) % vs.length]; const p1 vs[i]; const p2 vs[(i 1) % vs.length]; triangles.push([p0, p1, p2]); vs.splice(i, 1); found true; break; } } if (!found) { throw new Error(无法找到耳朵节点请检查输入多边形是否合法); } } triangles.push(vs); return triangles; }这段代码跑通之后你会发现一个很直观的验证方法对于一个有n个顶点的简单多边形最终三角形个数恒等于 n - 2。如果输出数量对不上一定是哪个环节处理错了。3.3 第二步把三角形合并成凸多边形三角剖分的结果已经可以用来做渲染填充了但如果是用来做碰撞体还需要做凸合并。我的目标是把相邻的三角形尽量合并成更大的凸多边形减少最终凸体的数量降低物理引擎的计算压力。最简单的策略是贪心合并遍历所有相邻三角形对判断合并后的四边形或更大多边形是否仍是凸多边形如果是就合并成一个多边形然后继续遍历新的多边形列表直到无法再合并为止。判断合并后的多边形是否是凸多边形只需遍历其所有顶点要求每个内部角的叉积符号一致在我们这个逆时针约束下即全部为大于阈值。这里最需要小心的是“相邻”的定义。两个三角形共享一条边才算相邻不能只看坐标接近。所以我在实现时给每个多边形增加了一个“邻接关系表”每次合并后更新邻接关系。关系表本质上记录的是两个多边形之间存在一条完全重合的边判断重合时不能用严格等于要用点与点之间的距离小于阈值来判断。一次简单的合并过程大概长这样找到一个共享边把两个多边形的顶点序列重新拼接成一个更大的顶点序列然后跑一次凸性校验。如果凸性校验通过就把原来的两个多边形从列表中移除加入新的合并结果。这个过程要不断重复直到一轮遍历里没有任何合并发生。从原理上说这有点像Hertel-Mehlhorn凸分解算法的思路先有三角剖分然后逐条尝试删除内部对角线删除后如果得到的多边形仍然是凸的就执行删除。区别在于Hertel-Mehlhorn对三角剖分里每条内部对角线都以固定的规则尝试而贪心合并更灵活一些。两个方案都有文献支持落到工程里像我这样的应用场景下贪心合并的代码量更小调试也更容易。实现时有一个值得优化的点不要每次合并后都从头扫描所有多边形。维护一个“待处理多边形队列”只用队列里的多边形去找邻居尝试合并能显著减少无效遍历。我最初的版本就是每次都全量扫描几百个三角形时还行到几千个三角形时明显卡顿后来改成队列更新才流畅起来。3.4 第三步结果验证与误差控制写算法到能跑只算完成了一半。剩下的一半是确认结果是正确的这在计算几何里尤其重要因为浮点数会让结果非常“微妙”地出错。我的验证流程分三步走。第一步顶点数与拓扑验证。输入的简单多边形如果有n个顶点三角剖分结果必须是 n-2 个三角形凸拆分的结果里所有多边形顶点数之和应该等于原多边形顶点数加上内部新增的点数乘以2因为每条内部对角线会把一个顶点纳入两个子多边形。用这个关系可以快速发现明显的错误。第二步面积守恒验证。拆分前后面积应该一致。由于每个子多边形都是原多边形的一部分理论上所有子多边形面积之和等于原多边形面积。浮点误差会导致有小偏差但偏差应该控制在一个极小的范围内。我的方法是计算原多边形面积再累加所有三角形或凸多边形的有向面积最后与原始面积对比误差如果超过原始面积的千分之一基本可以判定合并过程中出现了重叠或者空洞。第三步随机多边形压测。我会随机生成大量凹多边形跑完整的拆分流程用上面的面积守恒和顶点数规则去自动校验。这一步非常重要它帮我找到了很多边界条件下才触发的问题比如细长凹口、重复顶点、极小的边。我个人强烈建议你把这个测试集成到自动化脚本里每次改完代码跑一遍能少掉不少头发。关于误差控制我的统一策略是定义全局的EPS常量所有面积判断、叉积判断、距离比较都基于这个阈值。阈值取得太小比如1e-12浮点噪声会导致频繁误判取得太大比如1e-3会把一些本该保留的细微结构合并掉。在我的场景里坐标范围是[-1000, 1000]1e-7是一个比较合适的值。如果你处理的坐标范围更大阈值要相应调大一些。4. 常见问题与排查技巧4.1 顶点方向搞反了所有检测都会挂这是我第一次实现耳切法时遇到的第一个问题也是最让人头疼的一类问题。明明代码逻辑看起来完全正确但就是剪不出耳朵要么提前报错要么输出一堆彻底乱掉的三角形。后来排查发现所有问题都源于输入顶点是顺时针方向。耳朵检测里的叉积判断依赖逆时针方向方向反了以后凸点全会变成凹点凹点全会变成凸点整个算法的判断基础就崩了。排查技巧在算法入口处先打印一下有向面积的正负号。如果输入多边形的有向面积为负直接调用反转函数。记住这一步不要只在顶层入口做凡是你把顶点数组传给其他函数、其他模块时都要注意对方是否同样约定为逆时针。我曾经在集成到编辑器菜单时忘了给排序后的顶点再做方向确认结果就碰上了一个用户绘制顺序不同导致的诡异bug。4.2 共线点和退化耳朵共线点如果不去掉耳切法非常容易生成面积接近0的三角形。这种退化三角形在合并步骤里会出现各种问题比如两个边界点判断重叠或者合并后的凸性校验因为某个角度等于180度而摆动。我在跑随机压测时发现一个精心生成的多边形里共线点出现的概率远比想象高尤其是当顶点来源于用户鼠标点击时。解决的方法很简单在预处理阶段把所有相邻三个点的叉积绝对值小于阈值的中间点删除。但有个细节要注意删除共线点时要保留首尾点因为有时候首尾相接的边也会出现共线比如一个凹角两边恰好在同一条直线上这时必须让首尾点保留下来才能维持封闭多边形。还有一类情况是所谓的“退化耳朵”即三角形面积太小虽然不算共线但已经低于阈值。这种情况我建议直接在检测阶段把它放行然后在面积验证阶段统一看整体误差。过度干预退化耳朵反而容易破坏拓扑结构。4.3 自相交多边形该拒绝就拒绝耳切法要求输入必须是一个简单多边形即边不能交叉。如果输入一个自相交的多边形耳切法通常会陷入死循环或者输出完全错误的结果。我最初没有做这个检查用户传入一个“蝴蝶形”的边界时程序直接崩溃在无限循环里调试体验非常糟糕。后来我在预处理阶段增加了自相交检测。实现并不复杂遍历所有边对判断是否存在非相邻边相交。如果发现自相交直接抛出明确错误提示告诉使用者“当前实现不支持自相交多边形请先修正输入”。从工具角度来说宁可拒绝输入也比默默产出错误结果强。如果你的应用必须处理自相交多边形那就要引入更复杂的多边形正则化算法先计算交点和子区域重新构建合法的多边形集合。这是一个独立且更大的话题一般项目的精力不太建议耗在这里。4.4 顶点多时的性能取舍耳切法最朴素的实现是每次扫描整个顶点数组找第一个耳朵扫完一遍还要对每个耳朵做全量顶点包含检查最坏复杂度是O(n³)。当顶点数只有几十个时无感但到了几千个操作延迟就非常明显了。我实际用到的优化手段有三个。第一个是维护一个候选耳朵列表每次移除顶点后只更新受影响的两个或三个相邻顶点的状态而不是重新扫描所有顶点。这个优化能把复杂度降到O(n²)左右实现也不难因为移除一个顶点后可能变成“新耳朵”的只有它前后几个邻居。第二个是预处理凹凸标记用一个布尔数组记录每个顶点是凸还是凹在耳朵检测中先查这个标记可以省去前面的叉积计算。第三个是对大多边形启用“先粗拆再细拆”的策略如果多边形有几千个顶点用某种方式先把它切成几个子多边形再对每个子多边形递归执行耳切法。不过说实话如果你的工具主要处理的是几十到几百个顶点用最直接的实现就够了。过早优化反而会让代码变得难以理解维护成本直线上升。我的建议是先跑通功能再用性能分析工具定位瓶颈千万不要在第一步就铺开一堆优化逻辑。5. 实际项目落地与更多扩展思路5.1 接入编辑器工具的关键点把拆分算法接入编辑器工具时有几个额外问题需要处理。第一个是撤销重做。如果用户调整了原始多边形的顶点编辑器需要能恢复到拆分前的状态。这个不算算法问题但需要把算法调用和编辑器的命令系统绑定拆分结果不要直接破坏原始数据。我当时的做法是把原始顶点数组保存为只读对象拆分后的凸多边形组作为独立数据块编辑器任何时候都可以一键回到原始状态。第二个是拆分结果的稳定性。同一组顶点如果只是微小移动用户期望拆分结果不要发生剧烈变化。然而耳切法在某些临界情况下会突然选择完全不同的耳朵路径导致输出多边形组“跳变”。这个问题很难完全避免但可以在算法里增加一个有序性偏好每次选耳朵时如果有多个合法耳朵可以选择优先选取索引更小的顶点这样结果至少是确定性的至于更平滑的拆分映射就属于更前沿的研究范畴了。第三个是Visual Debugging。在做编辑器工具时我会增加一个调试画板把每个拆分步骤高亮显示出来。比如原始多边形用一种颜色三角形剖分结果用另一种颜色最终凸多边形组再换一种颜色并且在每一步旁边显示当前面积和顶点数。这个调试面板帮我发现了很多奇怪的边界情况可以说是写这类几何算法的“保命工具”。5.2 再往前走一步约束Delaunay、带孔多边形与布尔运算有了这套拆分工具作为基础我后来又把方向延伸到了几个更进阶的方向。第一个是约束Delaunay三角剖分。耳切法生成的三角形质量有时不太理想有些三角形特别细长在渲染抗锯齿和有限元计算场景里不友好。约束Delaunay能保证在“尽量把多边形边保留为约束边”的前提下最大化三角形的最小角。它的实现复杂度比耳切高不少但如果你的场景对三角形质量有要求值得研究。第二个是带孔多边形。很多实际形状是有洞的比如一个圆环形区域。耳切法本身不支持孔洞需要先把孔洞“桥接”到外边界构造一条边把孔洞外边界连接起来把带孔多边形变成一个复杂的简单多边形然后再跑耳切。桥接边的选择会影响最终结果质量这也是一个值得单独写一篇的细节。第三个是多边形布尔运算。有了拆分和三角化能力之后再往上是做多边形的交、并、差集。比如游戏里一个玩家角色站到水面区域时需要把水面遮罩“挖”出一个洞里来。这种情况下你要处理两个多边形的重叠关系再用拆分工具把重叠区域拆出来。这些场景我都有做过实验性实现效果不错不过坑依然很多等后面有更多实战经验再和大家分享。多边形拆分看似是个小工具实际牵扯到的计算几何问题非常多。写这篇文章时我把当年踩过的坑又重新梳理了一遍希望能给正在阅读的你一些实际帮助。如果你也在做类似的功能或者遇到其他没提到的坑欢迎在评论区留言聊聊我们一起把这块的经验积累起来。