简介：这是一份基于耳切法（Ear Clipping）实现多边形三角化的 C++ 资源，核心库源自 mapbox 的 earcut 算法，并参考 FIST 与 David Eberly 的经典思路做了改良。它通过 Z 阶曲线散列优化顶点排序，能够处理带孔洞、扭曲、退化及自相交的多边形，面向需要从无序顶点快速生成三角形索引的图形学、GIS 与游戏开发场景。压缩包共33个文件，大小约4.29MB，主体为10个 h 头文件、7个 c 源码、4个 hpp 及2个 cpp 工程实现，另含4个 csv 测试数据、工程解决方案和说明文档，便于直接编译与对比验证。包内同时提供了 libtess2 对照实现和 fixtures 典型用例，适合希望研究三角化原理、替换现有剖分方案或做算法对比的中高级开发者。目前已有454人学习下载，既可用于三维建模、地图数据简化等生产实践，也可作为图形学算法学习与二次改造的起点。

1. 无序顶点三角化：Earcut 耳切法解决的是渲染管线的最后一公里

某个跨平台可视化项目里，地图模块需要把用户随手画的多边形区域填充成半透明色块。开发组最开始用图形 API 的 stencil 机制临时兜底，结果复杂轮廓出现漏填和边缘错位，被迫回到最经典的问题：任意多边形如何快速变成一组可直接渲染的三角形索引。Earcut 耳切法三角化就是在这时进场的。它接受无序的平面顶点数组，返回一组可直接交给 drawElements 的三角形索引，包体极小、无第三方依赖，源码能嵌入 C++、JavaScript、Python 等主流工程。适合正在做地图围栏、CAD 多边形编辑、图像 ROI 裁剪或 UI 异形控件渲染的开发者。拿到资源后先把顶点组织成闭合环，剩下的索引生成与孔洞桥接全部交给它。这不是玄学，而是一个有明确边界条件的工程答案。

2. 耳切法原理与选型：从“切耳朵”到稳定拿索引

2.1 耳切法核心流程：先确定“耳朵”再切掉

耳切法处理的对象是简单多边形，也就是由一组闭合顶点构成的环。它的思路很直白：每次取连续三个顶点 P[i-1]、P[i]、P[i+1]，判断这三个点组成的三角形是否满足两个条件——一是中间点相对于多边形是凸的，二是该三角形内部不包含多边形其他任何顶点。满足条件就称 P[i] 为“耳尖”，把这个三角形切下来，并从环中删除 P[i]，继续对剩余顶点重复这个过程，直到剩下的顶点少于 3 个。

朴素实现的复杂度是 O(n²)，因为每个“耳朵”都要做一次全量扫描，检查是否有点落在三角形内部。一个 10000 顶点的轮廓，在低端设备上就能感觉到明显卡顿。Earcut 的改进点在于两点：一是先用扫描线思想把顶点按 X 坐标排序，让“点是否在三角形内”的判定只发生在局部区间，而不是每次遍历全部顶点；二是用双向链表管理环结构，删除一个耳尖只需要改前后节点的指针，不需要频繁挪动数组。工程实现上复杂度接近 O(n log n)，内存占用 O(n)，对几千个顶点的行政区划边界基本是毫秒级。

需要特别说明的是，耳切法的输入必须是“已构成闭合环”的顶点。如果你拿到的是一堆点云，没有邻接关系，那第一步永远是先把散点连成多边形轮廓，而不是直接丢给 Earcut。这也是很多新手第一次调用失败的根本原因。

2.2 无序顶点不失控：索引始终指向原始数组

关键词“无序顶点”需要精确理解。Earcut 并不接受完全乱序的点云，它要求每个环内部的顶点按轮廓邻接顺序排列；但环的起点可以任意，多个环之间的先后顺序可以任意，每个环是顺时针还是逆时针也可以任意。这些“无序”信息 Earcut 会自己在初始化阶段梳理清楚。

它依赖的是带符号面积公式：

signedArea = 0.5 * sum((x_i * y_i+1) - (x_i+1 * y_i))

遍历一个环的所有顶点，得到的结果是正数说明环为逆时针，负数说明环为顺时针，绝对值等于环面积。Earcut 内部用这个公式完成三件事：判断外环与孔洞的面积量级、给孔洞配对到正确的外环、在必要时反转孔洞顶点的遍历方向。

对外表现上，最重要的设计是它不修改你传入的顶点数组，而是返回“顶点索引”。每个索引都是原数组的下标，从 0 开始计数。这意味着你把顶点 Upload 到 GPU 顶点缓冲后，只需要替换索引缓冲，不需要重排顶点坐标。图形渲染里最耗带宽的操作之一就是顶点重排，Earcut 把这个开销直接省掉了。

2.3 选型对比：为什么先试 Earcut 而不是 Delaunay

耳切法一个容易被低估的优势是“边界锁定”。Delaunay 在凹多边形外侧会出现越过边界的三角形，因为它的优化目标是最大化最小角，而不是保持边界完整；除非额外加约束边，否则凹口的视觉效果会直接出错。耳切法每一步都是沿着当前多边形的边切，三角形天然被限制在边界内部，省掉了约束处理。对地图围栏、ROI 裁剪这类要求边界精确的场景，这就是决定性差异。

3. 把 Earcut 接进渲染流程：输入格式与索引数组解读

3.1 输入约定：扁平数组、维度参数与环组织

Earcut 的核心函数签名非常朴素，以 JavaScript 版本为例：

const indices = earcut(vertices, holes, dim);

三个参数分别说明：

• vertices：一维扁平数组，坐标按[x0, y0, x1, y1, ...]交错排列。所有环的顶点依次拼接在同一个数组里。
• holes：记录每个孔洞第一个顶点在vertices中的下标。没有孔洞时传空数组或null。
• dim：顶点维度步长，默认是 2，表示每读两个数取一组(x, y)。

看一个最小例子：

// 一个矩形，四个顶点，逆时针 const vertices = [0, 0, 100, 0, 100, 100, 0, 100]; const holes = []; const indices = earcut(vertices, holes, 2); console.log(indices); // 例如 [2, 1, 0, 3, 2, 0]

dim参数常被忽略但很重要。如果你的模型带 Z 坐标，顶点数组是[x0, y0, z0, x1, y1, z1, ...]，就必须把dim设为 3，否则 Earcut 会把x0和z0当成一个二维点来读，索引结果直接错乱。

3.2 输出约定：每三个索引一组，方向跟随输入环

返回的indices是一个一维数组，长度永远是 3 的倍数。每三个元素描述一个三角形，例如[a, b, c]，表示顶点数组中下标为a、b、c的三个坐标点按顺序构成一个三角形。

三角形绕序与输入环方向保持一致。输入外环是逆时针排列，输出三角形基本也是逆时针；输入外环是顺时针，输出也相应翻转。对光照计算敏感的 3D 场景，这一步需要提前确认，否则会看到法线反向导致的变暗或剔除错误。

把索引拆成三角形列表的代码模式如下：

const tri = []; for (let i = 0; i < indices.length; i += 3) { tri.push([ indices[i], indices[i + 1], indices[i + 2] ]); }

拿到每个三角形的三个顶点下标后，配合原始顶点数组就能取出实际坐标。Earcut 返回三角形数量的规律是：对没有任何退化点的简单多边形，三角形数量 = 顶点数 - 2。五个顶点的凹五边形，期望得到 3 个三角形；如果你的结果数量明显多于这个值，大概率是顶点中存在重复点或共线点，见第 5 章的排查。

3.3 完整示例：从无序五边形到可绘制三角形

下面给一个完整可运行的示例，输入是一个五边形，环起点故意选在中间位置，验证 Earcut 对“起点随意”的兼容性：

import earcut from './earcut.js'; // 五边形顶点，起点不是左下角 const polygon = [ 120, 300, 380, 320, 400, 120, 60, 80, 50, 200 ]; const indices = earcut(polygon, null, 2); console.log('三角形数量:', indices.length / 3);

把三角形描到画布上验证：

function drawTriangulated(ctx, points, indices) { ctx.beginPath(); for (let i = 0; i < indices.length; i += 3) { const a = indices[i]; const b = indices[i + 1]; const c = indices[i + 2]; ctx.moveTo(points[a * 2], points[a * 2 + 1]); ctx.lineTo(points[b * 2], points[b * 2 + 1]); ctx.lineTo(points[c * 2], points[c * 2 + 1]); ctx.closePath(); } ctx.fill(); }

这段代码的关键点是：绘制时从points里取坐标一定要用a * 2和a * 2 + 1，因为顶点数组是扁平结构，下标乘以 2 才能跳到对应顶点的 X 坐标。很多移植到 WebGL 的项目在这里栽跟头，索引正确但取坐标的地址计算错了，看起来就全是乱线。

4. 带孔洞与复杂轮廓：holes 参数、边界方向与容错范围

4.1 holes 数组记录的是每个孔洞起始点下标

带孔洞是多边形三角化里最常用的能力，比如地图上一个行政区域内部有湖泊，或者 CAD 图形里一个法兰盘上有螺栓孔。Earcut 的孔洞输入方式很特别，不是传第二个数组，而是在同一个vertices数组里继续追加孔洞顶点，然后用holes数组标记每个孔洞从哪里开始。

// 外部矩形 const outer = [0, 0, 1000, 0, 1000, 1000, 0, 1000]; // 内部矩形孔洞 const hole = [250, 250, 750, 250, 750, 750, 250, 750]; // 拼接成一个数组 const all = outer.concat(hole); // holes 传 [4]：孔洞第一个顶点在 all 中的下标是 4 const indices = earcut(all, [4], 2);

4这个数字不是顶点序号，而是all数组里孔洞起始点的扁平下标。外环 4 个点占掉下标 0 到 3，所以孔洞第一个顶点的扁平下标是 4。多个孔洞就传多个下标：

const indices = earcut(all, [4, 12, 20], 2);

表示all中下标 4、12、20 分别是三个孔洞的起点。Earcut 会从每个起点读到数组末尾，或读到下一个起点之前，从而切分出每个环。所以拼接时顺序不能乱，外环在前，孔洞按顺序依次追加。

4.2 环方向与外环匹配：面积符号自动兜底

不少教程要求外环和孔洞方向相反，也就是外环逆时针、孔洞顺时针。这个约定在某些手工实现里确实存在，但在 Earcut 中不是必须的。内部排序阶段会先用带符号面积计算每个环的方向与大小，然后自动把孔洞匹配到最合适的外环上，再沿着桥接边把内环并入外环形成一个“带切口”的等价多边形，之后统一做耳切。

这也解释了为什么 Earcut 返回的索引里会出现外环顶点和孔洞顶点交替出现的情况——桥接过程会在两个环之间建立一对连接点，剖分时三角形可能跨过桥接线，从一个环跳到另一个环。索引语义依然正确，只是你不能再假设三角形完全落在同一环内。

自定义实现这个桥接逻辑非常容易出错，一旦桥接点选择不当，剖分结果就会出现穿透孔洞或丢失边界的三角形。用现成的 Earcut 至少能避免这一层手工维护，代价是你必须正确传holes下标。

4.3 容错边界：重复点、共线点与自相交的限制

Earcut 能容忍一定程度的脏数据：重复顶点会被跳过，共线顶点形成的零面积“耳朵”会在判凸阶段被过滤。如果传入的顶点少于 3 个或全为重合点，返回空数组而不是报错。

但有一个边界它明确处理不了：自相交多边形。两根边界边交叉成 X 形状时，耳切法无法确定该保留哪个区域，输出结果没有语义保证。项目里如果用户能自由拖拽多边形节点，必须先在上一层做自相交检测，而不是指望三角化库兜底。

另一个容易忽略的限制是浮点数精度。超大坐标会让叉积计算接近机器精度上限，表现为某些“耳朵”判定时好时坏。通常解法是先把所有顶点减去多边形的最小 X、最小 Y，完成三角化后再把坐标整体平移回去。这个预处理不影响索引结构，因为平移不改变拓扑关系。

5. 避坑指南：Earcut 高频翻车点与四条排查路径

5.1 环内顶点顺序乱跳，三角形互相交叉

现象：调用 Earcut 后返回的索引能画出三角形，但三角形互相穿插，甚至覆盖到多边形外部。

原因：环内顶点没有按轮廓邻接顺序排列。耳切法依赖相邻顶点的相对关系，如果输入序列里相邻两个点实际并不相邻，等价于喂了一个自相交或非简单的“折线环”，算法无法建立正确内外边界。

解决：进入 Earcut 之前，先对多边形顶点做一次环闭合检查。常见做法是按照计算几何里的极角或邻接表排序，把顶点重排成单一闭合链。我一般会在数据层面对源顶点做“从第一个点开始沿邻接关系遍历，直到回到起点”的校验，排完序再剖分。

5.2 孔洞没进 holes 数组，剖分把洞直接填平

现象：多边形中间应该透明的孔洞区域被三角形覆盖，看起来像洞被焊死了。

原因：孔洞顶点只是被拼接进vertices数组，没有在holes参数中声明起始下标，Earcut 把所有顶点当成一个连续的大环处理。

解决：拼接顶点时同步记录每个孔洞的起点下标。常见的代码写法是：

let cursor = outer.length; const holesIndex = []; for (const h of holeList) { holesIndex.push(cursor); cursor += h.length; } const all = outer.flatMap(p => [p.x, p.y]) .concat(holeList.flatMap(p => [p.x, p.y])); const indices = earcut(all, holesIndex, 2);

处理顺序不能乱，cursor必须在拼接之前记录，否则下标会整体偏移。

5.3 带 Z 坐标时忘记调整 stride

现象：传入的是[x, y, z, ...]交错数组，dim还是默认的 2，剖分结果出现索引越界或三角形完全错乱。

原因：Earcut 按dim个连续数字读一个点。dim为 2 时，它把y之后的下一个z当成了下一个点的x，整个坐标体系错位。

解决：数组里每个点占 3 个数就传3，占更多就传对应值。如果你的数据是分离的x[]、y[]、z[]三个数组，需要先交错合并成扁平数组再调用。这个坑在 WebGL 项目中很常见，因为顶点缓冲本身就是带 Z 的，顺手写2的人不在少数。

5.4 大坐标下耳朵判定不稳定

现象：使用地理经纬度这类大数坐标时，同一段逻辑偶尔剖分成功，偶尔产生空洞或三角形缺失，且跟边界条件相关。

原因：大坐标使叉积和面积计算的结果量级偏大，相对精度下降。当两个相邻三角形面积差极小时，浮点数误差可能翻转判凸符号。

解决：剖分前对坐标做平移，把所有顶点减去包围盒的最小角点，让数值落在一个相对小的量级里。注意平移后，返回的索引仍然指向原始顶点数组，所以不要对原始坐标做任何改动，只影响中间计算。

6. 三角化结果的面积校验与工程验证习惯

6.1 用三角形面积总和反推多边形面积

验证剖分是否正确，最直接的办法是计算面积守恒。一个正确的三角化，所有三角形面积之和应等于原多边形有向面积的绝对值。

function triArea2D(p, a, b, c) { return (p[b*2] - p[a*2]) * (p[c*2+1] - p[a*2+1]) - (p[b*2+1] - p[a*2+1]) * (p[c*2] - p[a*2]); } let sum = 0; for (let i = 0; i < indices.length; i += 3) { sum += Math.abs( triArea2D(polygon, indices[i], indices[i+1], indices[i+2]) ); } // 与多边形总面积比较，容差建议在 0.1% 以内

如果缺口超过 0.1%，多半是孔洞未声明或顶点顺序有问题，而不是 Earcut 本身出错。

6.2 顶点数与孔洞数量守恒校验

不带孔洞的简单多边形满足三角形数量 = 顶点数 - 2。带 h 个孔洞时，公式变为三角形数量 = 总顶点数 + 2 * h - 2。这是一个很强的约束条件，适合做成自动化的断言：

const expected = vertexCount + 2 * holeCount - 2; if (indices.length / 3 !== expected) { console.warn('三角化结果与理论值不一致'); }

注意这个公式建立在没有退化点被过滤的前提下，共线点或重复点会导致 Earcut 跳过部分顶点，这时用公式做参考而不是硬卡。

6.3 把三角化结果与调试渲染拆成独立步骤

工程实践上，我会把三角化结果缓存成单独的索引数组，再在调试面板里给每个三角形描白色细边、半透明填充，和原始多边形边界做叠加对比。能看到孔洞边缘完整、外边界清晰，才算通过验证。

从那以后，每次把 Earcut 接入新模块，我都会强制走一遍面积守恒、三角形数量约束、描边可视这三道检查。看似多花几分钟，实际省掉的是在集成阶段反复排查多边形漏洞的时间。希望帮到你。

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