一、为什么要切成三角形把蛋糕想象成一个简单多边形边界不自交没有洞。凸形蛋糕很好切从任意一个顶点向其他顶点各切一刀就能得到一组“扇形”三角形。凹形蛋糕比如 L 形、星形、月牙形就不能这样切有些刀口会切到蛋糕外面去。三角剖分的应用很广领域用途渲染GPU 只能绘制三角形UI 形状和地图区块都需要剖分物理引擎Box2D 等引擎只支持凸形碰撞体凹形必须先分解寻路NavMesh 由凸多边形组成GIS / CAD填充区域、计算面积、布尔运算二、两个定理定理 1三角形数量任何 n 个顶点的简单多边形都能被 n−3 条对角线切成恰好 n−2 个三角形。无论怎么切块数都一样。定理 2双耳定理Meisters 1975任何 n ≥ 4 的简单多边形至少有两个不相交的“耳朵”。耳朵连续三个顶点 (a, b, c)满足两个条件b 是凸顶点内角 180°三角形 abc 内部不包含多边形的其他顶点。满足这两个条件时可以沿 ac 一刀切下这个三角形剩下的部分仍是简单多边形。双耳定理保证了最朴素的算法一定能完成不断找耳朵、切掉直到只剩一个三角形。这就是耳切法Ear Clipping。三、算法全景算法复杂度输出特点扇形剖分O(n)三角形只适用于凸多边形耳切法O(n²)三角形简单、稳健工程上最常用如 mapbox/earcut单调多边形分解O(n log n)三角形先扫描线切成 y-单调块再线性剖分Seidel 随机算法期望 O(n log* n)三角形理论上更快实现复杂Chazelle 算法O(n)三角形理论最优几乎没人能实现约束 DelaunayCDTO(n log n)三角形三角形质量最好避免细长三角形Hertel-Mehlhorn剖分后 O(n)凸多边形块数不超过最优解的 4 倍BayazitO(n log n) 左右凸多边形结果更美观常用于物理引擎Keil 最优分解O(n³)凸多边形块数最少代价高下面用 C# 实现两个最实用的耳切法切成三角形和Hertel-Mehlhorn把三角形合并成更少的凸块。四、耳切法实现核心思路统一顶点顺序为逆时针CCW这样“凸顶点”就等价于叉积 0。用双向链表维护剩余顶点删除一个顶点是 O(1)。遍历顶点遇到耳朵就切掉并输出三角形。判断耳朵时只需检查凹顶点是否落在三角形内。凸顶点不可能挡住耳朵这是一个常用优化。usingSystem;usingSystem.Collections.Generic;usingSystem.Numerics;// Unity 中可替换为 UnityEngine.Vector2publicstaticclassGeometry{publicconstfloatEps1e-7f;/// 叉积 (b - a) × (c - a)0 表示 a→b→c 逆时针左转publicstaticfloatCross(Vector2a,Vector2b,Vector2c)(b.X-a.X)*(c.Y-a.Y)-(b.Y-a.Y)*(c.X-a.X);/// 有向面积0 表示逆时针publicstaticfloatSignedArea(IReadOnlyListVector2pts){floats0;for(inti0,jpts.Count-1;ipts.Count;ji)s(pts[j].X*pts[i].Y)-(pts[i].X*pts[j].Y);returns*0.5f;}/// 点 p 是否在逆时针三角形 abc 内含边界防止顶点恰好压在刀口上publicstaticboolPointInTriangle(Vector2p,Vector2a,Vector2b,Vector2c)Cross(a,b,p)-EpsCross(b,c,p)-EpsCross(c,a,p)-Eps;}publicstaticclassEarClipping{/// summary/// 对简单多边形做三角剖分。/// 返回顶点索引列表每 3 个为一个逆时针三角形。/// /summarypublicstaticListintTriangulate(IReadOnlyListVector2pts){vartrisnewListint();intnpts.Count;if(n3)returntris;// 1. 建立双向链表并统一为逆时针顺序varprevnewint[n];varnextnewint[n];boolccwGeometry.SignedArea(pts)0;for(inti0;in;i){inta(in-1)%n,b(i1)%n;prev[i]ccw?a:b;next[i]ccw?b:a;}intremainingn;intcur0;intstall0;// 连续多少次没找到耳朵// 2. 不断切耳朵while(remaining3){intpprev[cur],nxnext[cur];if(IsEar(pts,prev,next,p,cur,nx)){tris.Add(p);tris.Add(cur);tris.Add(nx);// 从链表中摘除 curnext[p]nx;prev[nx]p;remaining--;curnx;stall0;}else{curnx;// 转了一整圈都没找到耳朵输入可能自交或严重退化if(stallremaining){// 兜底强行切掉当前顶点避免死循环// 也可以选择抛异常tris.Add(prev[cur]);tris.Add(cur);tris.Add(next[cur]);next[prev[cur]]next[cur];prev[next[cur]]prev[cur];remaining--;curnext[cur];stall0;}}}// 3. 最后剩下的三角形tris.Add(prev[cur]);tris.Add(cur);tris.Add(next[cur]);returntris;}staticboolIsEar(IReadOnlyListVector2pts,int[]prev,int[]next,intia,intib,intic){Vector2apts[ia],bpts[ib],cpts[ic];// 条件 1b 必须是凸顶点逆时针下左转if(Geometry.Cross(a,b,c)Geometry.Eps)returnfalse;// 条件 2没有其他顶点落在三角形 abc 内for(intinext[ic];i!ia;inext[i]){Vector2ppts[i];// 与三角形顶点重合的点跳过处理挖洞时的桥接重复点if(pa||pb||pc)continue;// 只有凹顶点可能挡住耳朵boolreflexGeometry.Cross(pts[prev[i]],p,pts[next[i]])0;if(reflexGeometry.PointInTriangle(p,a,b,c))returnfalse;}returntrue;}}用法示例切一块 L 形蛋糕varcakenewListVector2{new(0,0),new(4,0),new(4,1),new(1,1),new(1,3),new(0,3)};vartrisEarClipping.Triangulate(cake);for(inti0;itris.Count;i3)Console.WriteLine($三角形:{tris[i]},{tris[i1]},{tris[i2]});// 6 个顶点 → 恰好 4 个三角形n − 2五、Hertel-Mehlhorn从三角形回到凸块物理引擎和寻路系统通常希望块数越少越好而不是一堆碎三角形。Hertel-Mehlhorn 的思路是先三角剖分再逐条检查对角线。如果删掉某条对角线后两侧合并成的多边形仍是凸的就删掉它。可以证明结果块数不超过最优凸分解的4 倍实际效果通常好得多。publicstaticclassHertelMehlhorn{/// 输入原始多边形会先做三角剖分输出凸多边形列表每个是逆时针顶点索引publicstaticListListintDecompose(IReadOnlyListVector2pts){vartrisEarClipping.Triangulate(pts);varpolysnewListListint();for(inti0;itris.Count;i3)polys.Add(newListint{tris[i],tris[i1],tris[i2]});boolmergedtrue;while(merged){mergedfalse;for(inti0;ipolys.Count!merged;i)for(intji1;jpolys.Count!merged;j){if(!FindSharedEdge(polys[i],polys[j],outintu,outintv))continue;varcandidateMerge(polys[i],polys[j],u,v);if(IsConvex(pts,candidate)){polys[i]candidate;polys.RemoveAt(j);mergedtrue;}}}returnpolys;}/// A 中有边 u→vB 中有边 v→u都是逆时针共享边方向相反staticboolFindSharedEdge(Listinta,Listintb,outintu,outintv){for(inti0;ia.Count;i){ua[i];va[(i1)%a.Count];for(intk0;kb.Count;k)if(b[k]vb[(k1)%b.Count]u)returntrue;}uv-1;returnfalse;}/// 沿共享边 (u, v) 合并两个多边形staticListintMerge(Listinta,Listintb,intu,intv){varrnewListint();// 从 A 的 v 出发绕一圈走到 uintiaa.IndexOf(v);for(intk0;ka.Count;k){intxa[(iak)%a.Count];r.Add(x);if(xu)break;}// 接着从 B 中 u 的下一个点走到 v 之前intibb.IndexOf(u);for(intk1;kb.Count;k){intxb[(ibk)%b.Count];if(xv)break;r.Add(x);}returnr;}staticboolIsConvex(IReadOnlyListVector2pts,Listintpoly){intnpoly.Count;for(inti0;in;i){varapts[poly[(in-1)%n]];varbpts[poly[i]];varcpts[poly[(i1)%n]];if(Geometry.Cross(a,b,c)-Geometry.Eps)returnfalse;}returntrue;}}L 形蛋糕用耳切法得到 4 个三角形经 Hertel-Mehlhorn 合并后得到2 个矩形这正是最优解。性能提示上面的合并用 O(k²) 两两比较便于理解。工程中应建立“边 → 多边形”的字典整体可降到接近线性。六、进阶话题1. 带洞的蛋糕中间挖了个圆经典做法是桥接法David Eberly 的论文《Triangulation by Ear Clipping》找到洞上 x 坐标最大的点 M从 M 向右发射线找到外轮廓上一个“可见”的顶点 P在 M 和 P 之间加一条来回的“缝”双向边把洞并入外轮廓得到一个退化的简单多边形直接用耳切法处理。上面IsEar中“跳过重合点”的判断就是为这种重复顶点准备的。mapbox/earcut 正是用这个方案处理洞的。2. 三角形质量耳切法容易产生细长三角形sliver会影响渲染插值精度和有限元计算的稳定性。改进方法有两种择优切耳每次选最小内角最大的那只耳朵但复杂度会变成 O(n²) 且常数更大边翻转Lawson flip剖分后对每条内部对角线检查 Delaunay 条件不满足就翻转最终得到约束 Delaunay 三角剖分。3. 稳健性陷阱工程中最容易出问题的地方问题对策浮点误差导致叉积判断出错使用 epsilon或先把坐标量化为整数Clipper 的做法或使用精确谓词Shewchuk共线点、重复点预处理时去重并移除共线顶点顶点顺序不定用有向面积统一为逆时针输入多边形自交先用 Clipper 做 Union 修复耳切法本身不处理自交找不到耳朵导致死循环加stall计数兜底如上面的代码七、业界现成库推荐mapbox/earcut耳切法加 z-order 曲线哈希加速支持洞速度极快。有 C# 移植版如 EarcutNet。poly2tri基于扫描线的约束 Delaunay 剖分支持洞三角形质量好。TriangleShewchuk学术界标杆提供质量网格和精确谓词。LibTessDotNetGLU tessellator 的 C# 移植能处理自交和多种填充规则。Clipper2多边形布尔运算和偏移常作为剖分前的“清洗”步骤。Box2D / Farseer / VelcroPhysics内置 Bayazit 凸分解。总结切蛋糕的方法可以按需求选择只要能切成三角形用耳切法代码约 80 行稳健可靠追求速度用单调分解或直接用 earcut追求三角形质量用约束 Delaunay需要尽量少的凸块物理碰撞、寻路先耳切再用 Hertel-Mehlhorn 合并或改用 Bayazit蛋糕中间有洞用桥接法把洞并入外轮廓再交给耳切法处理。