Earcut三角化实战：从无序顶点到可渲染网格的避坑指南

简介本资源为基于耳切法EarCut实现多边形三角化的完整工程包面向从事图形学、GIS 地理数据处理及游戏引擎开发的工程师与学习者。它采用修改后的耳朵切片算法借助 z 阶曲线散列进行优化并扩展支持孔洞、扭曲多边形、退化与自相交等复杂情形可在不保证三角剖分绝对正确的前提下尽量为地理形状等实用数据输出可用的三角网格同时提供无序顶点获取顶点索引的能力。包内共 33 个文件以 h 头文件、c 源文件、hpp 与 cpp 实现为主另含 csv 测试数据、txt 说明及 sln、vcxproj 等 Visual Studio 工程文件整体约 4.29MB目录结构清晰便于直接编译调试。资源参考了 FIST 与 David Eberly 的三角剖分思路并附带对比数据与顶点、索引等样例文件可帮助读者理解算法实现细节、验证剖分结果并快速集成到自有项目中。目前已有 454 人学习下载。1. 从一堆无序顶点到可渲染网格Earcut 三角化到底解决了什么问题如果你手里有一组多边形顶点顺序是乱的甚至带孔洞想把它喂给 WebGL、Three.js、Canvas 2D 或者任何需要三角面片的渲染管线第一道坎往往不是着色器而是「怎么把这些点连成不重叠的三角形」。Earcut-Triangulation.zip 就是冲着这件事来的——它把耳切法Ear Clipping封装成可直接调用的三角化工具输入顶点坐标输出顶点索引三元组让你跳过手写几何算法的阶段。它适合三类人做地图矢量面渲染的前端、处理 CAD 导出轮廓的图形工程师、以及需要把 SVG 路径转成三角网格的 3D 开发者。核心价值在于「无序顶点 → 有序索引」这一步索引拿到手剩下的交给 GPU 就行。耳切法本身不是新算法但把它做成开箱即用的压缩包省掉的是调试退化多边形和孔洞边界的那些夜晚。2. 耳切法的判定逻辑为什么它敢吃凹多边形和孔洞2.1 耳切法的几何直觉与算法流程耳切法的名字来自一个形象的动作在多边形上找「耳朵」切掉再找下一只直到只剩一个三角形。所谓耳朵是连续三个顶点 A、B、C 构成的三角形满足两个条件——三角形 ABC 完全落在多边形内部且多边形其余顶点都不在 ABC 内部。切掉耳朵后B 点从顶点序列中移除A 和 C 变成新的相邻点继续下一轮。这个流程对凸多边形几乎无脑对凹多边形才是真正的考验。凹顶点处容易形成「假耳朵」如果判定不严切出来的三角形会跑到多边形外面渲染时就是一块飞出去的碎片。Earcut 的实现里判定用的是有向面积加叉积符号配合一个包围盒加速的「点是否在三角形内」检测。常见做法是先把顶点按逆时针排序保证有向面积为正这样叉积符号才有统一含义。// 耳切法核心判定伪代码基于有向面积 function isEar(prev, curr, next, vertices) { // 1. 计算三角形有向面积面积 0 说明是凹顶点或退化不是耳朵 const area cross(prev, curr, next); if (area 0) return false; // 2. 遍历其余顶点检查是否有顶点落在三角形内部 for (let i 0; i vertices.length; i) { const p vertices[i]; if (p prev || p curr || p next) continue; if (pointInTriangle(p, prev, curr, next)) return false; } return true; }上面这段是判定逻辑的骨架。cross计算的是二维叉积结果就是三角形有向面积的两倍pointInTriangle用重心坐标或者同向叉积法都行Earcut 内部为了速度会先做包围盒剔除。参数上顶点数组必须是扁平化的[x0, y0, x1, y1, ...]这是 Earcut 的标准输入格式不是对象数组。如果你传的是{x, y}对象得先 map 成扁平数组否则索引会错位。2.2 孔洞处理桥接边与顶点索引的对应关系带孔洞的多边形是耳切法最容易翻车的地方。Earcut 的做法不是把孔洞单独三角化再拼而是用「桥接」把孔洞和外轮廓连成一个简单多边形。具体说找到孔洞上最右的顶点向外轮廓引一条不与任何边相交的桥接边把孔洞顶点插入外轮廓序列形成一个带「切口」的单一多边形然后再跑耳切。这一步对顶点索引的影响很直接桥接边会让某些顶点在序列里出现两次但输出索引时只保留一次实际坐标。如果你自己解析输出会发现索引数组里同一个顶点被多个三角形共享这是正常的GPU 顶点复用本来就靠索引。坑在于桥接边的选择——如果孔洞和外轮廓距离太近桥接边可能穿过其他边Earcut 会尝试多个候选点但极端情况下仍可能失败返回空数组。// 使用 Earcut 处理带孔洞多边形 const earcut require(earcut); // 外轮廓逆时针扁平数组 const outer [0, 0, 100, 0, 100, 100, 0, 100]; // 孔洞顺时针扁平数组 const hole [30, 30, 70, 30, 70, 70, 30, 70]; // 第二个参数是孔洞起始索引数组这里孔洞从索引 8 开始 const indices earcut(outer.concat(hole), [8], 2); console.log(indices); // [0, 1, 2, ...] 每三个一组指向顶点数组下标earcut(vertices, holes, dimensions)三个参数vertices是扁平坐标holes是孔洞起始索引的数组dimensions是维度二维传 2。孔洞顶点必须和外轮廓顶点拼在同一个数组里holes只记录孔洞第一个顶点在数组中的下标。输出indices是三角形索引长度一定是 3 的倍数。如果返回空数组说明三角化失败常见原因是顶点顺序反了或者存在自相交。3. 从压缩包到可运行 Demo环境搭建与最小复现路径3.1 解压后的目录结构与依赖确认拿到 Earcut-Triangulation.zip 后先别急着跑。解压出来通常包含源码目录、测试用例和构建脚本。我一般先看package.json或者README里的入口文件确认是 CommonJS 还是 ES Module。Earcut 本身零依赖但压缩包里可能带了可视化 Demo那就会依赖 Canvas 或者 Three.js。# 解压后进入目录查看结构 unzip Earcut-Triangulation.zip -d earcut-demo cd earcut-demo ls -la # 如果 package.json 存在安装依赖 npm install # 运行测试用例确认算法本身没问题 npm testnpm test这一步很关键。Earcut 的测试用例里包含大量退化多边形、自相交、重复顶点等边界情况跑一遍能确认你拿到的版本没有在打包时被改坏。如果测试挂了先看 Node 版本Earcut 对 Node 版本不敏感但测试框架可能要求 14 以上。依赖装不上时检查 npm 源不要用公司内网源容易缺包。3.2 最小三角化 Demo输入顶点、输出索引、渲染验证光看索引数组没有体感得把它画出来。下面这个 Demo 用 Canvas 2D 把三角化结果画成半透明三角形能直观看到有没有飞出去的碎片。!DOCTYPE html html body canvas idcv width400 height400/canvas script srcearcut.js/script script const canvas document.getElementById(cv); const ctx canvas.getContext(2d); // 一个凹多边形顶点逆时针 const vertices [50, 50, 200, 30, 250, 150, 150, 120, 100, 250, 30, 180]; const indices earcut(vertices, [], 2); // 每个三角形用随机颜色填充 for (let i 0; i indices.length; i 3) { const a indices[i] * 2; const b indices[i 1] * 2; const c indices[i 2] * 2; ctx.beginPath(); ctx.moveTo(vertices[a], vertices[a 1]); ctx.lineTo(vertices[b], vertices[b 1]); ctx.lineTo(vertices[c], vertices[c 1]); ctx.closePath(); ctx.fillStyle hsla(${i * 10 % 360}, 70%, 60%, 0.6); ctx.fill(); ctx.strokeStyle #333; ctx.stroke(); } /script /body /html这段代码里indices[i] * 2是因为顶点是扁平数组索引指向的是顶点序号乘以 2 才是坐标数组里的 x 下标。渲染出来如果看到三角形覆盖了整个多边形且没有溢出说明三角化正确。如果看到某块区域空白或者有三角形跑到轮廓外大概率是顶点顺序问题——Earcut 要求外轮廓逆时针、孔洞顺时针顺序反了会得到错误结果甚至空数组。提示用 Canvas 验证时把ctx.stroke()打开能清楚看到每个三角形的边方便定位溢出碎片。4. 避坑与排查顶点顺序、退化三角形和索引越界的血泪经验4.1 顶点顺序反了会怎样现象三角化返回空数组或者返回的索引画出来是一团乱麻。原因Earcut 内部依赖有向面积判断耳朵外轮廓必须是逆时针孔洞必须是顺时针。如果你从某些 CAD 或 GIS 工具导出的顶点是顺时针直接喂进去就会翻车。解决用鞋带公式算一下有向面积面积为负就反转顶点数组。function ensureCounterClockwise(vertices) { let area 0; for (let i 0; i vertices.length; i 2) { const x1 vertices[i], y1 vertices[i 1]; const x2 vertices[(i 2) % vertices.length], y2 vertices[(i 3) % vertices.length]; area x1 * y2 - x2 * y1; } if (area 0) { // 反转顶点顺序保持扁平结构 const reversed []; for (let i vertices.length - 2; i 0; i - 2) { reversed.push(vertices[i], vertices[i 1]); } return reversed; } return vertices; }这个函数对孔洞同样适用但孔洞要的是顺时针所以判断条件反过来。实际项目里我习惯在三角化之前统一做一次方向校正省得后面逐个排查。4.2 重复顶点和共线顶点导致的退化三角形现象渲染时出现面积为零的三角形或者某些边看起来「缺了一块」。原因原始数据里存在重复顶点或者三个连续顶点共线。耳切法遇到共线顶点时有向面积为零判定为凹顶点可能导致该切的地方切不掉最后剩下一个退化多边形。解决预处理阶段去重并移除共线中间点。function removeDuplicates(vertices, eps 1e-6) { const result []; for (let i 0; i vertices.length; i 2) { const x vertices[i], y vertices[i 1]; let duplicate false; for (let j 0; j result.length; j 2) { if (Math.abs(result[j] - x) eps Math.abs(result[j 1] - y) eps) { duplicate true; break; } } if (!duplicate) result.push(x, y); } return result; }eps是容差浮点坐标比较不能直接用。去重之后如果顶点数少于 3直接返回空数组没必要往下跑。4.3 索引越界维度参数传错现象控制台报undefined或者画出来的三角形位置完全不对。原因earcut(vertices, holes, dimensions)的第三个参数传成了 3但顶点数组是二维的。Earcut 支持三维顶点但会忽略 z 轴做二维三角化如果你传 3 而数组长度不是 3 的倍数索引计算就会错位。解决二维数据固定传 2三维数据传 3 且确保数组长度是 3 的倍数。4.4 孔洞桥接失败距离过近或自相交现象带孔洞的多边形三角化返回空数组或者孔洞被填平。原因孔洞离外轮廓太近桥接边找不到合法路径或者孔洞本身自相交。解决先检查孔洞是否完全在外轮廓内部用射线法或者包围盒粗判如果距离过近考虑把孔洞稍微缩小一点或者改用其他三角化库。Earcut 对自相交多边形没有兜底输入前必须保证几何合法。4.5 大数据量下的性能骤降现象顶点数超过几千后三角化耗时从毫秒级跳到秒级。原因耳切法最坏情况是 O(n²)每切一个耳朵都要遍历剩余顶点做点在三角形内检测。解决Earcut 内部有包围盒和 z-order 曲线加速但如果你自己实现务必加空间索引。实际项目里超过一万个顶点的多边形建议先做简化或者分块三角化再合并。5. 进阶技巧把索引喂给 Three.js 并验证法线方向拿到索引只是第一步真正落地到 3D 场景还得把顶点和索引组装成 BufferGeometry。下面这段代码把 Earcut 输出直接转成 Three.js 可渲染的网格并顺手验证法线方向。import * as THREE from three; import earcut from earcut; function polygonToMesh(vertices2D) { // 三角化得到索引 const indices earcut(vertices2D, [], 2); // 构建三维顶点z 统一为 0 const positions []; for (let i 0; i vertices2D.length; i 2) { positions.push(vertices2D[i], vertices2D[i 1], 0); } const geometry new THREE.BufferGeometry(); geometry.setAttribute(position, new THREE.Float32BufferAttribute(positions, 3)); geometry.setIndex(indices); // 计算法线如果法线朝下说明顶点顺序反了 geometry.computeVertexNormals(); const material new THREE.MeshBasicMaterial({ color: 0x3399ff, side: THREE.DoubleSide, // 调试时双面渲染方便看背面 wireframe: false }); return new THREE.Mesh(geometry, material); }setIndex接收的就是 Earcut 输出的索引数组Three.js 会自动按每三个索引组装三角形。computeVertexNormals会根据顶点顺序计算法线如果法线指向 -z说明三角形绕序是顺时针渲染时可能被背面剔除。调试阶段用THREE.DoubleSide能快速判断是不是绕序问题确认无误后再改回FrontSide。验证方法在场景里加一个AxesHelper把网格放上去旋转相机看背面。如果背面是黑的或者直接消失就是绕序反了。解决办法是在三角化之前确保外轮廓逆时针或者拿到索引后手动翻转每三个索引的顺序。// 翻转索引绕序 function flipWinding(indices) { const flipped []; for (let i 0; i indices.length; i 3) { flipped.push(indices[i], indices[i 2], indices[i 1]); } return flipped; }这个函数在调试阶段很管用但别长期用——正确的做法还是从源头保证顶点顺序。从那以后我每次拿到新数据都强制先跑一遍方向校正和去重再进三角化省得在渲染阶段来回翻烧饼。希望帮到你。本文还有配套的精品资源点击获取