耳切法三角化：无序顶点如何生成可直接渲染的三角形索引

简介：这是一个基于经典耳切法实现的多边形三角化工具包，面向需要处理不规则多边形的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 是单文件实现，全部代码压缩前不到 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 --format=esm --outfile=dist/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，索引缓冲上传 triangles，drawElements 就能画出一整个填充的多边形。这也是“无序顶点 + 获取顶点索引”这个需求被解决的核心方式——输入只需要坐标，输出自动帮你排好三角形顺序。

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 这个字段非常关键。它保存的是顶点在输入数组中的逻辑编号，比如 dim=2 时，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.js

Node 内置的 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 参数改成 3

earcut 的 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 三角化最实用的一步，实现量也不大。

从那以后我每次接手几何算法包，都会先构造一个带洞、凹口多、还夹着几个几乎共线点的多边形跑一遍可视化，确认没有穿模和裂缝才继续往下走。希望帮到你。

本文还有配套的精品资源，点击获取