“多边形拆分”这个需求，最初是在做一套游戏编辑器工具时被逼出来的。美术在场景里用鼠标随手画了一个不规则的石头形状，离线生成碰撞体的时候，物理引擎压根不吃凹多边形，碰撞体直接变成一个大包围盒，游戏里手感怪到没法看。查了一圈引擎文档，发现不管是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能保证在“尽量把多边形边保留为约束边”的前提下，最大化三角形的最小角。它的实现复杂度比耳切高不少，但如果你的场景对三角形质量有要求，值得研究。
第二个是带孔多边形。很多实际形状是有洞的，比如一个圆环形区域。耳切法本身不支持孔洞，需要先把孔洞“桥接”到外边界，构造一条边把孔洞外边界连接起来，把带孔多边形变成一个复杂的简单多边形，然后再跑耳切。桥接边的选择会影响最终结果质量，这也是一个值得单独写一篇的细节。
第三个是多边形布尔运算。有了拆分和三角化能力之后，再往上是做多边形的交、并、差集。比如游戏里，一个玩家角色站到水面区域时，需要把水面遮罩“挖”出一个洞里来。这种情况下，你要处理两个多边形的重叠关系，再用拆分工具把重叠区域拆出来。这些场景我都有做过实验性实现，效果不错，不过坑依然很多，等后面有更多实战经验再和大家分享。
多边形拆分看似是个小工具，实际牵扯到的计算几何问题非常多。写这篇文章时，我把当年踩过的坑又重新梳理了一遍，希望能给正在阅读的你一些实际帮助。如果你也在做类似的功能，或者遇到其他没提到的坑，欢迎在评论区留言聊聊，我们一起把这块的经验积累起来。
