简介这是一份基于耳切法Ear Clipping的多边形三角化实现专门面向需要从无序顶点快速生成三角面片索引的开发者。资源内含改进后的耳朵切片算法利用z阶曲线散列进行优化并尝试扩展处理带孔洞、扭曲多边形、退化甚至自相交等复杂数据适合用于地理围栏区域划分、游戏地图碰撞体构建、几何算法学习与验证等场景。压缩包共33个文件以C/C源码为主体10个头文件与7个C文件构成核心算法4个HPP文件与2个CPP文件包含示例与集成入口另有4个CSV测试数据如顶点表、索引表方便验证效果并附带Visual Studio工程sln/vcxproj可直接编译运行整体仅4.29MB。目前已有454人学习/下载。该实现参考FIST的工业级三角化思路与David Eberly的耳切法论文内含libtess2对比模块读者可对照测试数据检查输出快速掌握优化技巧并嵌入自己的几何处理管线是一份精简而完整的实用参考。1. 多边形三角剖分的现成答案这套 Earcut 打包为什么值得用批处理分割、GIS 地块聚合、连续轮廓填充、WebGL 地图这块任何一次将多边形化作 GPU 能吃的网格传进去的顶点、传回来的索引、组装的三角形这套 Earcut 实现的三角剖分就是那个少写千行代码的出口。多边形装洞、凹形状翻转、顶点上百上千它一个函数调用出来一套可直接送进缓冲区的索引前端渲染不再靠 Canvas 硬填色后端生成网格拿到顶点和三角形也能直接驱动碰撞检测。做地块聚合、小工具可视化、图像外轮廓填充的都可以把三角化这个环节换成它。本包其实是一个打包好的 Earcut 算法实现核心就一个函数接受一组坐标返回非重叠三角形的顶点索引列表典型用途是把任意简单多边形允许凹、允许孔洞转成 GPU 或计算几何可以直接消费的三角形集合。对熟悉 two-dimensional 图形的人来说这就是最省事的现成模块不用自己实现 ear clipping也不用引入庞大几何库拆开包、调用 API、处理数组完事。2. 为什么会选 Earcut从耳切算法到带洞多边形的处理方式2.1 耳切法为什么高效三角剖分主流思路是 Delaunay但 Earcut 走的路线是耳切法。它不停遍历多边形顶点找到“耳朵”即一个顶点其左右邻居连成的对角线完全落在多边形内部剪掉循环往复最终只剩一个三角形。耳切最坏情况是 O(n²)但对大多数实际轮廓剪耳时受 Floyd 启发每一步都把多边形切成两个子多边形属于一种快速剖分策略。因为操作的是二维坐标每个耳部判定只需要看点积叉积几何判定简单几千个顶点也能保持在可接受范围。常见场景下的表现接近 O(n log n)。对大多数实现来说处理凹多边形也不难但纯耳切碰到孔洞容易出错。这套打包方案里孔洞会先与外部轮廓合并再执行统一剖分输出结果直接就是带洞网格的三角形列表不会额外生成桥接边也不用业务层担心打通洞的连接顺序。2.2 索引输出的意义展开坐标后从 API 返回的是一组 Int32Array或普通数组三角形索引。假设传入顶点坐标列表为 [a0a1, a1a2, a2a3, ...]其中的数字是原始坐标数组下标除以维度后的顶点序号。例如多边形四个坐标依次是 (1,1)、(5,1)、(5,5)、(1,5)那么输出索引 [0,1,2, 0,2,3] 表示两个三角形顶点 0-1-2 与 0-2-3。这样做的好处是几何结构只维护一份顶点缓存渲染时按索引顺序提交 gl.drawElements 即可。不需要额外传递每个三角形的独立坐标也节省顶点缓冲区的存储量。做物理碰撞时按索引逐三角形构建检测形状同样非常直接。2.3 数值类型与维度参数函数签名本质就一个参数维度 dim 决定坐标的排列方式。默认 dim2数组按 (x1,y1, x2,y2, ...) 排列。如果传入 dim3坐标排列为 (x,y,z, x,y,z, ...)此时 z 轴可以用于携带高度值或纹理映射参数。注意剖分过程完全忽略 z 轴z 值只是跟着顶点一起消耗索引并不会影响三角形划分想得到真正的 3D 曲面剖分它不会帮你做投影需要先把三维坐标投影到二维再剖分。3. 把这套打包展开最小可跑通的命令序列3.1 引入模块与数据准备以 JavaScript 写作最小示例准备好顶点坐标。使用 yarn/pnpm/npm 安装依赖后直接按 CommonJS 方式导入。const earcut require(./earcut); // 假设把打包文件放到项目根目录 // 定义三角形外环顺时针 const outerRing [ [0, 0], [10, 0], [10, 10], [0, 10] ]; // 定义三角形内孔逆时针 const hole [ [3, 3], [7, 3], [7, 7], [3, 7] ]; const coords []; outerRing.forEach(p coords.push(p[0], p[1])); const holeStart coords.length / 2; hole.forEach(p coords.push(p[0], p[1])); const triangles earcut(coords, [holeStart]); console.log(triangles);逻辑说明先拼接全部顶点为一个线性数组然后把孔洞起点记录为独立数组传给 holes 参数。earcut 内部会先对孔洞做剪耳融合然后统一三角化。输出索引的顺序为外环上的顶点下标天然在前孔洞顶点下标依次排在后面。参数说明holes 数组里每个值必须是孔洞的起始顶点在坐标数组中的下标除以 dim 后而不是坐标序号。多孔洞就按照这样的方式传一个数组进来。返回的是每个三角形三个顶点的索引排列方式是三的倍数。3.2 从索引恢复三角形坐标拿到索引后往往要组装成坐标集合。const positions [0, 0, 10, 0, 10, 10, 0, 10, 3, 3, 7, 3, 7, 7, 3, 7]; const triangleIndices earcut(positions, [4]); const trianglesCoords []; for (let i 0; i triangleIndices.length; i 3) { const a triangleIndices[i]; const b triangleIndices[i 1]; const c triangleIndices[i 2]; trianglesCoords.push([ [positions[a * 2], positions[a * 2 1]], [positions[b * 2], positions[b * 2 1]], [positions[c * 2], positions[c * 2 1]] ]); } console.log(trianglesCoords);参数说明由于默认 dim2顶点下标换算回坐标时需要乘以 2。整体逻辑是三位一组输出三角形。此时看 triangles 数组长度正好是 3 的倍数代表三角形个数是该长度除以 3。若开启了 dim3则换算时乘 3。4. 实际业务中的三个常用侧重点4.1 大数据量轮廓与性能取舍地图围栏、行政区轮廓、等高线这类典型输入顶点数量常在几千甚至上万。直接交给默认配置通常也能扛住。但有两个参数值得调一个是对退化三角形的剔除一个是排序策略。实际测试中坐标抖动会造成极窄的三角形带洞且顶点聚类严重的轮廓最容易出现这种问题。建议在业务侧先使用一个轻量的坐标approx简化将顶点距离过近的点合并再丢给剖分。输出三角形数量会明显减少整体网格更干净。4.2 带孔洞多边形顺序是玄学吗外环使用顺时针、孔洞使用逆时针是常见惯例但本包采用的是“内部自动识别”策略。如果输入数据方向统一处理还好但如果外环和孔洞方向相反注意力就要放在孔洞起点数组的构造上。核心要求是孔洞必须完全落在外部多边形内部且彼此不相交否则剖分会生成负面三角形。另外多个孔洞时如果孔洞之间有交叉重叠剖分结果可能会包含自交三角形这种输入属于非法多边形没有算法能完全兜底。直接建议在业务逻辑层做一次多边形合法性校验检测边是否相交、孔洞是否越界。4.3 从索引到渲染的一步到位配置拿到三角形索引直接生成 WebGL 渲染所需的数据。const renderVertices []; for (let i 0; i triangleIndices.length; i) { const index triangleIndices[i]; renderVertices.push(coords[index * 2], coords[index * 2 1]); } // 再写入 buffer这样做的问题在于三角形共享顶点时会重复存储浪费显存和绘制效率。常见做法是把 Earcut 的索引直接上传到 ELEMENT_ARRAY_BUFFER配合顶点属性缓冲使用 drawElements而不是先重构。如果渲染引擎强制要求每个三角形独立顶点则上面的展开方式可行但注意要同步展开 UV 等属性。5. Earcut 落地最容易翻车的四个坑5.1 孔洞数组起点传成序号而非下标现象传入 holes 后三角形乱七八糟甚至出现外部边与内部孔洞交错渲染完全不可控。原因api 的 holes 参数要求的是顶点下标即线性坐标数组中的位置除以维度而不是第几个顶点。手动拼接坐标时经常按“第几个坐标点”来传偏移一位导致内部桥接混乱。解决把孔洞起点记录为 coords.length / dim 的值而不是单独计数。例如已有 6 个坐标3 个顶点第二个孔洞起点写 3不写 2。多一个孔就记录一次当前坐标数组中的下标。5.2 坐标浮点抖动导致退化三角形现象剖分结果里有面积接近 0 的狭长三角形渲染时出现闪面、反光异常物理碰撞检测多出很多无效多边形。原因输入顶点带有大量小数点后多位如 1.0000001 与 1.0000000 两个点距离极近剖分时形成极小三角形除非运行强制合并。解决预处理时做一个坐标抖动修复常见的做法是保留 3 位小数或按一定阈值合并相邻顶点。下面给出一段简单的合并逻辑。function dedupeVertices(coords, tol 1e-4) { const unique []; const map new Map(); for (let i 0; i coords.length; i 2) { const x coords[i], y coords[i 1]; let bestIdx -1; for (let u 0; u unique.length; u) { if (Math.abs(unique[u][0] - x) tol Math.abs(unique[u][1] - y) tol) { bestIdx u; break; } } if (bestIdx -1) { bestIdx unique.length; unique.push([x, y]); } map.set(i / 2, bestIdx); } return { unique, map }; }5.3 自交多边形处理结果难以预期现象输入多边形边与边相交输出会出现重叠三角形视觉上出现面片遮挡边界变得渲染错误。原因耳切算法要求输入是简单多边形边不能交叉。自交区域没有明确定义“内部”earcut 无法保证正确。解决不要试图用 earcut 兜底先修复输入多边形。常见做法是先用几何库把自交多边形转为若干非自交多边形或者将形状按点位拆成多个子轮廓分别剖分。业务上给用户绘制工具的应实时捕获最后一次点位的连线若与已有边相交就在界面上给出提示源头规避。5.4 多边形方向混淆导致的孔洞删除现象三角形数量比预期少孔洞区域被填充了好像洞不存在一样。原因如果孔洞的顶点顺序与外环一致earcut 可能会将孔洞当作内部独立的轮廓处理而不是融合切除最终生成的三角形覆盖了孔洞区域。解决在调用前对每个孔洞执行一次方向判断。代码中判断面积符号并做翻转。function ringArea(coords, start, end, dim 2) { let area 0; for (let i start, j end - dim; i end; j i, i dim) { area coords[i] * coords[j 1] - coords[j] * coords[i 1]; } return area / 2; } // 若外环为正、孔洞在外部表现一致则需要将孔洞方向取反很多时间花在“为什么孔洞没打掉”上往往是方向没统一。本包虽然对方向有一定容忍但工程上仍建议统一外环顺时针、内环逆时针省去后续排查。6. 进阶用法从三角网格转成可用的邻接结构三角剖分输出具备天然邻接关系但索引列表本身不直接表达每个三角形的邻居是谁。在实现物理碰撞、网格简化、跳跃 flooding 算法处理时需要把索引转为邻接结构。常见做法是建立半边结构。function buildAdjacency(triangles, vertexCount) { const adj new Array(vertexCount).fill(null); // 记录每条半边起点终点 const halfEdge {}; for (let t 0; t triangles.length; t 3) { const a triangles[t], b triangles[t 1], c triangles[t 2]; const edges [ [a, b], [b, c], [c, a] ]; edges.forEach(([from, to], k) { const key from * vertexCount to; const oppKey to * vertexCount from; if (halfEdge[oppKey] ! undefined) { // 配对成功写邻接表 const triOpp halfEdge[oppKey]; // 记录三角形 tri 与三角形 triOpp 相邻 } else { halfEdge[key] t / 3; } }); } return adj; }代码逻辑说明利用顶点索引构建 key遍历当前三角形的三条边查找是否存在反向边如果存在说明邻接三角形已经出现两端共享这条边。使用该结构后续计算法线、平滑、轮廓提取都能直接找到邻居三角形。参数说明vertexCount 必须等于剖分输入的原始顶点去重后的数量如果直接使用 earcut 索引则 vertexCount 为坐标数组长度除以维度。如果用去重后的顶点更新索引则使用新的计数。我自己的切身体会是任何三角剖分方案都要在输入侧多花时间做合法性检查合法输入与非法输入的结果差距极大。不要在数据异常时怀疑剖分算法有问题先让数据解释自己。希望这组笔记能帮你减少一些试错时间。本文还有配套的精品资源点击获取