简介Earcut-Triangulation.zip 是一份基于耳切法Ear Clipping的多边形三角化实现源自 mapbox/earcut 的 C 移植与改进面向需要处理多边形网格、碰撞检测或地理数据渲染的图形开发者。算法通过 z 阶曲线散列进行优化可支持带孔洞、自相交、退化等复杂多边形并输出可直接用于渲染或几何运算的顶点索引序列。压缩包共 33 个文件、约 4.29MB其中包含 10 个 h 头文件、4 个 hpp 头文件、7 个 c 源文件和 2 个 cpp 源文件覆盖接口声明与核心算法实现另有 4 个 csv 测试数据如 in_RoadArea.csv、vertex.csv和 2 个 txt 说明文档便于对比验证剖分效果同时附带 Visual Studio 的 sln、vcxproj、filters 工程文件可一键打开编译。目前已有 454 人学习下载。通过学习源码可深入理解 FIST 改进算法思路、z 阶曲线散列提升耳朵查找效率的原理并结合道路区域、顶点等测试数据掌握复杂多边形三角化的实际落地方法适合具有一定 C 基础、想研究几何算法工程的开发者。1. Earcut-Triangulation.zip一份多边形三角剖分的现成算法先搞清楚它帮你省了什么事你手里的 Earcut-Triangulation.zip本质上是一份多边形三角剖分算法的可运行实现。做地图渲染、WebGL 编辑器、CAD 工具链的人迟早会撞上同样的问题一块任意形状的区域甚至中间带洞、带凹角要渲染成没有接缝的面片就必须先把多边形切成三角形。Earcut 这类算法解决的正是从“多边形顶点列表”到“三角形索引列表”的转换问题而且尽量快、尽量稳定不挑输入形状。这个包适合两类人一类是正在给渲染管线填坑的工程师多边形已经转成 Mesh 之前的最后一步差一个剖分器另一类是学习几何算法的开发者想看一套在生产环境磨过多年的耳朵裁剪Ear Clipping思路到底怎么组织代码。它不负责修复自相交多边形也不做 Delaunay 优化它只做一件事给你凸的、凹的、带洞的多边形快速吐出一串可用的三角形顶点索引。搞清楚这个边界后面用起来才不翻车。2. 先看懂输入输出格式再谈算法本身扁平数组、holes 与索引结果2.1 扁平顶点数组为什么 Earcut 不收“数组套数组”大多数人对多边形的第一反应是[[x1,y1], [x2,y2], ...]这种嵌套结构但 Earcut 系列实现几乎都坚持用扁平数组[x1, y1, x2, y2, x3, y3, ...]。这个选择不是写代码的人图省事而是有实际的性能收益。扁平数组的数据在内存里是连续排布的遍历时 CPU 缓存命中率高传给 WebGL buffer 时可以直接Float32Array一把拷进去省掉一层层解嵌套的开销GC 压力也小渲染循环里不会反复创建小对象。对于一个可能要处理几十万顶点、每帧都可能更新的场景这几项优势累加起来非常可观。// 嵌套结构的表达方式 const nested [[0, 0], [100, 0], [100, 100], [0, 100]]; // Earcut 要求的扁平数组表达方式 const flat [0, 0, 100, 0, 100, 100, 0, 100];这段代码的核心差异在于第二个数组用索引i * 2访问第 i 个顶点的 x 坐标、i * 2 1访问 y 坐标。参数层面要注意Earcut 的dim参数默认是 2如果你传入的数组里每个顶点带 z 或者带额外属性必须通过dim告诉剖分器“每隔几个数取一个顶点”否则索引会全部错位。2.2 holes 与 dim带洞多边形和三维坐标怎么传带洞多边形是 Earcut 经常被用错的地方。它的约定是外环顶点先全部排完然后依次排列各个内洞环的顶点最后用一个holes数组记录每个洞环第一个顶点在总数组里的索引。洞环的数量、顺序都不限制只要每个洞环本身是闭合的简单多边形即可。// 外环 4 个点洞环 4 个点洞的起始索引是 4 const vertices [ 0, 0, 100, 0, 100, 100, 0, 100, // 外环 25, 25, 75, 25, 75, 75, 25, 75 // 洞环 ]; const holes [4]; // 返回的是三角形顶点索引不是坐标 const triangles earcut(vertices, holes);这里的逻辑是算法拿到holes后会把每个洞通过一条内部桥接边“缝”到外环上从而把带洞多边形等价转换成一个无洞的简单多边形再统一做耳朵裁剪。参数层面有两个容易忽略的点holes里的数字是洞环起始顶点在vertices中的下标而不是“第几个环”dim2时顶点按两位一组切分如果后续你改成dim3holes的索引依旧指向顶点序号跟坐标维度无关。2.3 耳朵裁剪与切线策略剖分结果为什么是一串下标耳朵裁剪的直觉很简单在多边形边界上找一个凸顶点它和前后两个相邻顶点组成的三角形如果没包住其他顶点就把它剪下来然后删掉这个顶点对剩下的多边形重复这个过程。Earcut 的改进在于裁剪时对候选耳朵做定向的边相交检查并用固定半径搜索代替全量扫描所以平均复杂度能压到接近 O(n log n)而不是最朴素的 O(n²)。// 典型输出每个三角形由 3 个顶点索引组成 // [1, 0, 3, 3, 2, 1] 表示两个三角形(1,0,3) 和 (3,2,1) const triangles earcut([0, 0, 100, 0, 100, 100, 0, 100]); console.log(triangles);这段代码的输出含义很关键triangles里存的全是顶点下标不是坐标。三角形(1,0,3)表示取第 1 号顶点、第 0 号顶点、第 3 号顶点组成一个三角形。不同移植版本输出顺序可能略有差异但“索引指向顶点数组”这个约定是统一的。另外一个常见误读是认为输出会按三角形扇面顺序排列实际上 Earcut 不保证这种结构它就是一组无序但完整的三角形列表渲染时不需要关心顺序。3. 解开 zip 动手跑通从最小调用到可视化验证3.1 先确认你拿到的是哪一种实现Earcut-Triangulation.zip 在不同环境里流传的版本形态不一样最常见的是两种纯 JavaScript 单文件版和 C 单头文件版。前者直接require就能跑适合前端 WebGL 和 Node.js 脚本后者是.hpp头文件实现适合 C 桌面应用或服务端批处理。两者算法同源数据结构约定一致只是调用入口和模板参数不同。拿到 zip 后我建议先看一眼根目录结构不要急着写代码。重点确认三件事入口函数叫什么名字头文件/模块导出的形参顺序是(vertices, holes, dim)以及返回值是std::vectorint还是Array。确认完这三个点直接跳到自己对应语言的示例即可。3.2 JavaScript 版最小调用一个四边形和一个带洞五边形// 引入模块具体路径以你解压出的文件为准 const earcut require(./earcut.js); // 例 1简单四边形 const quad [0, 0, 100, 0, 100, 100, 0, 100]; const t1 earcut(quad); console.log(t1); // 三角形顶点索引 // 例 2带一个洞的矩形 const outer [0, 0, 200, 0, 200, 200, 0, 200]; const inner [50, 50, 150, 50, 150, 150, 50, 150]; const t2 earcut(outer.concat(inner), [8]); console.log(t2);第一个例子里t1的长度是 6正好对应 2 个三角形。第二个例子把外环和洞环拼成一个数组洞的起始索引写的是 8因为外环 4 个点占了 8 个数字。注意这里concat之后holes参数必须传[8]如果写成[4]算法会从洞环中间切开输出的三角形直接乱掉。参数层面还要留意earcut的第三个参数dim默认是 2holes不传或传null都表示无洞。3.3 C 头文件版的最小调用注意模板与命名空间#include earcut.hpp #include array #include vector #include iostream // 约定每个点只有 x, y 两个分量 using Point std::arraydouble, 2; using Ring std::vectorPoint; using Polygon std::vectorRing; int main() { // 外环 Ring outer {{0, 0}, {100, 0}, {100, 100}, {0, 100}}; // 洞环 Ring hole {{25, 25}, {75, 25}, {75, 75}, {25, 75}}; Polygon polygon; polygon.push_back(outer); polygon.push_back(hole); // 入口函数命名以 zip 内头文件实际声明为准 std::vectorint triangles /* 命名空间:: */earcutint(polygon); for (int idx : triangles) { std::cout idx ; } return 0; }C 版的输入是嵌套vector跟 JS 版扁平数组的直观感受不同但模板内部会把嵌套结构展开成同样的处理逻辑。模板参数int指定的是输出索引的类型坐标是double索引用int可以省内存。编译时一般不需要额外链接库直接g -O2 -stdc17 main.cpp -o tri_demo即可。命名空间每家移植版可能不同写之前看一眼头文件最稳妥。3.4 把结果画出来SVG 兜底可视化索引数组抽象直接看数字不容易发现几何错误。最快的验证方式是把剖分结果转成 SVG 多边形在浏览器里一眼看出三角形有没有漏缝、有没有穿洞。// 根据 vertices 和 triangles 生成 SVG 片段 function toSVG(vertices, triangles, w 200, h 200) { let parts svg width${w} height${h} xmlnshttp://www.w3.org/2000/svg; for (let i 0; i triangles.length; i 3) { const pts [triangles[i], triangles[i 1], triangles[i 2]] .map(v ${vertices[v * 2]},${vertices[v * 2 1]}) .join( ); parts polygon points${pts} fillrgba(80,180,80,0.3) stroke#333/; } return parts /svg; }这段代码的作用是把每个三角形单独画成一个半透明绿色多边形描边用深色。三角形之间如果出现透明缝隙或者重叠区域立刻能看出来。参数说明vertices必须是扁平数组triangles是 Earcut 返回的索引数组v * 2之所以成立是因为默认维度dim2。如果用了dim3这里要改成v * 3。4. 实际项目中的三个调参位epsilon、dimensions 与数据预处理4.1 epsilon什么场景该调什么场景千万别碰Earcut 的参数列表里epsilon不显眼默认 0很多人从来不改。它的作用是控制“点与点、点与边”视为重合的容差当两个顶点距离小于 epsilon会先合并当一个顶点到某条边的距离小于 epsilon计算上会当作在边上。这个参数能救你也能害你。我一般只在两类场景调大 epsilon一是坐标经过了投影变换后数值特别大比如几百万量级浮点运算带来的抖动会让原本共线的点出现亚像素偏移二是输入数据本身是从 GIS 工具导出的天然带精度噪声不合并就会出现大量细长三角形。自定义模型、人工手绘的多边形保持默认 0 就好调大了反而会把真实的凹角给合并掉剖分结果与预期不符。参数默认值建议场景不建议场景epsilon0大坐标、带噪声数据、需要批量去重精确建模、坐标已归一化dim2纯平面 XY 数据三维数据但想丢 Z 时设为 3holesnull带洞多边形外环与洞环顺序混乱时先修正// 大坐标场景下的 epsilon 用法 const tri earcut(vertices, null, 2, 0.001);代码里的第四个参数0.001表示 0.001 单位内的点视为重合。注意epsilon 不修复自相交也不修复洞方向错误这些问题在进入算法前就该被处理掉。4.2 dimensions3三维模型的 Z 轴怎么处理如果顶点数据是三维模型导出的每个点带[x, y, z]直接按dim2切分会把 z 当成下一个点的 x剖分结果完全错误。正确的做法是把dim设为 3告诉算法“三个数一组只取前两个参与剖分”。const vertices3d [ 0, 0, 5, 1, 1, 5, 2, 0, 5, 3, 1, 5 ]; // 第三个参数 3每组数据含 x,y,z内部只用 x,y 剖分 const tris earcut(vertices3d, null, 3); // 遍历三角形顶点索引时坐标读取步长也要改成 3这里最容易踩的坑是索引数组依旧只指向“第几个顶点”而不是“第几个数字”。比如返回索引 1对应的坐标在vertices3d[3]和vertices3d[4]不是vertices3d[1]。渲染时如果用顶点索引去访问Float32Array步长必须跟dim保持一致。4.3 数据预处理三件事去重、平移缩放、洞环排序Earcut 的容错能力没你想的那么强输入质量直接决定输出质量。我在每次把数据交给剖分器之前都会强制走三步预处理第一把坐标值平移到接近原点的范围再按比例缩放第二相邻重复点直接合并第三确认洞环都在外环内部且洞环之间不互相包含。// 平移加缩放把坐标范围缩放到 [0, 100] 区间 function normalize(vertices) { let minX Infinity, minY Infinity, maxX -Infinity, maxY -Infinity; for (let i 0; i vertices.length; i 2) { minX Math.min(minX, vertices[i]); maxX Math.max(maxX, vertices[i]); minY Math.min(minY, vertices[i 1]); maxY Math.max(maxY, vertices[i 1]); } const scale Math.max(maxX - minX, maxY - minY) || 1; return vertices.map((v, idx) idx % 2 0 ? ((v - minX) / scale) * 100 : ((v - minY) / scale) * 100 ); }这段代码做了两件事减掉最小值保证坐标不从巨大数值开始除以边长最大值把整体范围压到 100 以内。参数说明scale取宽高较大者保证等比缩放不变形|| 1防止所有点重合时除零。预处理完再剖分结果用逆变换映射回原始坐标数值精度问题能被压到最低。5. 常见问题排查五种剖分翻车现场及对策5.1 自相交多边形剖分“成功”但面片全乱现象剖分函数正常返回了索引数组三角形数量也对但渲染出来的面片互相穿插有的区域重复覆盖有的区域直接镂空。原因Earcut 的前提是输入必须是简单多边形也就是边除了相邻边端点外不能互相交叉。自相交输入属于未定义行为算法不会报错只会给出看似合理实则错乱的结果。解决在调用剖分之前做一次自相交检测。最直观的办法是把多边形先画到离屏 canvas 或者用射线法逐边交叉检查发现相交就用多边形裁剪库做布尔运算拆分成多个简单多边形再分别剖分。不要指望 epsilon 能修这个问题。5.2 洞的起点索引算错三角形直接跨进洞里现象带洞多边形剖分后本应镂空的洞里被填上了三角形周围区域的三角形也出现不规则延伸。原因holes数组里的索引在拼数组时算错了一位。最常见的是把洞环的“第几个点”当成索引比如洞环第 4 个点写成了 4但实际外环有 6 个点洞的起点在总数组里的下标是 12。解决写一个小工具函数动态计算洞环起点。外环顶点数组拼接完成后记录下outer.length每个洞环拼进去之前先把当前位置记录到holes数组。这个顺序永远不要手算。// 动态计算 holes 起点避免手算出错 const vertices []; const holes []; outer.forEach(p vertices.push(p.x, p.y)); holes.push(vertices.length / 2); // 外环结束后第一个洞的起点 inner.forEach(p vertices.push(p.x, p.y)); holes.push(vertices.length / 2); // 第二个洞的起点注意到vertices.length / 2是浮点运算但length永远是偶数结果恒为整数可以安全使用。5.3 重复顶点与几乎重合点剖分卡顿甚至超时现象多边形顶点数不多但剖分耗时异常高极端情况下浏览器标签页直接卡死。原因数据源里有大量重复顶点或者距离极近的点耳朵裁剪判断“三角形是否包含其他点”时这些近重合点造成大量无效计算还有一种情况是环没闭合首尾点没对齐算法在最后一步永远剪不干净。解决预处理时按 epsilon 把邻近距离小于阈值的点合并并检查环的首尾点是否相等。如果首尾点差值小于阈值直接 drop 掉尾点。5.4 全共线或近零面积多边形返回空数组而不是报错现象所有顶点在同一条直线上或者自交后实际围成面积几乎为零的多边形Earcut 返回一个空数组没有异常。原因算法找不到任何有效的耳朵选择直接结束。这不是 bug而是这类多边形本来就没有可剖分的三角面。解决调用前用鞋带公式算面积面积绝对值小于某个阈值直接跳过不要把空数组当成 bug 传给上层的渲染逻辑。渲染层收到空索引数组时应直接隐藏该面片而不是报错。5.5 大坐标值导致细长三角形和渲染裂缝现象坐标从几百万起始剖分结果出现大量极细长三角形拼出来的面片在线框模式下看着还行填充渲染时相邻三角形之间出现暗线或裂缝。原因大坐标值在浮点计算中损失低位精度三角形共享边的顶点坐标经过两次独立计算后可能产生极小偏差光栅化时这条边被画了两次或者一次都没画上。解决先做 4.3 的平移缩放把坐标范围压到小尺度渲染时去掉多边形共享边的描边或者把顶点位置用gl_Position计算后再做一次偏移。简单粗暴的方式是把渲染背景色设置成多边形填充色同色掩盖掉那条亚像素缝。6. 验证剖分结果的三个技巧面积守恒、方向检测与测试固件剖分器输出结果后直接灌进渲染管线是很冒险的做法。我习惯先跑三个快速验证全部通过再往下走。第一个技巧是面积守恒检测把返回的三角形逐个算面积并累加跟原多边形面积比对。带洞的场景里外环面积减掉所有洞面积才是理论值三角形面积累加如果跟理论值对不上说明剖分结果有遗漏或重叠。// 按三角形索引累加面积返回绝对值 function trianglesArea(vertices, tris) { let sum 0; for (let i 0; i tris.length; i 3) { const ax vertices[tris[i] * 2], ay vertices[tris[i] * 2 1]; const bx vertices[tris[i 1] * 2], by vertices[tris[i 1] * 2 1]; const cx vertices[tris[i 2] * 2], cy vertices[tris[i 2] * 2 1]; sum ax * (by - cy) bx * (cy - ay) cx * (ay - by); } return Math.abs(sum) / 2; }这段代码直接用叉积公式累计有符号面积再取绝对值。注意这里假设所有三角形同向如果混了方向累加前要统一符号否则正负抵消后面积偏小。第二个技巧是方向检测渲染开背面剔除后面片消失多半是三角形绕序反了。把每个三角形的叉积符号取出来全部同号说明方向一致不一致就翻转三角形。Earcut 的输出通常跟输入环方向一致但如果你在预处理时旋转过环方向就可能丢。第三个技巧是攒一个测试固件把一组有代表性的多边形凸、凹、带洞、带多个洞连同验证函数写进自动化测试每次改数据前跑一遍。这个方法救过我很多次比任何代码审查都管用。我自己的习惯是任何新项目里引入 Earcut第一件事不是写具体业务而是先把测试固件搭起来后面所有重构都基于这套固件回归。几何算法翻车往往是悄悄发生的有自动化兜底心里才有底。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/15 16:02:43 · 阅读 1.2k 多边形三角剖分算法Earcut实战解析：从耳朵裁剪原理到参数调优
简介Earcut-Triangulation.zip 是一份基于耳切法Ear Clipping的多边形三角化实现源自 mapbox/earcut 的 C 移植与改进面向需要处理多边形网格、碰撞检测或地理数据渲染的图形开发者。算法通过 z 阶曲线散列进行优化可支持带孔洞、自相交、退化等复杂多边形并输出可直接用于渲染或几何运算的顶点索引序列。压缩包共 33 个文件、约 4.29MB其中包含 10 个 h 头文件、4 个 hpp 头文件、7 个 c 源文件和 2 个 cpp 源文件覆盖接口声明与核心算法实现另有 4 个 csv 测试数据如 in_RoadArea.csv、vertex.csv和 2 个 txt 说明文档便于对比验证剖分效果同时附带 Visual Studio 的 sln、vcxproj、filters 工程文件可一键打开编译。目前已有 454 人学习下载。通过学习源码可深入理解 FIST 改进算法思路、z 阶曲线散列提升耳朵查找效率的原理并结合道路区域、顶点等测试数据掌握复杂多边形三角化的实际落地方法适合具有一定 C 基础、想研究几何算法工程的开发者。1. Earcut-Triangulation.zip一份多边形三角剖分的现成算法先搞清楚它帮你省了什么事你手里的 Earcut-Triangulation.zip本质上是一份多边形三角剖分算法的可运行实现。做地图渲染、WebGL 编辑器、CAD 工具链的人迟早会撞上同样的问题一块任意形状的区域甚至中间带洞、带凹角要渲染成没有接缝的面片就必须先把多边形切成三角形。Earcut 这类算法解决的正是从“多边形顶点列表”到“三角形索引列表”的转换问题而且尽量快、尽量稳定不挑输入形状。这个包适合两类人一类是正在给渲染管线填坑的工程师多边形已经转成 Mesh 之前的最后一步差一个剖分器另一类是学习几何算法的开发者想看一套在生产环境磨过多年的耳朵裁剪Ear Clipping思路到底怎么组织代码。它不负责修复自相交多边形也不做 Delaunay 优化它只做一件事给你凸的、凹的、带洞的多边形快速吐出一串可用的三角形顶点索引。搞清楚这个边界后面用起来才不翻车。2. 先看懂输入输出格式再谈算法本身扁平数组、holes 与索引结果2.1 扁平顶点数组为什么 Earcut 不收“数组套数组”大多数人对多边形的第一反应是[[x1,y1], [x2,y2], ...]这种嵌套结构但 Earcut 系列实现几乎都坚持用扁平数组[x1, y1, x2, y2, x3, y3, ...]。这个选择不是写代码的人图省事而是有实际的性能收益。扁平数组的数据在内存里是连续排布的遍历时 CPU 缓存命中率高传给 WebGL buffer 时可以直接Float32Array一把拷进去省掉一层层解嵌套的开销GC 压力也小渲染循环里不会反复创建小对象。对于一个可能要处理几十万顶点、每帧都可能更新的场景这几项优势累加起来非常可观。// 嵌套结构的表达方式 const nested [[0, 0], [100, 0], [100, 100], [0, 100]]; // Earcut 要求的扁平数组表达方式 const flat [0, 0, 100, 0, 100, 100, 0, 100];这段代码的核心差异在于第二个数组用索引i * 2访问第 i 个顶点的 x 坐标、i * 2 1访问 y 坐标。参数层面要注意Earcut 的dim参数默认是 2如果你传入的数组里每个顶点带 z 或者带额外属性必须通过dim告诉剖分器“每隔几个数取一个顶点”否则索引会全部错位。2.2 holes 与 dim带洞多边形和三维坐标怎么传带洞多边形是 Earcut 经常被用错的地方。它的约定是外环顶点先全部排完然后依次排列各个内洞环的顶点最后用一个holes数组记录每个洞环第一个顶点在总数组里的索引。洞环的数量、顺序都不限制只要每个洞环本身是闭合的简单多边形即可。// 外环 4 个点洞环 4 个点洞的起始索引是 4 const vertices [ 0, 0, 100, 0, 100, 100, 0, 100, // 外环 25, 25, 75, 25, 75, 75, 25, 75 // 洞环 ]; const holes [4]; // 返回的是三角形顶点索引不是坐标 const triangles earcut(vertices, holes);这里的逻辑是算法拿到holes后会把每个洞通过一条内部桥接边“缝”到外环上从而把带洞多边形等价转换成一个无洞的简单多边形再统一做耳朵裁剪。参数层面有两个容易忽略的点holes里的数字是洞环起始顶点在vertices中的下标而不是“第几个环”dim2时顶点按两位一组切分如果后续你改成dim3holes的索引依旧指向顶点序号跟坐标维度无关。2.3 耳朵裁剪与切线策略剖分结果为什么是一串下标耳朵裁剪的直觉很简单在多边形边界上找一个凸顶点它和前后两个相邻顶点组成的三角形如果没包住其他顶点就把它剪下来然后删掉这个顶点对剩下的多边形重复这个过程。Earcut 的改进在于裁剪时对候选耳朵做定向的边相交检查并用固定半径搜索代替全量扫描所以平均复杂度能压到接近 O(n log n)而不是最朴素的 O(n²)。// 典型输出每个三角形由 3 个顶点索引组成 // [1, 0, 3, 3, 2, 1] 表示两个三角形(1,0,3) 和 (3,2,1) const triangles earcut([0, 0, 100, 0, 100, 100, 0, 100]); console.log(triangles);这段代码的输出含义很关键triangles里存的全是顶点下标不是坐标。三角形(1,0,3)表示取第 1 号顶点、第 0 号顶点、第 3 号顶点组成一个三角形。不同移植版本输出顺序可能略有差异但“索引指向顶点数组”这个约定是统一的。另外一个常见误读是认为输出会按三角形扇面顺序排列实际上 Earcut 不保证这种结构它就是一组无序但完整的三角形列表渲染时不需要关心顺序。3. 解开 zip 动手跑通从最小调用到可视化验证3.1 先确认你拿到的是哪一种实现Earcut-Triangulation.zip 在不同环境里流传的版本形态不一样最常见的是两种纯 JavaScript 单文件版和 C 单头文件版。前者直接require就能跑适合前端 WebGL 和 Node.js 脚本后者是.hpp头文件实现适合 C 桌面应用或服务端批处理。两者算法同源数据结构约定一致只是调用入口和模板参数不同。拿到 zip 后我建议先看一眼根目录结构不要急着写代码。重点确认三件事入口函数叫什么名字头文件/模块导出的形参顺序是(vertices, holes, dim)以及返回值是std::vectorint还是Array。确认完这三个点直接跳到自己对应语言的示例即可。3.2 JavaScript 版最小调用一个四边形和一个带洞五边形// 引入模块具体路径以你解压出的文件为准 const earcut require(./earcut.js); // 例 1简单四边形 const quad [0, 0, 100, 0, 100, 100, 0, 100]; const t1 earcut(quad); console.log(t1); // 三角形顶点索引 // 例 2带一个洞的矩形 const outer [0, 0, 200, 0, 200, 200, 0, 200]; const inner [50, 50, 150, 50, 150, 150, 50, 150]; const t2 earcut(outer.concat(inner), [8]); console.log(t2);第一个例子里t1的长度是 6正好对应 2 个三角形。第二个例子把外环和洞环拼成一个数组洞的起始索引写的是 8因为外环 4 个点占了 8 个数字。注意这里concat之后holes参数必须传[8]如果写成[4]算法会从洞环中间切开输出的三角形直接乱掉。参数层面还要留意earcut的第三个参数dim默认是 2holes不传或传null都表示无洞。3.3 C 头文件版的最小调用注意模板与命名空间#include earcut.hpp #include array #include vector #include iostream // 约定每个点只有 x, y 两个分量 using Point std::arraydouble, 2; using Ring std::vectorPoint; using Polygon std::vectorRing; int main() { // 外环 Ring outer {{0, 0}, {100, 0}, {100, 100}, {0, 100}}; // 洞环 Ring hole {{25, 25}, {75, 25}, {75, 75}, {25, 75}}; Polygon polygon; polygon.push_back(outer); polygon.push_back(hole); // 入口函数命名以 zip 内头文件实际声明为准 std::vectorint triangles /* 命名空间:: */earcutint(polygon); for (int idx : triangles) { std::cout idx ; } return 0; }C 版的输入是嵌套vector跟 JS 版扁平数组的直观感受不同但模板内部会把嵌套结构展开成同样的处理逻辑。模板参数int指定的是输出索引的类型坐标是double索引用int可以省内存。编译时一般不需要额外链接库直接g -O2 -stdc17 main.cpp -o tri_demo即可。命名空间每家移植版可能不同写之前看一眼头文件最稳妥。3.4 把结果画出来SVG 兜底可视化索引数组抽象直接看数字不容易发现几何错误。最快的验证方式是把剖分结果转成 SVG 多边形在浏览器里一眼看出三角形有没有漏缝、有没有穿洞。// 根据 vertices 和 triangles 生成 SVG 片段 function toSVG(vertices, triangles, w 200, h 200) { let parts svg width${w} height${h} xmlnshttp://www.w3.org/2000/svg; for (let i 0; i triangles.length; i 3) { const pts [triangles[i], triangles[i 1], triangles[i 2]] .map(v ${vertices[v * 2]},${vertices[v * 2 1]}) .join( ); parts polygon points${pts} fillrgba(80,180,80,0.3) stroke#333/; } return parts /svg; }这段代码的作用是把每个三角形单独画成一个半透明绿色多边形描边用深色。三角形之间如果出现透明缝隙或者重叠区域立刻能看出来。参数说明vertices必须是扁平数组triangles是 Earcut 返回的索引数组v * 2之所以成立是因为默认维度dim2。如果用了dim3这里要改成v * 3。4. 实际项目中的三个调参位epsilon、dimensions 与数据预处理4.1 epsilon什么场景该调什么场景千万别碰Earcut 的参数列表里epsilon不显眼默认 0很多人从来不改。它的作用是控制“点与点、点与边”视为重合的容差当两个顶点距离小于 epsilon会先合并当一个顶点到某条边的距离小于 epsilon计算上会当作在边上。这个参数能救你也能害你。我一般只在两类场景调大 epsilon一是坐标经过了投影变换后数值特别大比如几百万量级浮点运算带来的抖动会让原本共线的点出现亚像素偏移二是输入数据本身是从 GIS 工具导出的天然带精度噪声不合并就会出现大量细长三角形。自定义模型、人工手绘的多边形保持默认 0 就好调大了反而会把真实的凹角给合并掉剖分结果与预期不符。参数默认值建议场景不建议场景epsilon0大坐标、带噪声数据、需要批量去重精确建模、坐标已归一化dim2纯平面 XY 数据三维数据但想丢 Z 时设为 3holesnull带洞多边形外环与洞环顺序混乱时先修正// 大坐标场景下的 epsilon 用法 const tri earcut(vertices, null, 2, 0.001);代码里的第四个参数0.001表示 0.001 单位内的点视为重合。注意epsilon 不修复自相交也不修复洞方向错误这些问题在进入算法前就该被处理掉。4.2 dimensions3三维模型的 Z 轴怎么处理如果顶点数据是三维模型导出的每个点带[x, y, z]直接按dim2切分会把 z 当成下一个点的 x剖分结果完全错误。正确的做法是把dim设为 3告诉算法“三个数一组只取前两个参与剖分”。const vertices3d [ 0, 0, 5, 1, 1, 5, 2, 0, 5, 3, 1, 5 ]; // 第三个参数 3每组数据含 x,y,z内部只用 x,y 剖分 const tris earcut(vertices3d, null, 3); // 遍历三角形顶点索引时坐标读取步长也要改成 3这里最容易踩的坑是索引数组依旧只指向“第几个顶点”而不是“第几个数字”。比如返回索引 1对应的坐标在vertices3d[3]和vertices3d[4]不是vertices3d[1]。渲染时如果用顶点索引去访问Float32Array步长必须跟dim保持一致。4.3 数据预处理三件事去重、平移缩放、洞环排序Earcut 的容错能力没你想的那么强输入质量直接决定输出质量。我在每次把数据交给剖分器之前都会强制走三步预处理第一把坐标值平移到接近原点的范围再按比例缩放第二相邻重复点直接合并第三确认洞环都在外环内部且洞环之间不互相包含。// 平移加缩放把坐标范围缩放到 [0, 100] 区间 function normalize(vertices) { let minX Infinity, minY Infinity, maxX -Infinity, maxY -Infinity; for (let i 0; i vertices.length; i 2) { minX Math.min(minX, vertices[i]); maxX Math.max(maxX, vertices[i]); minY Math.min(minY, vertices[i 1]); maxY Math.max(maxY, vertices[i 1]); } const scale Math.max(maxX - minX, maxY - minY) || 1; return vertices.map((v, idx) idx % 2 0 ? ((v - minX) / scale) * 100 : ((v - minY) / scale) * 100 ); }这段代码做了两件事减掉最小值保证坐标不从巨大数值开始除以边长最大值把整体范围压到 100 以内。参数说明scale取宽高较大者保证等比缩放不变形|| 1防止所有点重合时除零。预处理完再剖分结果用逆变换映射回原始坐标数值精度问题能被压到最低。5. 常见问题排查五种剖分翻车现场及对策5.1 自相交多边形剖分“成功”但面片全乱现象剖分函数正常返回了索引数组三角形数量也对但渲染出来的面片互相穿插有的区域重复覆盖有的区域直接镂空。原因Earcut 的前提是输入必须是简单多边形也就是边除了相邻边端点外不能互相交叉。自相交输入属于未定义行为算法不会报错只会给出看似合理实则错乱的结果。解决在调用剖分之前做一次自相交检测。最直观的办法是把多边形先画到离屏 canvas 或者用射线法逐边交叉检查发现相交就用多边形裁剪库做布尔运算拆分成多个简单多边形再分别剖分。不要指望 epsilon 能修这个问题。5.2 洞的起点索引算错三角形直接跨进洞里现象带洞多边形剖分后本应镂空的洞里被填上了三角形周围区域的三角形也出现不规则延伸。原因holes数组里的索引在拼数组时算错了一位。最常见的是把洞环的“第几个点”当成索引比如洞环第 4 个点写成了 4但实际外环有 6 个点洞的起点在总数组里的下标是 12。解决写一个小工具函数动态计算洞环起点。外环顶点数组拼接完成后记录下outer.length每个洞环拼进去之前先把当前位置记录到holes数组。这个顺序永远不要手算。// 动态计算 holes 起点避免手算出错 const vertices []; const holes []; outer.forEach(p vertices.push(p.x, p.y)); holes.push(vertices.length / 2); // 外环结束后第一个洞的起点 inner.forEach(p vertices.push(p.x, p.y)); holes.push(vertices.length / 2); // 第二个洞的起点注意到vertices.length / 2是浮点运算但length永远是偶数结果恒为整数可以安全使用。5.3 重复顶点与几乎重合点剖分卡顿甚至超时现象多边形顶点数不多但剖分耗时异常高极端情况下浏览器标签页直接卡死。原因数据源里有大量重复顶点或者距离极近的点耳朵裁剪判断“三角形是否包含其他点”时这些近重合点造成大量无效计算还有一种情况是环没闭合首尾点没对齐算法在最后一步永远剪不干净。解决预处理时按 epsilon 把邻近距离小于阈值的点合并并检查环的首尾点是否相等。如果首尾点差值小于阈值直接 drop 掉尾点。5.4 全共线或近零面积多边形返回空数组而不是报错现象所有顶点在同一条直线上或者自交后实际围成面积几乎为零的多边形Earcut 返回一个空数组没有异常。原因算法找不到任何有效的耳朵选择直接结束。这不是 bug而是这类多边形本来就没有可剖分的三角面。解决调用前用鞋带公式算面积面积绝对值小于某个阈值直接跳过不要把空数组当成 bug 传给上层的渲染逻辑。渲染层收到空索引数组时应直接隐藏该面片而不是报错。5.5 大坐标值导致细长三角形和渲染裂缝现象坐标从几百万起始剖分结果出现大量极细长三角形拼出来的面片在线框模式下看着还行填充渲染时相邻三角形之间出现暗线或裂缝。原因大坐标值在浮点计算中损失低位精度三角形共享边的顶点坐标经过两次独立计算后可能产生极小偏差光栅化时这条边被画了两次或者一次都没画上。解决先做 4.3 的平移缩放把坐标范围压到小尺度渲染时去掉多边形共享边的描边或者把顶点位置用gl_Position计算后再做一次偏移。简单粗暴的方式是把渲染背景色设置成多边形填充色同色掩盖掉那条亚像素缝。6. 验证剖分结果的三个技巧面积守恒、方向检测与测试固件剖分器输出结果后直接灌进渲染管线是很冒险的做法。我习惯先跑三个快速验证全部通过再往下走。第一个技巧是面积守恒检测把返回的三角形逐个算面积并累加跟原多边形面积比对。带洞的场景里外环面积减掉所有洞面积才是理论值三角形面积累加如果跟理论值对不上说明剖分结果有遗漏或重叠。// 按三角形索引累加面积返回绝对值 function trianglesArea(vertices, tris) { let sum 0; for (let i 0; i tris.length; i 3) { const ax vertices[tris[i] * 2], ay vertices[tris[i] * 2 1]; const bx vertices[tris[i 1] * 2], by vertices[tris[i 1] * 2 1]; const cx vertices[tris[i 2] * 2], cy vertices[tris[i 2] * 2 1]; sum ax * (by - cy) bx * (cy - ay) cx * (ay - by); } return Math.abs(sum) / 2; }这段代码直接用叉积公式累计有符号面积再取绝对值。注意这里假设所有三角形同向如果混了方向累加前要统一符号否则正负抵消后面积偏小。第二个技巧是方向检测渲染开背面剔除后面片消失多半是三角形绕序反了。把每个三角形的叉积符号取出来全部同号说明方向一致不一致就翻转三角形。Earcut 的输出通常跟输入环方向一致但如果你在预处理时旋转过环方向就可能丢。第三个技巧是攒一个测试固件把一组有代表性的多边形凸、凹、带洞、带多个洞连同验证函数写进自动化测试每次改数据前跑一遍。这个方法救过我很多次比任何代码审查都管用。我自己的习惯是任何新项目里引入 Earcut第一件事不是写具体业务而是先把测试固件搭起来后面所有重构都基于这套固件回归。几何算法翻车往往是悄悄发生的有自动化兜底心里才有底。希望帮到你。本文还有配套的精品资源点击获取