简介基于耳切法Ear Clipping的多边形三角化 C 实现核心源自 mapbox 的 earcut 库并通过 z 阶曲线散列优化顶点访问顺序能够处理无序顶点并输出三角形顶点索引。算法在经典耳切法基础上吸收了 FISTFast Industrial-Strength Triangulation与 David Eberly 的改进思路对孔洞、扭曲多边形、退化与自相交等复杂输入有较好支持适合图形学、WebGIS 或几何算法方向的开发者学习与复用。压缩包共 33 个文件体积约 4.29MB除头文件与源文件外还附带多份 CSV 测试数据如道路区域、顶点坐标与索引表以及 Visual Studio 解决方案和工程文件可在 Windows 下直接打开构建调试。已有 453 人学习下载。对想理解耳切法工程实现、快速搭建三角化测试环境的读者而言这份资源提供了可运行的完整示例既能对照源码剖析关键优化也可以将核心逻辑抽取到自有项目中使用。 很多时候你以为从某个项目里扒下来的zip包只是个普通的资源压缩包结果解压开一看里面躺着一个改变你处理图形数据方式的小东西。Earcut-Triangulation.zip就是我在做地图可视化项目时遇到过的一个典型包里面其实就是Earcut这个三角剖分库的源码和示例。工程上三角剖分就是把一个多边形拆成三角形集合任何图形引擎、渲染管线最后处理的基本单位都是三角形。Earcut解决的正是如何快速、稳定地把任意二维多边形拆成三角形这一基础问题。如果你做WebGL、Canvas绘图、GIS数据渲染、游戏碰撞体生成或者凡是涉及多边形转网格的需求这篇文章都有参考价值。我会从它的核心原理、API使用、验证链路、选型对比到真实项目中的坑一条线讲清楚。不绕弯子直接进入正题。1. 解压zip包之后Earcut到底是干嘛的第一次接触Earcut这个库的时候我正被一个多边形填充问题折磨得够呛。项目里有一段来自GIS系统的地块边界数据多边形轮廓动辄上百个顶点而且中间还带着几个洞比如地块中间有个湖泊或绿化带。我要在Canvas上做纹理填充底层是WebGL。WebGL不会认多边形它只认三角形。也就是说我必须先把这些复杂的多边形数据切成一堆小三角形然后才能绘制。当时试过几种笨办法手动把多边形区域做网格划分或者用耳朵切法自己写一个。前者效率低后者边界情况多比如凹多边形、带洞多边形、顶点重复、浮点精度误差随便一个都能让网格出现裂缝或重叠。Earcut就是在这个场景下进入视线的。它是一个基于耳切法Ear Clipping的轻量级三角剖分库由Mapbox团队维护。它的核心能力是给定一个多边形及其内洞的顶点数据返回一串三角形顶点索引。整个过程没有任何依赖一个文件就能跑而且实测速度在同类库里常年排在前面。一个很有意思的细节是它的名字。Earcut从字面拆开是耳朵切割对应的是计算几何里的经典算法每次在多边形上寻找一个凸的耳朵把它切下来再用剩余顶点构造新的多边形重复这个过程直到所有顶点都被吃掉。Earcut把所有精力都放在让这个基本算法更快、更稳上。从我这个搞前端可视化的人的角度看Earcut有几点在当时特别打动我。第一数据结构极简输入是一个扁平的坐标数组输出是一个整数索引数组没有繁琐的对象包装拷贝成本低存到GPU缓冲里也方便。第二它不只是处理简单多边形对带洞多边形、退化点都做了处理。第三它在算法层面做了优化平均复杂度接近O(n)虽然最坏情况仍然是O(n²)但实际处理几万个顶点也基本不卡顿。2. 从耳朵到三角形的全部秘密耳切法的原理与边界处理理解了Earcut解决了什么问题之后有必要拆开看看它内部是怎么干的。这不是为了重复造轮子而是只有真正理解它的工作原理才能在我们自己的项目里把它用到刀刃上。2.1 耳朵是怎么定义的要理解耳切法第一步是搞清楚耳朵的数学定义。给定一个多边形的连续三个顶点A、B、C如果角ABC是一个凸角内角小于180度并且以顶点B为顶点的这个小三角形内部不包含当前多边形集合里的任何其他顶点那么三角形ABC就是一个耳朵。这个定义看起来简单但在程序里判断却要注意几个边界情况。首先是凸点的判断取A、B、C三点通过向量叉积计算方向。叉积大于零说明是凸角小于零说明是凹角等于零说明三点共线这是一个需要单独处理的退化情况。Earcut对共线点的处理策略比较明确共线的点不会形成有效耳朵通常会被跳过或者在前置处理阶段剔除。其次要判断三角形内部不包含其他顶点这一步。Earcut直接用了一个点在三角形内的判断函数对当前剩余的所有顶点做一次遍历。这也是耳切法最耗时的部分暴力遍历会让复杂度逼近O(n²)。Earcut在这里做了一项关键优化利用一个哈希网格hash grid来缩小哪些点可能需要检查的范围而不是每次都对全部顶点做包含判断。这一步直接决定了它面对大数据量时的性能上限。2.2 一个被忽略的前置步骤三角化前的排序与索引重排Earcut的输入允许你传入洞的索引数组它会先把外轮廓与洞统一处理成一个带洞多边形集合然后做一次预处理排序。这一步做的事情是通过比较所有环的某一点坐标找到一个绝佳的起始点然后对环的顶点顺序做一致性检查。为什么要做这个因为耳切法要求多边形顶点按固定方向Earcut内部统一为逆时针排列才能保证叉积符号判断正确。用户给的顶点顺序未必规范特别是GIS数据里的轮廓顺序经常是乱的。Earcut会自动把外轮廓和洞统一到正确方向外轮廓逆时针洞顺时针。这样处理完之后算法内部的所有符号判断才能统一。这也是我一开始用Earcut经常理解错的地方。我总以为输入数据的顶点顺序会影响剖分结果其实Earcut在内部已经做了方向重排。它对输入的唯一硬性要求是每个环内的顶点顺序要保持连续不能穿插并且数据格式是二维或三维坐标的扁平数组。2.3 洞口的处理思路带洞多边形的三角剖分是很多自写方案望而却步的地方。直观上耳朵不能穿过洞否则三角形会跨越空洞区域。Earcut的做法比较巧妙它在主轮廓上找一个合适的顶点把洞桥接到主轮廓上让主轮廓和洞合并成单个多边形的顶点序列。这个桥接点选择很重要Earcut会找当前轮廓上视觉上最接近洞的一点然后在两个环上各自切开交叉连接相当于给形状开了一条割线绕洞走一圈再回来这样就把原本带洞的问题转化为无洞的耳切问题接下来交给同一套耳切流程处理。这个桥接思路本身不算新鲜但Earcut的聪明之处在于选择桥接点时用了可见性判断——只有主轮廓和洞之间的连线完全落在形状内部时才采纳否则换个点尝试。如果没有合适的连接点它会保守地认为这个洞无法处理。实际项目里遇到这种情况不多但一旦出现结果往往是剖分输出异常或直接报错下一篇踩坑部分会展开说。3. 上手实操从拿到zip到跑通第一个三角剖分理论部分讲完该动手了。下面这套流程完全基于Earcut-Triangulation.zip包里提供的内容来走我当初跑通的时候还没有这些理解现在回头看有几个步骤确实是可以直接抄作业的。3.1 解压包和引入库Earcut是零依赖的源码就是一个JavaScript文件。在Node.js环境里直接require就行在浏览器里也可以script标签引入后调用全局方法。const earcut require(./earcut.js); // 正方形四个顶点左上开始顺时针 const vertices [0, 0, 100, 0, 100, 100, 0, 100]; const triangles earcut(vertices); console.log(triangles); // 输出类似 [1, 0, 3, 3, 2, 1]表示两个三角形这里值得解释一下返回值这是一个扁平数组每三个数构成一个三角形的三个顶点索引。上面的输出表示第一个三角形由索引1、0、3对应的三个点构成第二个三角形由3、2、1对应的三个点构成。索引从输入坐标数组的第0个元素开始按第几个顶点计数而不是按数组下标计数。也就是说X坐标是第0个顶点Y坐标也是第0个顶点两者共同占用数组里的两个元素但索引只算顶点序号。3.2 带洞多边形的输入格式很多人在这一步栽过跟头。带洞多边形的调用多了一个参数holeIndices。它表示每个内洞的起始顶点在整体顶点列表里的序号。const outer [0, 0, 200, 0, 200, 200, 0, 200]; // 外框 const hole [50, 50, 150, 50, 150, 150, 50, 150]; // 洞 const allVertices outer.concat(hole); const holeIndices [4]; // 洞从第4个顶点开始 const triangles earcut(allVertices, holeIndices);关键点在于外轮廓和洞的顶点是拼接在同一个数组里的holeIndices里的值就是洞的起始顶点序号。如果外轮廓有4个顶点那么第一个洞的起始序号就是4第二个洞如果继续追加起始序号要重新计算。另外外轮廓和每个洞的顶点环都必须按环内顺序自然连续不能把不同环的顶点穿插存储。3.3 三维坐标怎么处理Earcut的第三个参数是维度默认值是2。如果你传入的是三维坐标数据比如带高度的地理坐标第三个参数传3Earcut会自动按照前两个维度做剖分第三个维度直接忽略但索引计算时仍然按三维坐标的步长跳过。const coords3d [0, 0, 10, 100, 0, 10, 100, 100, 10, 0, 100, 10]; const triangles earcut(coords3d, null, 3);这个特性在做3D地形、建筑模型墙面投影、或WebGL渲染高度图时特别实用。不用额外把数据降维直接传完整坐标Earcut自己知道取前两维做平面剖分输出索引依然对得上整个三维坐标数组。3.4 用Canvas验证剖分结果光有索引数组不渲染出来其实很难确认剖分是否正确。一个非常简单的验证方式是创建一个离屏Canvas画到页面上看效果。function drawTriangles(canvas, coords, triangles) { const ctx canvas.getContext(2d); ctx.fillStyle #f0f0f0; ctx.fillRect(0, 0, canvas.width, canvas.height); ctx.strokeStyle #333; for (let i 0; i triangles.length; i 3) { ctx.beginPath(); ctx.moveTo(coords[triangles[i] * 2], coords[triangles[i] * 2 1]); ctx.lineTo(coords[triangles[i 1] * 2], coords[triangles[i 1] * 2 1]); ctx.lineTo(coords[triangles[i 2] * 2], coords[triangles[i 2] * 2 1]); ctx.closePath(); ctx.stroke(); } }渲染出来如果三角形之间有重叠或者覆盖住了洞的区域说明剖分结果有问题。这里要特别强调一个很多人忽略的事项三角形重叠并不一定说明Earcut出错。我遇到过一种情况是洞的方向是反的导致Earcut桥接失败或者输入多边形本身是自相交的这类多边形属于不可三角剖分的几何范围Earcut的文档里明确说了它不支持自相交多边形。后面我会专门说这个坑。4. 实战场景对照Earcut在哪些环节能派上大用场讲了原理和用法接下来分享几个我自己实际用到Earcut的场景帮助你把它能做什么落在更具体的位置上。4.1 WebGL地图地块渲染这是Earcut的主场。地图上的国家边界、省市区边界、建筑物轮廓动辄上万顶点。这些数据传入WebGL之前必须变成三角形。Earcut在地图领域有非常成熟的应用案例Mapbox Vector Tile的渲染就大量依赖它。它的性能优势和极低的内存占用在这种每一帧都要重新三角剖分或者一次性剖分大量多边形的场景里会被放大到极致。实际操作中需要注意一个细节地理坐标系的经纬度数据不适合直接当平面坐标做剖分。因为经纬度在不同纬度上的实际距离不同如果直接把经纬度当成平面坐标输入剖分结果在高纬度地区会出现肉眼可见的变形。我一般的处理方式是先把经纬度投影到平面坐标系如Web Mercator投影再做剖分。Earcut本身不关心你的坐标单位它只对平面坐标负责。4.2 Canvas 2D复杂路径填充如果你只是想在Canvas 2D里填充一个带洞的多边形是不是不需要Earcut大部分情况下确实不需要Canvas自身的Path2D就能处理。但如果你的场景是把任意多边形拆成三角形集合再对每个三角形单独做渐变填充或者纹理映射Earcut就是不可替代的。我做过一个地块染色工具需求是每个地块内部按不同属性分区做斜向纹理填充。直接Canvas填充只能整块填无法逐三角形做材质变化。用Earcut把地块剖分后每个小三角形都能独立控制纹理角度和颜色视觉效果细腻很多渲染性能也稳定。4.3 游戏碰撞体和物理引擎游戏开发中很多碰撞体形状是凸多边形但关卡设计里的障碍物常常是凹的。大多数2D物理引擎如Box2D只支持凸多边形碰撞体复杂的凹形状需要拆成多个凸多边形的组合。Earcut虽然不是专门做凸分解的但可以先通过Earcut把凹多边形三角剖分再把相邻三角形合并成凸多边形或者直接把三角形网格作为碰撞体集合交给物理引擎。这在做2D横版关卡时是一条实用的管线。严格来说凸分解有更专门的库比如poly2tri配合贝塞尔曲线预处理但Earcut胜在集成成本低、结果稳定适合对碰撞精度要求不是物理级苛刻的中小型项目。5. 同场竞技Earcut和其他三角剖分方案怎么选在做项目选型的时候Earcut不是唯一选择。下面把常见的几个方案放在一张表里对比一下方便你按需选择。方案核心优势适用场景局限Earcut轻量、极快、零依赖带洞多边形支持好WebGL渲染、地图数据、Canvas大批量三角化不支持自相交多边形poly2tri支持约束边处理带洞能力强需要精确约束特定边的场景性能一般依赖相对多libtess.js强大的健壮性处理自相交和复杂退化情形复杂CAD类多边形、渲染引擎容错要求高体积大API复杂three.js ShapeUtils与Three.js生态无缝集成Three.js用户快速做形状三角化没有独立维护性能优化有限如果你已经引入Three.jsShapeUtils先用起来也不是不行但它是为通用形状设计的标准多边形的处理足够复杂大顶点量的场景性能不如Earcut。反过来如果你做的是CAD类工具输入多边形可能蕴含大量不规范数据如自相交那Earcut的直接抛错或者异常输出会让你崩溃这种情况建议直接上libtess.js。选Earcut还有一个很实际的考量——它集成极简。我在一个老项目里试过换掉自写的三角化逻辑改动量只有几十行没有引入任何新依赖因为Earcut本身就是一个文件。这种低成本无疑增加了我们做技术升级时的试错空间。6. 绕不开的坑真实项目里Earcut踩过的雷这部分是全文的重点。Earcut虽然强大但在真实业务数据上边界情况远比单元测试复杂得多。以下这些坑我从实战中一个个踩过来。6.1 自相交多边形文档里写得很清楚踩的时候才长记性Earcut官网文档有一句话This library does not work with self-intersecting polygons。我当初不以为意觉得真实业务数据怎么会有自相交结果第一次接入GIS数据就撞上了。多边形自相交指的是多边形的边与边之间有交叉这种形状严格意义上不是一个合法的简单多边形。Earcut对它不保证任何输出——可能返回奇怪索引可能直接卡住也可能在耳切时把交叉区域错误填充。问题的根因在于耳切法本身依赖点在三角形内部的判断自相交会破坏这个判断的正确性。我的排查思路如下第一步在调用eacut之前先用一条低成本的扫描线判断多边形是否自相交如果自相交就进入容错分支第二步容错分支里使用一个多边形拆分方法在自相交点处把多边形切成多个合法多边形再分别调用Earcut完成剖分。这段代码是通用性质的关键是找到自相交点并切割多边形业内常称为多边形正则化。不建议自己造轮子推荐使用turf.js里的polygon_self_intersection来处理或者如果必须在一个文件里搞定也可以直接用polygon-clipping库来做多边形归一化。总之不要心存侥幸业务数据一旦来源不可控自相交一定会出现。6.2 重复点与共线退化不报错但结果诡异有时候你的输入顶点里包含完全重复的坐标点或者三个连续顶点在同一水平线上。Earcut内部有去重和退化点剔除机制大多数情况它会自动处理。但处理结果可能不是你想的那样典型的特征是输出三角形数量少于预期。比如你要给一个形状做面积估算期望剖分出来50个三角形结果只出来40个一部分三角形面积被Earcut默认合并了。它之所以会这么做是因为退化三角形面积接近0对渲染没有任何帮助它的去重逻辑会优先牺牲这部分顶点换来的是更稳定的索引输出。这个行为在渲染上是优点但在需要严格三角形计数或顶点一一对应的场景里需要特别注意。如果你必须保持所有顶点都被使用需要把共线点提前做偏移微调或者改用其他允许约束的方案。我的处理方式是在进入Earcut之前对数据做一轮顶点清洗把距离小于某个容差的点合并并记录合并映射。这样既保证了Earcut内部的稳定性又能让我们拿到准确的顶点与三角形的对应关系。6.3 坐标数值过大带来的精度问题地图数据经常使用带6位以上小数位的经纬度或者超大范围的投影坐标系数值比如X坐标在百万级别。这种情况下浮点误差会被耳切法内部的叉积计算放大典型表现是三角形之间出现细小的裂缝这在渲染时表现为多边形边缘有锯齿或半透明缝隙。Earcut虽然对数值精度有处理但遇到极端跨度一个多边形横跨几百公里时还是会遇到精度问题。我的实践是做一个归一化预处理把多边形的所有坐标先减去包围盒的最小X和最小Y让数值落在相对较小的范围内三角剖分完成后再把顶点索引映射回原坐标值。这样做的代价很小能明显提升剖分稳定性。如果你同时还要做碰撞检测归一化后的坐标反而更容易做浮点运算。6.4 带洞多边形桥接失败无报错的异常输出前面说Earcut在处理洞的时候做桥接桥接需要主轮廓和洞之间有可见连接线。如果洞过度远离主轮廓或者主轮廓太狭窄复杂桥接可能失败。Earcut采用了一种缓存退避策略如果找不到理想的桥接点它可能会把洞当作独立的多边形单独剖分而不是作为一个空洞排除。这种异常的可怕之处在于它不报错也不返回异常值只是三角形穿过了洞的区域直观表现为纹理把洞填上了。排查方法是三角剖分结束后做一个面积校验。从输入多边形算出外轮廓面积和洞面积再从剖分结果算出所有三角形的总面积带符号面积或绝对值面积都行对比两者是否接近。如果差出一个洞的面积量级就可以断定桥接失败。修复桥接失败没有通用银弹一个比较稳的做法是在调用Earcut前手动扩大洞的边缘让洞与主轮廓保持一个合理的间隙或者把洞的位置做一次微小平移让桥接点更容易找到实在不行就把带洞多边形拆成多个无洞的多边形分别处理。工程上我认为第三招最靠谱毕竟拆分后的结果是确定的、可控的。7. 让Earcut更快性能调优的几个实测方向前面提到Earcut本身够快但在大顶点量数据场景还是可以通过一些手段压榨出更多性能。7.1 预处理顶点合并几千个顶点的多边形往往包含大量视觉上不敏感、但数值上存在微小抖动的点。在一次渲染场景里这些点没有影响但在每帧都需要三角剖分的场景里它们会显著拖慢速度。对我常用的地块数据一个简单的Douglas-Peucker抽稀算法能把顶点数减少40%以上而形状误差肉眼几乎不可见。Earcut的剖分时间跟顶点数强相关所以抽稀是性价比最高的优化。7.2 避免频繁创建大数组Earcut的输入输出都是数组JS引擎在GC时对超大数组的回收是有代价的。如果你在动画循环里频繁调用Earcut建议复用输入数组而不是每次new一个新数组同时缓存输出的索引数组以便复用。这一点在移动端WebGL场景下尤其敏感我做过一次对比试验复用数组的方案比每次新建数组的方案在长时间帧序列里能减少约30%的明显卡顿。7.3 把Earcut放Web Worker里跑如果你的多边形数据量极大十万级顶点Earcut的计算耗时可能超过16ms这会导致动画掉帧。把Earcut丢到Web Worker里做剖分主线程只负责接收索引并上传GPU渲染和剖分流水线并行体感流畅度会有质的提升。Earcut本身没有环境依赖Worker里直接跑完全没问题这也是它轻量属性带来的隐形福利。8. 验证剖分正确性的标准化流程最后分享一套我自己整理的验证清单。每当我改完三角剖分管线都会按这套流程自测一遍能拦截绝大多数隐藏问题。面积一致性校验计算输入多边形的有符号面积总和外轮廓正、洞负和剖分结果所有三角形的带符号面积之和做对比误差超过0.1%视为剖分异常。索引合法性校验所有三角形索引必须在[0, 顶点数)这个区间内出现负数或越界基本都是数据错误。边界完整性校验把剖分结果所有三角形的边收集起来外轮廓的边界边出现次数必须是1洞边界的边界边出现次数也必须是1内部共享边出现次数必须是2。不满足说明剖分有裂缝或重叠。洞区域校验在带洞多边形场景中随机采样洞内部几个点确认这些点没有被任何三角形覆盖。这套校验流程不用每次都跑全量的数学计算但在数据源切换、Earcut版本升级、算法参数修改这三个节点上最好都执行一遍。跑一次也就几毫秒但能免去很多查半天查不出原因的渲染Bug。做好这些前置校验Earcut在绝大多数业务场景里都能稳定发挥。它虽然是个轻量到不能再轻量的库但深入进去会发现图形学里那些基础问题真的到了工程落地上处处都是细节。本文还有配套的精品资源点击获取
Earcut三角剖分库的工程实践：原理、应用场景与踩坑全解析
简介基于耳切法Ear Clipping的多边形三角化 C 实现核心源自 mapbox 的 earcut 库并通过 z 阶曲线散列优化顶点访问顺序能够处理无序顶点并输出三角形顶点索引。算法在经典耳切法基础上吸收了 FISTFast Industrial-Strength Triangulation与 David Eberly 的改进思路对孔洞、扭曲多边形、退化与自相交等复杂输入有较好支持适合图形学、WebGIS 或几何算法方向的开发者学习与复用。压缩包共 33 个文件体积约 4.29MB除头文件与源文件外还附带多份 CSV 测试数据如道路区域、顶点坐标与索引表以及 Visual Studio 解决方案和工程文件可在 Windows 下直接打开构建调试。已有 453 人学习下载。对想理解耳切法工程实现、快速搭建三角化测试环境的读者而言这份资源提供了可运行的完整示例既能对照源码剖析关键优化也可以将核心逻辑抽取到自有项目中使用。 很多时候你以为从某个项目里扒下来的zip包只是个普通的资源压缩包结果解压开一看里面躺着一个改变你处理图形数据方式的小东西。Earcut-Triangulation.zip就是我在做地图可视化项目时遇到过的一个典型包里面其实就是Earcut这个三角剖分库的源码和示例。工程上三角剖分就是把一个多边形拆成三角形集合任何图形引擎、渲染管线最后处理的基本单位都是三角形。Earcut解决的正是如何快速、稳定地把任意二维多边形拆成三角形这一基础问题。如果你做WebGL、Canvas绘图、GIS数据渲染、游戏碰撞体生成或者凡是涉及多边形转网格的需求这篇文章都有参考价值。我会从它的核心原理、API使用、验证链路、选型对比到真实项目中的坑一条线讲清楚。不绕弯子直接进入正题。1. 解压zip包之后Earcut到底是干嘛的第一次接触Earcut这个库的时候我正被一个多边形填充问题折磨得够呛。项目里有一段来自GIS系统的地块边界数据多边形轮廓动辄上百个顶点而且中间还带着几个洞比如地块中间有个湖泊或绿化带。我要在Canvas上做纹理填充底层是WebGL。WebGL不会认多边形它只认三角形。也就是说我必须先把这些复杂的多边形数据切成一堆小三角形然后才能绘制。当时试过几种笨办法手动把多边形区域做网格划分或者用耳朵切法自己写一个。前者效率低后者边界情况多比如凹多边形、带洞多边形、顶点重复、浮点精度误差随便一个都能让网格出现裂缝或重叠。Earcut就是在这个场景下进入视线的。它是一个基于耳切法Ear Clipping的轻量级三角剖分库由Mapbox团队维护。它的核心能力是给定一个多边形及其内洞的顶点数据返回一串三角形顶点索引。整个过程没有任何依赖一个文件就能跑而且实测速度在同类库里常年排在前面。一个很有意思的细节是它的名字。Earcut从字面拆开是耳朵切割对应的是计算几何里的经典算法每次在多边形上寻找一个凸的耳朵把它切下来再用剩余顶点构造新的多边形重复这个过程直到所有顶点都被吃掉。Earcut把所有精力都放在让这个基本算法更快、更稳上。从我这个搞前端可视化的人的角度看Earcut有几点在当时特别打动我。第一数据结构极简输入是一个扁平的坐标数组输出是一个整数索引数组没有繁琐的对象包装拷贝成本低存到GPU缓冲里也方便。第二它不只是处理简单多边形对带洞多边形、退化点都做了处理。第三它在算法层面做了优化平均复杂度接近O(n)虽然最坏情况仍然是O(n²)但实际处理几万个顶点也基本不卡顿。2. 从耳朵到三角形的全部秘密耳切法的原理与边界处理理解了Earcut解决了什么问题之后有必要拆开看看它内部是怎么干的。这不是为了重复造轮子而是只有真正理解它的工作原理才能在我们自己的项目里把它用到刀刃上。2.1 耳朵是怎么定义的要理解耳切法第一步是搞清楚耳朵的数学定义。给定一个多边形的连续三个顶点A、B、C如果角ABC是一个凸角内角小于180度并且以顶点B为顶点的这个小三角形内部不包含当前多边形集合里的任何其他顶点那么三角形ABC就是一个耳朵。这个定义看起来简单但在程序里判断却要注意几个边界情况。首先是凸点的判断取A、B、C三点通过向量叉积计算方向。叉积大于零说明是凸角小于零说明是凹角等于零说明三点共线这是一个需要单独处理的退化情况。Earcut对共线点的处理策略比较明确共线的点不会形成有效耳朵通常会被跳过或者在前置处理阶段剔除。其次要判断三角形内部不包含其他顶点这一步。Earcut直接用了一个点在三角形内的判断函数对当前剩余的所有顶点做一次遍历。这也是耳切法最耗时的部分暴力遍历会让复杂度逼近O(n²)。Earcut在这里做了一项关键优化利用一个哈希网格hash grid来缩小哪些点可能需要检查的范围而不是每次都对全部顶点做包含判断。这一步直接决定了它面对大数据量时的性能上限。2.2 一个被忽略的前置步骤三角化前的排序与索引重排Earcut的输入允许你传入洞的索引数组它会先把外轮廓与洞统一处理成一个带洞多边形集合然后做一次预处理排序。这一步做的事情是通过比较所有环的某一点坐标找到一个绝佳的起始点然后对环的顶点顺序做一致性检查。为什么要做这个因为耳切法要求多边形顶点按固定方向Earcut内部统一为逆时针排列才能保证叉积符号判断正确。用户给的顶点顺序未必规范特别是GIS数据里的轮廓顺序经常是乱的。Earcut会自动把外轮廓和洞统一到正确方向外轮廓逆时针洞顺时针。这样处理完之后算法内部的所有符号判断才能统一。这也是我一开始用Earcut经常理解错的地方。我总以为输入数据的顶点顺序会影响剖分结果其实Earcut在内部已经做了方向重排。它对输入的唯一硬性要求是每个环内的顶点顺序要保持连续不能穿插并且数据格式是二维或三维坐标的扁平数组。2.3 洞口的处理思路带洞多边形的三角剖分是很多自写方案望而却步的地方。直观上耳朵不能穿过洞否则三角形会跨越空洞区域。Earcut的做法比较巧妙它在主轮廓上找一个合适的顶点把洞桥接到主轮廓上让主轮廓和洞合并成单个多边形的顶点序列。这个桥接点选择很重要Earcut会找当前轮廓上视觉上最接近洞的一点然后在两个环上各自切开交叉连接相当于给形状开了一条割线绕洞走一圈再回来这样就把原本带洞的问题转化为无洞的耳切问题接下来交给同一套耳切流程处理。这个桥接思路本身不算新鲜但Earcut的聪明之处在于选择桥接点时用了可见性判断——只有主轮廓和洞之间的连线完全落在形状内部时才采纳否则换个点尝试。如果没有合适的连接点它会保守地认为这个洞无法处理。实际项目里遇到这种情况不多但一旦出现结果往往是剖分输出异常或直接报错下一篇踩坑部分会展开说。3. 上手实操从拿到zip到跑通第一个三角剖分理论部分讲完该动手了。下面这套流程完全基于Earcut-Triangulation.zip包里提供的内容来走我当初跑通的时候还没有这些理解现在回头看有几个步骤确实是可以直接抄作业的。3.1 解压包和引入库Earcut是零依赖的源码就是一个JavaScript文件。在Node.js环境里直接require就行在浏览器里也可以script标签引入后调用全局方法。const earcut require(./earcut.js); // 正方形四个顶点左上开始顺时针 const vertices [0, 0, 100, 0, 100, 100, 0, 100]; const triangles earcut(vertices); console.log(triangles); // 输出类似 [1, 0, 3, 3, 2, 1]表示两个三角形这里值得解释一下返回值这是一个扁平数组每三个数构成一个三角形的三个顶点索引。上面的输出表示第一个三角形由索引1、0、3对应的三个点构成第二个三角形由3、2、1对应的三个点构成。索引从输入坐标数组的第0个元素开始按第几个顶点计数而不是按数组下标计数。也就是说X坐标是第0个顶点Y坐标也是第0个顶点两者共同占用数组里的两个元素但索引只算顶点序号。3.2 带洞多边形的输入格式很多人在这一步栽过跟头。带洞多边形的调用多了一个参数holeIndices。它表示每个内洞的起始顶点在整体顶点列表里的序号。const outer [0, 0, 200, 0, 200, 200, 0, 200]; // 外框 const hole [50, 50, 150, 50, 150, 150, 50, 150]; // 洞 const allVertices outer.concat(hole); const holeIndices [4]; // 洞从第4个顶点开始 const triangles earcut(allVertices, holeIndices);关键点在于外轮廓和洞的顶点是拼接在同一个数组里的holeIndices里的值就是洞的起始顶点序号。如果外轮廓有4个顶点那么第一个洞的起始序号就是4第二个洞如果继续追加起始序号要重新计算。另外外轮廓和每个洞的顶点环都必须按环内顺序自然连续不能把不同环的顶点穿插存储。3.3 三维坐标怎么处理Earcut的第三个参数是维度默认值是2。如果你传入的是三维坐标数据比如带高度的地理坐标第三个参数传3Earcut会自动按照前两个维度做剖分第三个维度直接忽略但索引计算时仍然按三维坐标的步长跳过。const coords3d [0, 0, 10, 100, 0, 10, 100, 100, 10, 0, 100, 10]; const triangles earcut(coords3d, null, 3);这个特性在做3D地形、建筑模型墙面投影、或WebGL渲染高度图时特别实用。不用额外把数据降维直接传完整坐标Earcut自己知道取前两维做平面剖分输出索引依然对得上整个三维坐标数组。3.4 用Canvas验证剖分结果光有索引数组不渲染出来其实很难确认剖分是否正确。一个非常简单的验证方式是创建一个离屏Canvas画到页面上看效果。function drawTriangles(canvas, coords, triangles) { const ctx canvas.getContext(2d); ctx.fillStyle #f0f0f0; ctx.fillRect(0, 0, canvas.width, canvas.height); ctx.strokeStyle #333; for (let i 0; i triangles.length; i 3) { ctx.beginPath(); ctx.moveTo(coords[triangles[i] * 2], coords[triangles[i] * 2 1]); ctx.lineTo(coords[triangles[i 1] * 2], coords[triangles[i 1] * 2 1]); ctx.lineTo(coords[triangles[i 2] * 2], coords[triangles[i 2] * 2 1]); ctx.closePath(); ctx.stroke(); } }渲染出来如果三角形之间有重叠或者覆盖住了洞的区域说明剖分结果有问题。这里要特别强调一个很多人忽略的事项三角形重叠并不一定说明Earcut出错。我遇到过一种情况是洞的方向是反的导致Earcut桥接失败或者输入多边形本身是自相交的这类多边形属于不可三角剖分的几何范围Earcut的文档里明确说了它不支持自相交多边形。后面我会专门说这个坑。4. 实战场景对照Earcut在哪些环节能派上大用场讲了原理和用法接下来分享几个我自己实际用到Earcut的场景帮助你把它能做什么落在更具体的位置上。4.1 WebGL地图地块渲染这是Earcut的主场。地图上的国家边界、省市区边界、建筑物轮廓动辄上万顶点。这些数据传入WebGL之前必须变成三角形。Earcut在地图领域有非常成熟的应用案例Mapbox Vector Tile的渲染就大量依赖它。它的性能优势和极低的内存占用在这种每一帧都要重新三角剖分或者一次性剖分大量多边形的场景里会被放大到极致。实际操作中需要注意一个细节地理坐标系的经纬度数据不适合直接当平面坐标做剖分。因为经纬度在不同纬度上的实际距离不同如果直接把经纬度当成平面坐标输入剖分结果在高纬度地区会出现肉眼可见的变形。我一般的处理方式是先把经纬度投影到平面坐标系如Web Mercator投影再做剖分。Earcut本身不关心你的坐标单位它只对平面坐标负责。4.2 Canvas 2D复杂路径填充如果你只是想在Canvas 2D里填充一个带洞的多边形是不是不需要Earcut大部分情况下确实不需要Canvas自身的Path2D就能处理。但如果你的场景是把任意多边形拆成三角形集合再对每个三角形单独做渐变填充或者纹理映射Earcut就是不可替代的。我做过一个地块染色工具需求是每个地块内部按不同属性分区做斜向纹理填充。直接Canvas填充只能整块填无法逐三角形做材质变化。用Earcut把地块剖分后每个小三角形都能独立控制纹理角度和颜色视觉效果细腻很多渲染性能也稳定。4.3 游戏碰撞体和物理引擎游戏开发中很多碰撞体形状是凸多边形但关卡设计里的障碍物常常是凹的。大多数2D物理引擎如Box2D只支持凸多边形碰撞体复杂的凹形状需要拆成多个凸多边形的组合。Earcut虽然不是专门做凸分解的但可以先通过Earcut把凹多边形三角剖分再把相邻三角形合并成凸多边形或者直接把三角形网格作为碰撞体集合交给物理引擎。这在做2D横版关卡时是一条实用的管线。严格来说凸分解有更专门的库比如poly2tri配合贝塞尔曲线预处理但Earcut胜在集成成本低、结果稳定适合对碰撞精度要求不是物理级苛刻的中小型项目。5. 同场竞技Earcut和其他三角剖分方案怎么选在做项目选型的时候Earcut不是唯一选择。下面把常见的几个方案放在一张表里对比一下方便你按需选择。方案核心优势适用场景局限Earcut轻量、极快、零依赖带洞多边形支持好WebGL渲染、地图数据、Canvas大批量三角化不支持自相交多边形poly2tri支持约束边处理带洞能力强需要精确约束特定边的场景性能一般依赖相对多libtess.js强大的健壮性处理自相交和复杂退化情形复杂CAD类多边形、渲染引擎容错要求高体积大API复杂three.js ShapeUtils与Three.js生态无缝集成Three.js用户快速做形状三角化没有独立维护性能优化有限如果你已经引入Three.jsShapeUtils先用起来也不是不行但它是为通用形状设计的标准多边形的处理足够复杂大顶点量的场景性能不如Earcut。反过来如果你做的是CAD类工具输入多边形可能蕴含大量不规范数据如自相交那Earcut的直接抛错或者异常输出会让你崩溃这种情况建议直接上libtess.js。选Earcut还有一个很实际的考量——它集成极简。我在一个老项目里试过换掉自写的三角化逻辑改动量只有几十行没有引入任何新依赖因为Earcut本身就是一个文件。这种低成本无疑增加了我们做技术升级时的试错空间。6. 绕不开的坑真实项目里Earcut踩过的雷这部分是全文的重点。Earcut虽然强大但在真实业务数据上边界情况远比单元测试复杂得多。以下这些坑我从实战中一个个踩过来。6.1 自相交多边形文档里写得很清楚踩的时候才长记性Earcut官网文档有一句话This library does not work with self-intersecting polygons。我当初不以为意觉得真实业务数据怎么会有自相交结果第一次接入GIS数据就撞上了。多边形自相交指的是多边形的边与边之间有交叉这种形状严格意义上不是一个合法的简单多边形。Earcut对它不保证任何输出——可能返回奇怪索引可能直接卡住也可能在耳切时把交叉区域错误填充。问题的根因在于耳切法本身依赖点在三角形内部的判断自相交会破坏这个判断的正确性。我的排查思路如下第一步在调用eacut之前先用一条低成本的扫描线判断多边形是否自相交如果自相交就进入容错分支第二步容错分支里使用一个多边形拆分方法在自相交点处把多边形切成多个合法多边形再分别调用Earcut完成剖分。这段代码是通用性质的关键是找到自相交点并切割多边形业内常称为多边形正则化。不建议自己造轮子推荐使用turf.js里的polygon_self_intersection来处理或者如果必须在一个文件里搞定也可以直接用polygon-clipping库来做多边形归一化。总之不要心存侥幸业务数据一旦来源不可控自相交一定会出现。6.2 重复点与共线退化不报错但结果诡异有时候你的输入顶点里包含完全重复的坐标点或者三个连续顶点在同一水平线上。Earcut内部有去重和退化点剔除机制大多数情况它会自动处理。但处理结果可能不是你想的那样典型的特征是输出三角形数量少于预期。比如你要给一个形状做面积估算期望剖分出来50个三角形结果只出来40个一部分三角形面积被Earcut默认合并了。它之所以会这么做是因为退化三角形面积接近0对渲染没有任何帮助它的去重逻辑会优先牺牲这部分顶点换来的是更稳定的索引输出。这个行为在渲染上是优点但在需要严格三角形计数或顶点一一对应的场景里需要特别注意。如果你必须保持所有顶点都被使用需要把共线点提前做偏移微调或者改用其他允许约束的方案。我的处理方式是在进入Earcut之前对数据做一轮顶点清洗把距离小于某个容差的点合并并记录合并映射。这样既保证了Earcut内部的稳定性又能让我们拿到准确的顶点与三角形的对应关系。6.3 坐标数值过大带来的精度问题地图数据经常使用带6位以上小数位的经纬度或者超大范围的投影坐标系数值比如X坐标在百万级别。这种情况下浮点误差会被耳切法内部的叉积计算放大典型表现是三角形之间出现细小的裂缝这在渲染时表现为多边形边缘有锯齿或半透明缝隙。Earcut虽然对数值精度有处理但遇到极端跨度一个多边形横跨几百公里时还是会遇到精度问题。我的实践是做一个归一化预处理把多边形的所有坐标先减去包围盒的最小X和最小Y让数值落在相对较小的范围内三角剖分完成后再把顶点索引映射回原坐标值。这样做的代价很小能明显提升剖分稳定性。如果你同时还要做碰撞检测归一化后的坐标反而更容易做浮点运算。6.4 带洞多边形桥接失败无报错的异常输出前面说Earcut在处理洞的时候做桥接桥接需要主轮廓和洞之间有可见连接线。如果洞过度远离主轮廓或者主轮廓太狭窄复杂桥接可能失败。Earcut采用了一种缓存退避策略如果找不到理想的桥接点它可能会把洞当作独立的多边形单独剖分而不是作为一个空洞排除。这种异常的可怕之处在于它不报错也不返回异常值只是三角形穿过了洞的区域直观表现为纹理把洞填上了。排查方法是三角剖分结束后做一个面积校验。从输入多边形算出外轮廓面积和洞面积再从剖分结果算出所有三角形的总面积带符号面积或绝对值面积都行对比两者是否接近。如果差出一个洞的面积量级就可以断定桥接失败。修复桥接失败没有通用银弹一个比较稳的做法是在调用Earcut前手动扩大洞的边缘让洞与主轮廓保持一个合理的间隙或者把洞的位置做一次微小平移让桥接点更容易找到实在不行就把带洞多边形拆成多个无洞的多边形分别处理。工程上我认为第三招最靠谱毕竟拆分后的结果是确定的、可控的。7. 让Earcut更快性能调优的几个实测方向前面提到Earcut本身够快但在大顶点量数据场景还是可以通过一些手段压榨出更多性能。7.1 预处理顶点合并几千个顶点的多边形往往包含大量视觉上不敏感、但数值上存在微小抖动的点。在一次渲染场景里这些点没有影响但在每帧都需要三角剖分的场景里它们会显著拖慢速度。对我常用的地块数据一个简单的Douglas-Peucker抽稀算法能把顶点数减少40%以上而形状误差肉眼几乎不可见。Earcut的剖分时间跟顶点数强相关所以抽稀是性价比最高的优化。7.2 避免频繁创建大数组Earcut的输入输出都是数组JS引擎在GC时对超大数组的回收是有代价的。如果你在动画循环里频繁调用Earcut建议复用输入数组而不是每次new一个新数组同时缓存输出的索引数组以便复用。这一点在移动端WebGL场景下尤其敏感我做过一次对比试验复用数组的方案比每次新建数组的方案在长时间帧序列里能减少约30%的明显卡顿。7.3 把Earcut放Web Worker里跑如果你的多边形数据量极大十万级顶点Earcut的计算耗时可能超过16ms这会导致动画掉帧。把Earcut丢到Web Worker里做剖分主线程只负责接收索引并上传GPU渲染和剖分流水线并行体感流畅度会有质的提升。Earcut本身没有环境依赖Worker里直接跑完全没问题这也是它轻量属性带来的隐形福利。8. 验证剖分正确性的标准化流程最后分享一套我自己整理的验证清单。每当我改完三角剖分管线都会按这套流程自测一遍能拦截绝大多数隐藏问题。面积一致性校验计算输入多边形的有符号面积总和外轮廓正、洞负和剖分结果所有三角形的带符号面积之和做对比误差超过0.1%视为剖分异常。索引合法性校验所有三角形索引必须在[0, 顶点数)这个区间内出现负数或越界基本都是数据错误。边界完整性校验把剖分结果所有三角形的边收集起来外轮廓的边界边出现次数必须是1洞边界的边界边出现次数也必须是1内部共享边出现次数必须是2。不满足说明剖分有裂缝或重叠。洞区域校验在带洞多边形场景中随机采样洞内部几个点确认这些点没有被任何三角形覆盖。这套校验流程不用每次都跑全量的数学计算但在数据源切换、Earcut版本升级、算法参数修改这三个节点上最好都执行一遍。跑一次也就几毫秒但能免去很多查半天查不出原因的渲染Bug。做好这些前置校验Earcut在绝大多数业务场景里都能稳定发挥。它虽然是个轻量到不能再轻量的库但深入进去会发现图形学里那些基础问题真的到了工程落地上处处都是细节。本文还有配套的精品资源点击获取
