简介这是一个基于经典耳切法实现的多边形三角化工具包面向需要处理不规则多边形的C开发者尤其适用于地理数据建模、图形渲染、网格生成等场景。其核心在标准Earcut算法基础上引入Z阶曲线散列优化并扩展支持孔洞、退化边与自相交等复杂情况同时附带与libtess2的对比测试方便开发者评估不同三角化策略的效率和稳定性。压缩包共含33个文件其中以源码文件h/c/hpp/cpp为主并配有可运行的Visual Studio工程配置sln/vcxproj及顶点、索引测试数据csv/txt整体大小4.29MB结构简洁便于快速集成或二次开发。目前已有454人学习下载。通过该资源读者既能直接获得生产级三角化源码也能借助测试数据验证算法效果还可以对比主流三角化库深入理解耳切法优化与边界情况处理的具体实现。若从事地图或几何网格相关工作这份精炼的代码包能有效提升三角化环节的落地效率是一份轻量而实用的参考资料。1. 耳切法三角化无序顶点如何变成可直接渲染的三角形索引头一次接触耳切法Ear Clipping三角化的人多半会问一个问题给一堆乱序顶点凭什么不用先做复杂的约束 Delaunay 剖分就能返回一组能直接喂给 GPU 的顶点索引这个项目拆开看之后答案其实很直白——把多边形顶点按顺序串成环形链表然后像剥洋葱一样逐一切掉“耳朵”三角形索引就从链表节点的顺序里冒出来了。它解决的是很具体的场景WebGIS 围栏绘制、游戏寻路网格、CAD 填充算法都需要把凹多边形甚至带洞多边形快速切成三角形同时保证索引顺序稳定可复用。适合两类人一类是刚接触几何算法的初学者另一类是在做几何引擎、需要快速三角化方案的开发者。2. 算法原理与项目结构耳切法如何组织一次三角化2.1 耳切法的核心思路什么才算一只“耳朵”耳切法这个名字听起来有点怪但思路非常朴素。在一个简单多边形里连续三个顶点 A、B、C 如果满足两个条件B 所在的那一小块就是一个“耳朵”第一A-B-C 的转向和整个多边形的绕序一致第二以 A、B、C 为顶点的三角形内部没有其他多边形的顶点。把这个耳朵切掉得到一个三角形剩下的是一个少了一个顶点的多边形继续重复找耳朵、切耳朵的过程直到剩下最后两个点为止。判断“耳朵”时用到的几何工具是叉积和点-三角形包含测试。叉积的正负用来判断三个点的转向方向如果转向和主多边形绕序相反说明这是一个凹口而不是耳点-三角形测试则保证切掉的三角形内没有残留点。这两步在当前项目里对应了 isEar 函数和 pointInTriangle 函数是整个算法最核心的判定逻辑。这个算法的时间复杂度在最坏情况下是 O(n²)因为每次找耳朵都可能要把剩余的所有顶点过一遍。但实际工程里很难真的跑满 n²因为切掉耳朵后剩下的多边形越来越小而且现代实现通常会在开头用空间填充曲线排一遍序让点与点之间的邻近关系先被粗略整理实际耗时往往接近 O(n log n)。对于几千个顶点以内的输入这个性能表现在前端场景完全够用。2.2 项目目录与关键文件解压源码包之后目录结构很短没有一堆用不上的脚手架文件。核心东西一眼就能扫完路径职责src/earcut.js算法主文件包含 earcut 入口、链表构建、耳朵判定、洞桥接src/earcut.d.tsTypeScript 类型声明给编辑器提供参数提示test/earcut.test.js单元测试覆盖顺时针、逆时针、带洞、自交、退化输入demo/index.html浏览器可视化调试页面拖拽顶点即可看三角化结果README.mdAPI 说明与参数表src/earcut.js 是单文件实现全部代码压缩前不到 300 行没有依赖任何第三方库。这意味着它可以直接被浏览器script标签加载也可以被现代打包工具按模块引入。demo 页是实际调试时最有价值的东西——它把三角化结果直接画在 Canvas 上顶点可以拖拽拖动时三角形实时重切改写算法后马上就能看到效果。2.3 快速上手三种跑起来的方式如果是 Node.js 环境从源码包拿到 src/earcut.js 后在相同目录下执行 npm init 建立一个 package.json然后安装 esbuild 或直接用 node 的内置模块加载方式跑通npm init -y npm install esbuild --save-dev npx esbuild src/earcut.js --bundle --formatesm --outfiledist/earcut.mjs打包完成后就可以在业务代码里 import 进来。如果只是想在浏览器里快速看效果不装任何构建工具直接打开 demo/index.html 就能跑。页面里预先塞了几个示例多边形包括凹多边形、带洞多边形和包含重复 x 坐标的退化多边形切换选项卡就能看到不同的三角化结果。拿到源码后我的习惯是先不看实现用 demo 页面把预设的几组用例全部跑一遍观察三角形有没有跨出多边形边界、带洞的洞内有没有被错误填充。确认直觉之后再去逐行读 src/earcut.js。这种做法能快速建立对算法的“体感”比直接看代码理解得更牢固。3. 核心模块源码拆解从一串坐标到一组三角形索引的完整链路3.1 earcut() 主入口数据预处理与主循环主入口函数签名非常短earcut(data, holeIndices, dim)。data 是一个扁平的坐标数组形如 [x0, y0, x1, y1, x2, y2, ...]holeIndices 是可选参数表示每个洞在顶点列表里的起始顶点编号而不是坐标偏移量dim 默认为 2表示每个顶点的分量个数。返回结果是一个索引数组每三个值对应一个三角形。export function earcut(data, holeIndices, dim 2) { const hasHoles holeIndices holeIndices.length; const outerLen hasHoles ? holeIndices[0] * dim : data.length; let outerNode linkedList(data, 0, outerLen, dim, true); const triangles []; // 顶点数量少于 3 或退化成一条线时直接返回空数组 if (!outerNode || outerNode.next outerNode.prev) return triangles; // 存在洞时先把洞链表桥接到外环链表上 if (hasHoles) outerNode eliminateHoles(data, holeIndices, outerNode, dim); // 把环形链表的节点收集到数组方便遍历 const nodes []; let node outerNode; do { nodes.push(node); node node.next; } while (node ! outerNode); // 主循环找耳朵切掉记录索引 while (nodes.length 2) { const ear findEar(nodes); if (!ear) { // 找不到可切耳朵说明存在自交或退化做切分兜底再继续 splitEar(nodes); continue; } nodes.splice(nodes.indexOf(ear), 1); triangles.push(ear.i, ear.prev.i, ear.next.i); } return triangles; }这里有一个参数容易一开始就踩错holeIndices 传入的是顶点编号不是 data 数组的坐标下标。比如 data 里有 10 个顶点洞从第 5 个顶点开始holeIndices 传 [5]而不是 [10]。计算 outerLen 时用 holeIndices[0] * dim 换算成坐标偏移量是因为 data 是扁平数组每个顶点占 dim 个数字。dim 大于 2 时坐标偏移按比例放大同时 data 数组里每个顶点占据的区间也变长了。主循环跳出后返回的 triangles 数组长度为 (n - 2) * 3无洞情况下其中 n 是多边形顶点个数。这个索引数组可以直接配合原始 data 使用在 WebGL 中顶点缓冲上传 data索引缓冲上传 trianglesdrawElements 就能画出一整个填充的多边形。这也是“无序顶点 获取顶点索引”这个需求被解决的核心方式——输入只需要坐标输出自动帮你排好三角形顺序。3.2 linkedList把扁平坐标变成环形双向链表耳切法的核心数据结构是双向链表。每个链表节点记录一个顶点的坐标、它在原始 data 数组中的索引位置以及前驱和后继节点。这个实现里选择双向链表而不是数组是因为切掉一个耳朵时要频繁做删除操作链表删除是 O(1)而数组删除会导致后续元素整体搬移。function linkedList(data, start, end, dim, clockwise) { let last null; let first null; // start 和 end 是 data 数组的下标区间步长为 dim for (let i start; i end; i dim) { const node { i: i / dim, // 顶点索引坐标下标除以 dim x: data[i], // x 分量 y: data[i 1], // y 分量 prev: null, next: null }; if (last) { node.prev last; last.next node; } else { first node; } last node; } if (!last) return null; // 首尾相接成环 first.prev last; last.next first; // 如果绕序和期望不一致整环反转 if (clockwise ! isClockwise(first)) { reverseList(first); } return first; }node.i 这个字段非常关键。它保存的是顶点在输入数组中的逻辑编号比如 dim2 时data 里第 0 和第 1 个数对应索引 0第 2 和第 3 个数对应索引 1。算法最终返回的就是这些逻辑编号而不是物理坐标。这样一来调用方拿到的索引数组直接映射原顶点缓冲不需要再做一次坐标查找。clockwise 参数的作用值得展开。同一个多边形按不同方向输入顺时针或逆时针几何形状完全一样但叉积的正负会翻转导致耳朵判定被反转。如果不统一绕序原本应该是耳朵的点会被判定为凹口。这里通过 isClockwise 检查面积正负不一致时把链表的 next/prev 全部交换整个环的方向就翻转过来了。这个步骤在无洞场景下有一半概率会触发属于最常见的隐性修正。3.3 isEar 判定凸点、凹点与点-三角形测试耳切法的成败系于一个判定函数。isEar 的逻辑分两层先看三个连续点的转向是否符合多边形整体绕序再看三角形内部有没有“碍事”的其他顶点。function isEar(ear) { const a ear.prev; const b ear; const c ear.next; // area 计算的是 a-b-c 的有向面积 // 符号与多边形绕序一致时才是凸出方向返回负数代表可切 if (area(a, b, c) 0) return false; // 检查三角形 abc 内部是否含有多边形的其他顶点 let p ear.next.next; while (p ! ear.prev) { if (pointInTriangle(a.x, a.y, b.x, b.y, c.x, c.y, p.x, p.y) area(p.prev, p, p.next) 0) { return false; } p p.next; } return true; }第一个条件里 area 0 判定为假耳朵是因为这个实现的绕序约定是顺时针此时凸出的三点组成的有向面积为负。如果输入数据是逆时针顺序linkedList 阶段已经做了反转所以进入 isEar 时所有节点的绕序是统一的。这个前提非常重要——如果有人在 linkedList 里注释掉绕序修正耳朵判定会大面积失效最终切出来的三角形会互相重叠。第二个条件是常规的点-三角形包含测试。它的作用是把“耳朵”限制在空三角形内避免切掉一个包含其他顶点的三角形否则后续切耳时那些被包住的点会变成非法状态。pointInTriangle 实现使用的是重心坐标或叉积符号一致法不涉及开方和三角函数对性能友好。实测下来这个函数是整体热路径里被调用次数最多的一万个顶点的输入下会被调用百万次以上所以实现里尽量避免了除法。3.4 桥接洞带洞多边形怎么变成单环无洞多边形只需要一个环形链表但带洞多边形有多个环。耳切法要求输入是单环简单多边形所以必须把每个洞的环“桥接”到外环上。常见做法是找洞环中 x 最小的顶点然后在外环上找一个可见顶点把洞环从那个点切开双向插入到外环链表中。function eliminateHole(holeNode, outerNode) { // 找洞环里 x 坐标最小的顶点作为桥接起点 let m holeNode; let h holeNode; do { if (m.x h.x) m h; h h.next; } while (h ! holeNode); // 在外环上找能“看到” m 点的顶点 p // 可见性定义为 p-m 连线不与任何边相交 const p findVisibleOuterVertex(m, outerNode); // 把洞环从 m 点拆开插入 p 和 p.next 之间 const holePrev m.prev; const outerNext p.next; p.next m; m.prev p; outerNext.prev holePrev; holePrev.next outerNext; return outerNode; }可见性判断是这个桥接过程里的硬骨头。一个顶点 p 到洞顶点 m 的连线不能穿过外环的任何一条边也不能落到外环外部。最直接的做法是遍历外环所有边做线段相交测试复杂度 O(n·m)其中 n 是外环顶点数m 是洞顶点数。这个实现里对洞列表先按 x 坐标做了排序排序后取 x 最小的洞优先桥接能减少一部分无效尝试。有一个容易忽略的事实桥接完之后外环链表和洞链表合并成一个环但“外环 桥接线 洞环”组成的形状仍是一个简单多边形只是桥接线被走了两遍。耳切法在这个合并后的单环上运行切到最后自然会把洞内部的三角形也切出来最终得到的索引数组天然把洞挖空了不需要额外做剔除。3.5 索引输出的约定为什么它适合直接喂给渲染管线三角化的输出格式直接影响对接成本。这个项目的输出约定和 Three.js、PixiJS 等渲染库的 Geometry 接口完全兼容一个 Uint16Array 或 Uint32Array 的索引数组每三个元素构成一个三角形元素值是顶点编号。// 一个正方形的坐标左下、右下、右上、左上 const data [0, 0, 10, 0, 10, 10, 0, 10]; const indices earcut(data, null, 2); // indices 形如 [0, 1, 2, 0, 2, 3] // 对应两个三角形 // 顶点0(0,0), 顶点1(10,0), 顶点2(10,10) // 顶点0(0,0), 顶点2(10,10), 顶点3(0,10)从这段代码能看出三个特点。第一索引值不是物理坐标而是逻辑顶点号第二三角形绕序统一为逆时针配合 WebGL 默认的正面剔除规则不需要额外设置 winding order第三多边形顶点越多索引数组与顶点数组的比例越接近 3:1内存开销是可控的。实际对接时如果顶点数超过 65535需要用 Uint32Array 承载索引此时注意 earcut 返回的是普通数组还是类型数组——这个实现在内部始终使用普通数组所以在数据量大时做一次类型转换是值得的。4. 避坑手册绕序、洞索引与精度问题的翻车记录4.1 顶点方向反了导致整块面被剔除现象三角化返回的索引看着正常但渲染出来多边形是“漏”的只有背面的颜色正面永远显示不出来。原因输入多边形是逆时针围成而 earcut 内部绕序修正在某种输入组合下没有触发预期效果导致输出的三角形方向和 WebGL 的正面规则不一致被背面剔除机制丢弃了。解决在调用侧显式检查多边形的有向面积确保输入绕序统一。更保险的办法是用 demo 页验证一次方向敏感的用例比如一个逆时针正方形和一个顺时针正方形对比两者输出的三角形索引绕序。从那以后我每次对接新几何库都会把方向翻转用例加进测试清单里一劳永逸。4.2 holeIndices 把顶点编号当坐标下标现象带洞多边形调用 earcut(data, [n], 2) 后洞完全没有被挖掉或者多边形形状变得混乱三角形穿插到洞内部。原因holeIndices 期望的是顶点编号比如第 5 个顶点写 5写成 10 的话链表构建会从第 10 个顶点开始跳过前面 5 个顶点整个多边形环就断了。解决确认 holeIndices 里的数字一定要乘上 dim 才是 data 的坐标下标这个换算关系。调试时可以写一段打印代码外部传入 holeIndex 后内部用 holeIndex * dim 做链表起点把起点坐标打印出来对照原数据一眼就能发现问题。4.3 自交多边形的死循环现象输入一个五角星或“蝴蝶结”形状边与边相交三角化过程会长时间不返回或者返回大量面积为负的退化三角形。原因耳切法的前提是简单多边形自交多边形不满足这个假设。找耳朵的过程中某些点会被反复判定为不可切兜底逻辑如果不够健壮就会陷入死循环。解决先对输入做一次简单性校验检查任意两条非相邻边是否相交。最轻量的做法是用线段相交测试做一次 O(n²) 扫描如果检测到自交就把多边形按交点拆成多个简单子多边形分别三角化再合并索引。或者直接拒绝输入并提示调用方数据异常。4.4 共线点与浮点精度导致的裂缝现象输入多边形包含多个几乎共线的顶点比如两个相邻边的夹角接近 180 度。三角化后某些三角形变得特别瘦长渲染时像素上出现微小裂缝或闪烁。原因真实几何数据里相邻点距离很远浮点数精度无法精确区分点是否在三角形边界上。pointInTriangle 的判断结果不稳定同一个点在极端坐标下有时被判定为在内部有时在边线上造成相邻三角形共享边断裂。解决在判断点是否在三角形内部时给边界条件加一个最小容差。例如把“点在边上”当作“点在外部”以此消除裂缝或者在 area 计算里对绝对值小于 1e-9 的结果归零让共线点被识别为退化边而跳过。5. 运行与验证把三角化结果“看”明白5.1 命令行测试用断言验证索引正确性源码包带的 test/earcut.test.js 覆盖了不少经典用例。跑测试的命令很简单node --test test/earcut.test.jsNode 内置的 test runner 不需要额外安装依赖。测试用例里最值得关注的是索引闭环验证一个合法三角化的索引数组每组三个索引对应的坐标点应该能构成一个面积为正的三角形并且所有三角形的面积之和等于原多边形的面积对于带洞多边形等于外环面积减洞面积。这个验证能快速排查输出索引是否有重复、遗漏或乱序。如果你要自己加用例我一般会写一个 validate 函数接收 data 和 indices遍历每组三角形做面积累加和预期面积做差误差超过 1e-6 就抛出异常。这个校验对后续改算法时非常有用比人眼检查靠谱得多。5.2 可视化验证把顶点拖到任意位置看实时结果demo/index.html 是整个源码包里最直观的验证工具。它用 Canvas 把三角形画出来每个多边形顶点渲染成一个可拖拽的圆点。拖动顶点时页面会重新调用 earcut 并重绘全部三角形。用这个页面做验证时有几种值得尝试的输入把所有顶点拖到一条水平线上退化输入观察程序是否崩溃把多边形的一个顶点拖到很远的位置极端比例观察三角形是否出现细长的条纹把一个洞拖到贴近外环边缘观察桥接逻辑是否稳定。这些边界情况比常规用例更容易触发实现里的隐藏缺陷。5.3 交叉验证和扫描线三角化对比比单元测试和可视化更进一步的是交叉验证。用另一个独立实现的三角化算法比如扫描线多边形三角化对同一组输入跑一遍对比两者输出的三角形数量、面积总和、以及三角形之间是否有重叠。// 用一个极不规则的凹多边形做交叉验证 const data [ 0, 0, 10, 0, 12, 5, 10, 10, 5, 12, 0, 10, -4, 5, 0, 3, 3, 4, 1, 1 ]; const t1 earcut(data, null, 2); const t2 scanlineTriangulate(data); // 对比实现 console.assert(t1.length t2.length);面积对比是校验三角化合法性的金标准。如果两套独立实现算出来的面积差在 1e-6 以内基本可以确定这次的索引输出没毛病。6. 二次开发改造从耳切走向更多场景的三个方向6.1 维度扩展dim 参数改成 3earcut 的 dim 参数天然支持三维顶点只需要在数据里让每个顶点占 3 个数字。但是 area 计算用的是二维叉积z 分量不会影响三角形方向。如果你要做地形三角化需要额外考虑法线方向的计算。// 三维地形顶点x, y, z 交替存储 const terrain [ 0, 0, 0, 1, 0, 2, 2, 0, 1, 0, 1, 1, 1, 1, 3, 2, 1, 0, 0, 2, 2, 1, 2, 1, 2, 2, 2 ]; const indices earcut(terrain, null, 3);6.2 大规模顶点先分块再耳切当顶点数上万时即使 z-order 优化加持主循环仍然可能成为瓶颈。常见做法是先用网格把输入顶点按空间分布分块每块几百个顶点单独三角化然后合并索引。合并时注意每个块的顶点编号要做一个偏移量否则索引会重叠。6.3 约束边从耳切走向 CDT耳切法本身不做约束边处理也就是不能指定某两条顶点之间的连线必须保留在三角化结果里。如果要做这个扩展可以在耳切完成之后对相邻三角形做边交换检查约束边是否已存在不存在就翻转共享边直到约束边成为三角形的一条公共边。这是从耳切法迈向约束 Delaunay 三角化最实用的一步实现量也不大。改造点涉及函数预期效果dim 扩展earcut / linkedList支持三维顶点输入分块合并earcut 外层十万级顶点可接受约束边新增 edgeFlip支持指定边保留从那以后我每次接手几何算法包都会先构造一个带洞、凹口多、还夹着几个几乎共线点的多边形跑一遍可视化确认没有穿模和裂缝才继续往下走。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/24 13:47:22 · 阅读 1.2k 耳切法三角化：无序顶点如何生成可直接渲染的三角形索引
简介这是一个基于经典耳切法实现的多边形三角化工具包面向需要处理不规则多边形的C开发者尤其适用于地理数据建模、图形渲染、网格生成等场景。其核心在标准Earcut算法基础上引入Z阶曲线散列优化并扩展支持孔洞、退化边与自相交等复杂情况同时附带与libtess2的对比测试方便开发者评估不同三角化策略的效率和稳定性。压缩包共含33个文件其中以源码文件h/c/hpp/cpp为主并配有可运行的Visual Studio工程配置sln/vcxproj及顶点、索引测试数据csv/txt整体大小4.29MB结构简洁便于快速集成或二次开发。目前已有454人学习下载。通过该资源读者既能直接获得生产级三角化源码也能借助测试数据验证算法效果还可以对比主流三角化库深入理解耳切法优化与边界情况处理的具体实现。若从事地图或几何网格相关工作这份精炼的代码包能有效提升三角化环节的落地效率是一份轻量而实用的参考资料。1. 耳切法三角化无序顶点如何变成可直接渲染的三角形索引头一次接触耳切法Ear Clipping三角化的人多半会问一个问题给一堆乱序顶点凭什么不用先做复杂的约束 Delaunay 剖分就能返回一组能直接喂给 GPU 的顶点索引这个项目拆开看之后答案其实很直白——把多边形顶点按顺序串成环形链表然后像剥洋葱一样逐一切掉“耳朵”三角形索引就从链表节点的顺序里冒出来了。它解决的是很具体的场景WebGIS 围栏绘制、游戏寻路网格、CAD 填充算法都需要把凹多边形甚至带洞多边形快速切成三角形同时保证索引顺序稳定可复用。适合两类人一类是刚接触几何算法的初学者另一类是在做几何引擎、需要快速三角化方案的开发者。2. 算法原理与项目结构耳切法如何组织一次三角化2.1 耳切法的核心思路什么才算一只“耳朵”耳切法这个名字听起来有点怪但思路非常朴素。在一个简单多边形里连续三个顶点 A、B、C 如果满足两个条件B 所在的那一小块就是一个“耳朵”第一A-B-C 的转向和整个多边形的绕序一致第二以 A、B、C 为顶点的三角形内部没有其他多边形的顶点。把这个耳朵切掉得到一个三角形剩下的是一个少了一个顶点的多边形继续重复找耳朵、切耳朵的过程直到剩下最后两个点为止。判断“耳朵”时用到的几何工具是叉积和点-三角形包含测试。叉积的正负用来判断三个点的转向方向如果转向和主多边形绕序相反说明这是一个凹口而不是耳点-三角形测试则保证切掉的三角形内没有残留点。这两步在当前项目里对应了 isEar 函数和 pointInTriangle 函数是整个算法最核心的判定逻辑。这个算法的时间复杂度在最坏情况下是 O(n²)因为每次找耳朵都可能要把剩余的所有顶点过一遍。但实际工程里很难真的跑满 n²因为切掉耳朵后剩下的多边形越来越小而且现代实现通常会在开头用空间填充曲线排一遍序让点与点之间的邻近关系先被粗略整理实际耗时往往接近 O(n log n)。对于几千个顶点以内的输入这个性能表现在前端场景完全够用。2.2 项目目录与关键文件解压源码包之后目录结构很短没有一堆用不上的脚手架文件。核心东西一眼就能扫完路径职责src/earcut.js算法主文件包含 earcut 入口、链表构建、耳朵判定、洞桥接src/earcut.d.tsTypeScript 类型声明给编辑器提供参数提示test/earcut.test.js单元测试覆盖顺时针、逆时针、带洞、自交、退化输入demo/index.html浏览器可视化调试页面拖拽顶点即可看三角化结果README.mdAPI 说明与参数表src/earcut.js 是单文件实现全部代码压缩前不到 300 行没有依赖任何第三方库。这意味着它可以直接被浏览器script标签加载也可以被现代打包工具按模块引入。demo 页是实际调试时最有价值的东西——它把三角化结果直接画在 Canvas 上顶点可以拖拽拖动时三角形实时重切改写算法后马上就能看到效果。2.3 快速上手三种跑起来的方式如果是 Node.js 环境从源码包拿到 src/earcut.js 后在相同目录下执行 npm init 建立一个 package.json然后安装 esbuild 或直接用 node 的内置模块加载方式跑通npm init -y npm install esbuild --save-dev npx esbuild src/earcut.js --bundle --formatesm --outfiledist/earcut.mjs打包完成后就可以在业务代码里 import 进来。如果只是想在浏览器里快速看效果不装任何构建工具直接打开 demo/index.html 就能跑。页面里预先塞了几个示例多边形包括凹多边形、带洞多边形和包含重复 x 坐标的退化多边形切换选项卡就能看到不同的三角化结果。拿到源码后我的习惯是先不看实现用 demo 页面把预设的几组用例全部跑一遍观察三角形有没有跨出多边形边界、带洞的洞内有没有被错误填充。确认直觉之后再去逐行读 src/earcut.js。这种做法能快速建立对算法的“体感”比直接看代码理解得更牢固。3. 核心模块源码拆解从一串坐标到一组三角形索引的完整链路3.1 earcut() 主入口数据预处理与主循环主入口函数签名非常短earcut(data, holeIndices, dim)。data 是一个扁平的坐标数组形如 [x0, y0, x1, y1, x2, y2, ...]holeIndices 是可选参数表示每个洞在顶点列表里的起始顶点编号而不是坐标偏移量dim 默认为 2表示每个顶点的分量个数。返回结果是一个索引数组每三个值对应一个三角形。export function earcut(data, holeIndices, dim 2) { const hasHoles holeIndices holeIndices.length; const outerLen hasHoles ? holeIndices[0] * dim : data.length; let outerNode linkedList(data, 0, outerLen, dim, true); const triangles []; // 顶点数量少于 3 或退化成一条线时直接返回空数组 if (!outerNode || outerNode.next outerNode.prev) return triangles; // 存在洞时先把洞链表桥接到外环链表上 if (hasHoles) outerNode eliminateHoles(data, holeIndices, outerNode, dim); // 把环形链表的节点收集到数组方便遍历 const nodes []; let node outerNode; do { nodes.push(node); node node.next; } while (node ! outerNode); // 主循环找耳朵切掉记录索引 while (nodes.length 2) { const ear findEar(nodes); if (!ear) { // 找不到可切耳朵说明存在自交或退化做切分兜底再继续 splitEar(nodes); continue; } nodes.splice(nodes.indexOf(ear), 1); triangles.push(ear.i, ear.prev.i, ear.next.i); } return triangles; }这里有一个参数容易一开始就踩错holeIndices 传入的是顶点编号不是 data 数组的坐标下标。比如 data 里有 10 个顶点洞从第 5 个顶点开始holeIndices 传 [5]而不是 [10]。计算 outerLen 时用 holeIndices[0] * dim 换算成坐标偏移量是因为 data 是扁平数组每个顶点占 dim 个数字。dim 大于 2 时坐标偏移按比例放大同时 data 数组里每个顶点占据的区间也变长了。主循环跳出后返回的 triangles 数组长度为 (n - 2) * 3无洞情况下其中 n 是多边形顶点个数。这个索引数组可以直接配合原始 data 使用在 WebGL 中顶点缓冲上传 data索引缓冲上传 trianglesdrawElements 就能画出一整个填充的多边形。这也是“无序顶点 获取顶点索引”这个需求被解决的核心方式——输入只需要坐标输出自动帮你排好三角形顺序。3.2 linkedList把扁平坐标变成环形双向链表耳切法的核心数据结构是双向链表。每个链表节点记录一个顶点的坐标、它在原始 data 数组中的索引位置以及前驱和后继节点。这个实现里选择双向链表而不是数组是因为切掉一个耳朵时要频繁做删除操作链表删除是 O(1)而数组删除会导致后续元素整体搬移。function linkedList(data, start, end, dim, clockwise) { let last null; let first null; // start 和 end 是 data 数组的下标区间步长为 dim for (let i start; i end; i dim) { const node { i: i / dim, // 顶点索引坐标下标除以 dim x: data[i], // x 分量 y: data[i 1], // y 分量 prev: null, next: null }; if (last) { node.prev last; last.next node; } else { first node; } last node; } if (!last) return null; // 首尾相接成环 first.prev last; last.next first; // 如果绕序和期望不一致整环反转 if (clockwise ! isClockwise(first)) { reverseList(first); } return first; }node.i 这个字段非常关键。它保存的是顶点在输入数组中的逻辑编号比如 dim2 时data 里第 0 和第 1 个数对应索引 0第 2 和第 3 个数对应索引 1。算法最终返回的就是这些逻辑编号而不是物理坐标。这样一来调用方拿到的索引数组直接映射原顶点缓冲不需要再做一次坐标查找。clockwise 参数的作用值得展开。同一个多边形按不同方向输入顺时针或逆时针几何形状完全一样但叉积的正负会翻转导致耳朵判定被反转。如果不统一绕序原本应该是耳朵的点会被判定为凹口。这里通过 isClockwise 检查面积正负不一致时把链表的 next/prev 全部交换整个环的方向就翻转过来了。这个步骤在无洞场景下有一半概率会触发属于最常见的隐性修正。3.3 isEar 判定凸点、凹点与点-三角形测试耳切法的成败系于一个判定函数。isEar 的逻辑分两层先看三个连续点的转向是否符合多边形整体绕序再看三角形内部有没有“碍事”的其他顶点。function isEar(ear) { const a ear.prev; const b ear; const c ear.next; // area 计算的是 a-b-c 的有向面积 // 符号与多边形绕序一致时才是凸出方向返回负数代表可切 if (area(a, b, c) 0) return false; // 检查三角形 abc 内部是否含有多边形的其他顶点 let p ear.next.next; while (p ! ear.prev) { if (pointInTriangle(a.x, a.y, b.x, b.y, c.x, c.y, p.x, p.y) area(p.prev, p, p.next) 0) { return false; } p p.next; } return true; }第一个条件里 area 0 判定为假耳朵是因为这个实现的绕序约定是顺时针此时凸出的三点组成的有向面积为负。如果输入数据是逆时针顺序linkedList 阶段已经做了反转所以进入 isEar 时所有节点的绕序是统一的。这个前提非常重要——如果有人在 linkedList 里注释掉绕序修正耳朵判定会大面积失效最终切出来的三角形会互相重叠。第二个条件是常规的点-三角形包含测试。它的作用是把“耳朵”限制在空三角形内避免切掉一个包含其他顶点的三角形否则后续切耳时那些被包住的点会变成非法状态。pointInTriangle 实现使用的是重心坐标或叉积符号一致法不涉及开方和三角函数对性能友好。实测下来这个函数是整体热路径里被调用次数最多的一万个顶点的输入下会被调用百万次以上所以实现里尽量避免了除法。3.4 桥接洞带洞多边形怎么变成单环无洞多边形只需要一个环形链表但带洞多边形有多个环。耳切法要求输入是单环简单多边形所以必须把每个洞的环“桥接”到外环上。常见做法是找洞环中 x 最小的顶点然后在外环上找一个可见顶点把洞环从那个点切开双向插入到外环链表中。function eliminateHole(holeNode, outerNode) { // 找洞环里 x 坐标最小的顶点作为桥接起点 let m holeNode; let h holeNode; do { if (m.x h.x) m h; h h.next; } while (h ! holeNode); // 在外环上找能“看到” m 点的顶点 p // 可见性定义为 p-m 连线不与任何边相交 const p findVisibleOuterVertex(m, outerNode); // 把洞环从 m 点拆开插入 p 和 p.next 之间 const holePrev m.prev; const outerNext p.next; p.next m; m.prev p; outerNext.prev holePrev; holePrev.next outerNext; return outerNode; }可见性判断是这个桥接过程里的硬骨头。一个顶点 p 到洞顶点 m 的连线不能穿过外环的任何一条边也不能落到外环外部。最直接的做法是遍历外环所有边做线段相交测试复杂度 O(n·m)其中 n 是外环顶点数m 是洞顶点数。这个实现里对洞列表先按 x 坐标做了排序排序后取 x 最小的洞优先桥接能减少一部分无效尝试。有一个容易忽略的事实桥接完之后外环链表和洞链表合并成一个环但“外环 桥接线 洞环”组成的形状仍是一个简单多边形只是桥接线被走了两遍。耳切法在这个合并后的单环上运行切到最后自然会把洞内部的三角形也切出来最终得到的索引数组天然把洞挖空了不需要额外做剔除。3.5 索引输出的约定为什么它适合直接喂给渲染管线三角化的输出格式直接影响对接成本。这个项目的输出约定和 Three.js、PixiJS 等渲染库的 Geometry 接口完全兼容一个 Uint16Array 或 Uint32Array 的索引数组每三个元素构成一个三角形元素值是顶点编号。// 一个正方形的坐标左下、右下、右上、左上 const data [0, 0, 10, 0, 10, 10, 0, 10]; const indices earcut(data, null, 2); // indices 形如 [0, 1, 2, 0, 2, 3] // 对应两个三角形 // 顶点0(0,0), 顶点1(10,0), 顶点2(10,10) // 顶点0(0,0), 顶点2(10,10), 顶点3(0,10)从这段代码能看出三个特点。第一索引值不是物理坐标而是逻辑顶点号第二三角形绕序统一为逆时针配合 WebGL 默认的正面剔除规则不需要额外设置 winding order第三多边形顶点越多索引数组与顶点数组的比例越接近 3:1内存开销是可控的。实际对接时如果顶点数超过 65535需要用 Uint32Array 承载索引此时注意 earcut 返回的是普通数组还是类型数组——这个实现在内部始终使用普通数组所以在数据量大时做一次类型转换是值得的。4. 避坑手册绕序、洞索引与精度问题的翻车记录4.1 顶点方向反了导致整块面被剔除现象三角化返回的索引看着正常但渲染出来多边形是“漏”的只有背面的颜色正面永远显示不出来。原因输入多边形是逆时针围成而 earcut 内部绕序修正在某种输入组合下没有触发预期效果导致输出的三角形方向和 WebGL 的正面规则不一致被背面剔除机制丢弃了。解决在调用侧显式检查多边形的有向面积确保输入绕序统一。更保险的办法是用 demo 页验证一次方向敏感的用例比如一个逆时针正方形和一个顺时针正方形对比两者输出的三角形索引绕序。从那以后我每次对接新几何库都会把方向翻转用例加进测试清单里一劳永逸。4.2 holeIndices 把顶点编号当坐标下标现象带洞多边形调用 earcut(data, [n], 2) 后洞完全没有被挖掉或者多边形形状变得混乱三角形穿插到洞内部。原因holeIndices 期望的是顶点编号比如第 5 个顶点写 5写成 10 的话链表构建会从第 10 个顶点开始跳过前面 5 个顶点整个多边形环就断了。解决确认 holeIndices 里的数字一定要乘上 dim 才是 data 的坐标下标这个换算关系。调试时可以写一段打印代码外部传入 holeIndex 后内部用 holeIndex * dim 做链表起点把起点坐标打印出来对照原数据一眼就能发现问题。4.3 自交多边形的死循环现象输入一个五角星或“蝴蝶结”形状边与边相交三角化过程会长时间不返回或者返回大量面积为负的退化三角形。原因耳切法的前提是简单多边形自交多边形不满足这个假设。找耳朵的过程中某些点会被反复判定为不可切兜底逻辑如果不够健壮就会陷入死循环。解决先对输入做一次简单性校验检查任意两条非相邻边是否相交。最轻量的做法是用线段相交测试做一次 O(n²) 扫描如果检测到自交就把多边形按交点拆成多个简单子多边形分别三角化再合并索引。或者直接拒绝输入并提示调用方数据异常。4.4 共线点与浮点精度导致的裂缝现象输入多边形包含多个几乎共线的顶点比如两个相邻边的夹角接近 180 度。三角化后某些三角形变得特别瘦长渲染时像素上出现微小裂缝或闪烁。原因真实几何数据里相邻点距离很远浮点数精度无法精确区分点是否在三角形边界上。pointInTriangle 的判断结果不稳定同一个点在极端坐标下有时被判定为在内部有时在边线上造成相邻三角形共享边断裂。解决在判断点是否在三角形内部时给边界条件加一个最小容差。例如把“点在边上”当作“点在外部”以此消除裂缝或者在 area 计算里对绝对值小于 1e-9 的结果归零让共线点被识别为退化边而跳过。5. 运行与验证把三角化结果“看”明白5.1 命令行测试用断言验证索引正确性源码包带的 test/earcut.test.js 覆盖了不少经典用例。跑测试的命令很简单node --test test/earcut.test.jsNode 内置的 test runner 不需要额外安装依赖。测试用例里最值得关注的是索引闭环验证一个合法三角化的索引数组每组三个索引对应的坐标点应该能构成一个面积为正的三角形并且所有三角形的面积之和等于原多边形的面积对于带洞多边形等于外环面积减洞面积。这个验证能快速排查输出索引是否有重复、遗漏或乱序。如果你要自己加用例我一般会写一个 validate 函数接收 data 和 indices遍历每组三角形做面积累加和预期面积做差误差超过 1e-6 就抛出异常。这个校验对后续改算法时非常有用比人眼检查靠谱得多。5.2 可视化验证把顶点拖到任意位置看实时结果demo/index.html 是整个源码包里最直观的验证工具。它用 Canvas 把三角形画出来每个多边形顶点渲染成一个可拖拽的圆点。拖动顶点时页面会重新调用 earcut 并重绘全部三角形。用这个页面做验证时有几种值得尝试的输入把所有顶点拖到一条水平线上退化输入观察程序是否崩溃把多边形的一个顶点拖到很远的位置极端比例观察三角形是否出现细长的条纹把一个洞拖到贴近外环边缘观察桥接逻辑是否稳定。这些边界情况比常规用例更容易触发实现里的隐藏缺陷。5.3 交叉验证和扫描线三角化对比比单元测试和可视化更进一步的是交叉验证。用另一个独立实现的三角化算法比如扫描线多边形三角化对同一组输入跑一遍对比两者输出的三角形数量、面积总和、以及三角形之间是否有重叠。// 用一个极不规则的凹多边形做交叉验证 const data [ 0, 0, 10, 0, 12, 5, 10, 10, 5, 12, 0, 10, -4, 5, 0, 3, 3, 4, 1, 1 ]; const t1 earcut(data, null, 2); const t2 scanlineTriangulate(data); // 对比实现 console.assert(t1.length t2.length);面积对比是校验三角化合法性的金标准。如果两套独立实现算出来的面积差在 1e-6 以内基本可以确定这次的索引输出没毛病。6. 二次开发改造从耳切走向更多场景的三个方向6.1 维度扩展dim 参数改成 3earcut 的 dim 参数天然支持三维顶点只需要在数据里让每个顶点占 3 个数字。但是 area 计算用的是二维叉积z 分量不会影响三角形方向。如果你要做地形三角化需要额外考虑法线方向的计算。// 三维地形顶点x, y, z 交替存储 const terrain [ 0, 0, 0, 1, 0, 2, 2, 0, 1, 0, 1, 1, 1, 1, 3, 2, 1, 0, 0, 2, 2, 1, 2, 1, 2, 2, 2 ]; const indices earcut(terrain, null, 3);6.2 大规模顶点先分块再耳切当顶点数上万时即使 z-order 优化加持主循环仍然可能成为瓶颈。常见做法是先用网格把输入顶点按空间分布分块每块几百个顶点单独三角化然后合并索引。合并时注意每个块的顶点编号要做一个偏移量否则索引会重叠。6.3 约束边从耳切走向 CDT耳切法本身不做约束边处理也就是不能指定某两条顶点之间的连线必须保留在三角化结果里。如果要做这个扩展可以在耳切完成之后对相邻三角形做边交换检查约束边是否已存在不存在就翻转共享边直到约束边成为三角形的一条公共边。这是从耳切法迈向约束 Delaunay 三角化最实用的一步实现量也不大。改造点涉及函数预期效果dim 扩展earcut / linkedList支持三维顶点输入分块合并earcut 外层十万级顶点可接受约束边新增 edgeFlip支持指定边保留从那以后我每次接手几何算法包都会先构造一个带洞、凹口多、还夹着几个几乎共线点的多边形跑一遍可视化确认没有穿模和裂缝才继续往下走。希望帮到你。本文还有配套的精品资源点击获取