简介一套基于耳切法的多边形三角化实现面向游戏开发、地理信息建模及计算机图形学开发者解决从无序顶点快速生成三角形索引的问题。实现采用改进的耳朵切片算法借助空间填充曲线散列优化能够处理带孔洞、扭曲、退化乃至自相交的多边形适用于地理形状等实用数据思路参考了多边形快速三角化与耳切法的经典论述。压缩包共三十三个文件大小约4.29兆字节。其中以头文件与源码文件为主辅以数据文件存放顶点和索引测试样本另有工程配置文件便于直接编译运行说明文档则补充使用与构建信息。目前已有454人学习下载。通过源码可通晓耳切三角化的完整实现流程、散列优化细节并对比多种三角化方案随附的测试数据有助于自行验证算法在复杂边界下的表现适合想深入理解高效三角化原理或将其移植到自有项目的开发者。1. 耳切法三角化从无序顶点到可直接渲染的三角形索引第一次把用户在地图上随手画的多边形丢给 WebGL 渲染时我就被三角化这件事教育了一顿用户手绘的顶点方向有顺时针有逆时针有的多边形里还套着几个洞而 GPU 只接受三角形。Earcut-Triangulation.zip 里实现的耳切法Ear Clipping恰好解决这个问题——输入一个坐标平铺数组和可选的洞索引数组输出一组三角形顶点索引直接喂给渲染管线。核心代码是零依赖的 JavaScript 模块浏览器和 Node 都能跑。做 WebGL 绘制、几何编辑、碰撞体生成或单纯想研究几何算法的开发者都值得把这份源码拆一遍读完你就知道它为什么能成为地图渲染场景里被反复复用的那套三角化实现。2. 整体设计与技术选型一个零依赖几何算法包的组织方式2.1 接口设计扁平面数组进三角索引出Earcut 最让人舒服的一点是接口极简。整个算法对外只暴露一个函数调用方不需要维护任何中间状态数据进去、索引出来。/** * 对多边形执行耳切法三角化 * param {Arraynumber} data 顶点坐标扁平数组 [x0,y0, x1,y1, ...] * param {Arraynumber} holeIndices 每个洞的起始顶点序号可空无洞传 null * param {number} dim 坐标维度默认 23D 场景传 3 * returns {Arraynumber} 每三个一组构成一个三角形顶点索引 */ function earcut(data, holeIndices, dim) { dim dim || 2; const hasHoles holeIndices holeIndices.length; // 外环顶点对应的坐标区间 const outerLen hasHoles ? holeIndices[0] * dim : data.length; // 把外环顶点做成双向链表 let outerNode linkedList(data, 0, outerLen, dim, true); // 有洞则逐个合并进外环链表 if (hasHoles) { outerNode eliminateHoles(data, holeIndices, outerNode, dim); } // 核心三角化主循环 const triangles []; if (outerNode) { earcutLinked(outerNode, triangles, dim); } return triangles; }逻辑说明data是扁平数组而不是二维数组索引i对应坐标data[i * dim]和data[i * dim 1]。之所以用扁平结构是为了方便调用方直接把这个数组交给 WebGL 的bufferData省掉一次数据格式转换。holeIndices按「顶点序号」计数而不是按坐标分量数计数——外环有 5 个顶点、洞从第 6 个顶点开始那holeIndices第一项写 5对应数据偏移是data[10]。这个单位最容易传错后面避坑章节我专门展开。dim参数只在读取坐标时生效不影响三角形索引的输出格式。从调用者视角看这个 API 属于典型的「两入一出」唯一需要保证的是外环顶点按边界顺序排列方向无所谓。方向归一化、孔洞合并、耳朵剪切全部在函数内部完成这也是它能在各种渲染框架里被反复接入的根本原因——无状态纯函数天然适合嵌入。2.2 目录结构一个算法包该有的最小骨架解压 zip 之后目录组织方式是这样一个结构Earcut-Triangulation/ ├── src/ │ ├── earcut.js // 核心算法实现主战场 │ └── utils.js // 面积、点包含、线段相交等几何工具函数 ├── demo/ │ ├── index.html // 可视化测试页拖动顶点实时看三角化结果 │ └── main.js // Demo 交互逻辑监听鼠标拖拽 ├── test/ │ ├── fixtures.js // 测试多边形凸、凹、带洞、自交等各种形状 │ └── run.js // Node 环境测试入口跑完输出断言结果 ├── package.json └── README.mdsrc/earcut.js是核心整个文件不依赖任何第三方运行时也不需要 import 外部模块utils.js里的函数是直接复制进来或者按需引用的取决于你拿到的是哪个版本。demo目录给浏览器环境用test目录则是 Node 命令行下执行的验证集。这种「核心算法单文件 工具函数分离 浏览器 Demo 命令行测试」的组织方式非常适合一个需要被反复嵌入不同框架的算法型项目。要移植到 C 或 Rust只需要移植src目录要理解算法只需要读earcut.js一个文件。我的习惯是先跑测试再读源码node test/run.js通过之后再对照 fixtures 里的预期索引数组去读主循环这样对耳切法的行为会有直观印象而不是对着抽象的多边形理论硬啃。2.3 选型对比耳切法 vs Delaunay用耳切法而不是 Delaunay是「够用」和「最优」之间的取舍。两类算法都做三角形剖分但出发点不同维度耳切法Ear ClippingDelaunay 三角化复杂度最坏 O(n²)带 Z 序优化后实际接近 O(n log n)理论 O(n log n)实现复杂度高凹多边形可以且实现直观可以但要额外处理带洞支持天然支持通过桥接合并内外环需要约束边界代码量大三角形质量一般可能出现细长三角形自动最大化最小角质量更均匀实现体量核心约 300 行成熟库动辄上千行具体到这个项目场景耳切法赢在三个地方。第一输入要求低顶点方向无所谓不需要构建 Delaunay 那套点集拓扑关系第二实现直观「每次找一个凸角切掉」的逻辑在调试时可以逐步可视化出问题很快能定位是哪一步第三输出直接Delaunay 的三角网需要先提取边界才得到多边形剖分而耳切法输出的三角形天然填满原始多边形内部。当然代价也有如果输入是数千个顶点绕成螺旋状的极端形状最坏 O(n²) 会暴露出来。源码里通过 Z 序曲线Morton 码对顶点做空间哈希让点包含判断的候选范围大幅缩小几百顶点规模下耗时在毫秒级撑得住绝大多数 Web 应用。3. 核心模块拆解顶点链表、耳点判定与剪切主循环3.1 建立双向链表为什么链式结构是耳切法的基础耳切法的前提是能够在多边形边界上快速找到「某个顶点的前一个和后一个」顶点。数组可以做到但删除一个顶点后要不断搬运元素链表则能在 O(1) 时间内摘除一个节点。源码里第一步就是把扁平坐标数组组织成循环双向链表// 链表节点记录顶点坐标、邻接关系和 Z 序信息 function Node(i, x, y) { this.i i; // 顶点在数据数组中的原始序号未乘 dim this.x x; this.y y; this.prev null; // 前驱节点 this.next null; // 后继节点 this.z 0; // Z 序曲线编码用于空间加速 this.nextZ null; // Z 序排序后的后继 this.prevZ null; // Z 序排序后的前驱 this.steiner false; // 是否为算法内部插入的辅助点 } // 把扁平坐标数组的一段区间转成链表 function linkedList(data, start, end, dim, clockwise) { let last null; // 先算整段边界的有向面积决定遍历方向 if (clockwise signedArea(data, start, end, dim) 0) { // 有向面积为正逆时针正序插入 for (let i start; i end; i dim) { last insertNode(i, data[i], data[i 1], last); } } else { // 有向面积为负顺时针倒序插入让链表统一为逆时针 for (let i end - dim; i start; i - dim) { last insertNode(i, data[i], data[i 1], last); } } // 清理首尾重复点防止零长度退化边 if (last equals(last, last.next)) { removeNode(last); last last.next; } return last; } function insertNode(i, x, y, last) { const node new Node(i, x, y); if (last null) { node.prev node; // 单节点环自己指向自己 node.next node; } else { node.next last.next; // 新节点接在 last 之后 node.prev last; last.next.prev node; last.next node; } return node; }逻辑说明参数里start和end是坐标分量索引区间dim是坐标维度clockwise是期望的方向标志。signedArea用鞋带公式计算多边形有向面积正值为逆时针环绕。链表最终统一为逆时针后续所有凸角判断、点包含判断都基于「多边形内部在左侧」这个约定省掉了大量方向条件分支。插入方向的选择也值得注意正序插入时每个新节点接在last后面形成「头→第二个→……→尾→头」的环倒序插入时从末顶点往回收效果等价于先把数组反转再正序插入但避免了额外开辟反转数组。最后重复点清理很重要——多边形数据里经常出现首尾顶点重复封闭多边形习惯把起始点写两遍不清掉的话后续耳点判定很容易选出退化三角形渲染表现为看不清楚的细长三角形加上重叠顶点闪烁。这是我拆完代码后第一个记住的血泪经验。3.2 耳点判定凸角、点包含与剪枝优化耳切法的核心定理很朴素对任意简单多边形至少存在两个「耳朵」——由连续三个顶点组成、中间顶点为凸角、且三角形内部不含其他顶点的三角形。不断切掉耳朵顶点数递减最终形成完整三角剖分。难点在于高效判断「三角形内部不含其他顶点」。// 判断链表中的某个点是否是耳朵顶点 function isEar(ear) { const a ear.prev; const b ear; const c ear.next; // 条件一三角形 abc 的有向面积必须为正逆时针 // 面积 0 说明 b 是凹角或三点共线不可能是耳点 if (area(a, b, c) 0) return false; // 条件二三角形 abc 内部不能包含其他「凸」顶点 // 遍历链表中所有其他节点 let p ear.next.next; while (p ! ear.prev) { // p 落在三角形 abc 内部且 p 自身是凸角则封堵耳点 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; } // 鞋带公式计算三角形有向面积返回实际面积的 2 倍 function area(p, q, r) { return (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); }这个函数有三处值得掰开讲。第一处是area(a, b, c) 0的语义因为我们把多边形统一成逆时针连续三个顶点构成的有向三角形面积为正中间顶点就是凸角面积为负则是凹角。面积为零说明三点共线也不能做耳朵——切下去会产生零面积三角形渲染时会变成看不见的细线。第二处是点包含检查的剪枝条件。直观版本是「遍历所有其他顶点只要任何一个落在三角形 abc 内就判定 b 不是耳朵」。但源码加了一个限定被检查顶点 p 自身必须是凸角。原因在于凹顶点落在耳朵三角形内部时它所处的位置本来就在多边形凹陷区域不会真正封堵这个耳朵。只有凸顶点构成的「内部点」才是有效封堵。这个剪枝在地形边界数据上能省掉大量无谓的点包含运算是性能优化里最出彩的一笔。第三处是点包含判断本身。源码没有用射线法而是先用包围盒快速排除再用叉积符号判断点是否在三角形三条边的同一侧。这段逻辑在utils.js的pointInTriangle里大约二十行是全算法被调用最频繁的热点函数。Z 序优化在这里发挥作用链表外层维护一个按 Morton 码排序的副本点包含检查沿着 Z 序链表遍历时可以提前退出避免扫过全部顶点。3.3 主循环剪切、归档、重连有了isEar判定主循环骨架就很直白了遍历链表找到耳点就剪掉记录三角形索引摘除节点继续下一个。// earcutLinked持续切耳朵直到链表只剩两个节点 function earcutLinked(ear, triangles, dim) { if (!ear) return; let stop ear; // 哨兵节点防止死循环 while (ear.prev ! ear.next) { const prev ear.prev; const next ear.next; if (isEar(ear)) { // 找到耳朵输出三角形顶点索引除以 dim 还原顶点序号 triangles.push(prev.i / dim); triangles.push(ear.i / dim); triangles.push(next.i / dim); // 从链表中摘下 ear 节点重建邻接关系 next.prev prev; prev.next next; // 继续从 prev 方向搜索 ear prev; stop prev; } else { // 当前点不是耳朵挪到下一个节点 ear next; } } }逻辑说明终止条件是链表节点数减到 2ear.prev ear.next此时剩余的退化边由上层逻辑兜底。每轮剪切输出 3 个顶点索引索引除以dim还原成顶点编号。摘除节点只需改两个指针这是链表相对数组最核心的优势。这里有个容易误解的细节ear prev而不是ear next。源码这样选是为了尽量保持「连通区域」优先从同一方向推进减少链表在空间上的跳跃配合 Z 序缓存能获得更稳定的性能。如果改成每次向next方向搜索切出来的三角形形状分布会有细微差别但三角形总数不变、正确性不受影响。stop哨兵的作用是如果一整轮下来没找到任何耳朵说明输入多边形自交或退化此时强制推进避免无限循环。主循环完成后triangles里就是完整的三角剖分索引。到这里「顶点数组 → 双向链表 → 挖耳剪切 → 索引输出」的链路就闭环了。4. 无序顶点与孔洞处理三角化最容易翻车的两个场景4.1 顶点顺序归一化顺时针逆时针通吃的内幕很多初用这个包的人会问我的顶点到底要不要按顺序排答案是「要按边界顺序但方向无所谓」。所谓「无序顶点」指的是用户给出一组边界顶点时方向可以随意——算法内部自己判断通过链表翻转来统一。为什么统一方向如此重要因为整个算法依赖「有向面积为正 逆时针 多边形内部在左侧」这个约定。如果保留用户原始方向isEar的判断逻辑就得同时兼容正负两种面积符号每处判断多一个条件分支还容易在凹角判断的边界情况下出错。源码的解法是在构建链表时一次性翻转后续代码全部按逆时针假设运行所有几何判断保持单一约定。这带来一个附带好处holeIndices里每个洞的顶点方向同样不重要。earcut 在合并洞时会单独对每个洞的子链表做方向检查和翻转。调用方只需要把外环顶点坐标平铺在前面再把每个洞的顶点坐标依次接到后面最后在holeIndices数组里说明每个洞从哪个顶点序号开始就完成了全部输入。我实际用过之后最大的感受是这接口把「用户手绘多边形必然方向混乱」这一现实问题完全消化在了算法内部。4.2 带孔多边形holeIndices 的语义与桥接策略带洞多边形的三角化有个本质难点不能把洞的顶点直接参与耳切否则会切出跨越洞区域的非法三角形。earcut 的策略是「桥接」——从外环上找合适顶点与洞边界上最近的可视顶点连成一条桥边把外环和洞合并成一条「假外环」再对合并后的环做耳切。// 把单个洞合并进外环链表 function eliminateHole(data, holeIndices, outerNode, dim) { // hole 是该洞子链表的起点 // Step 1: 计算洞的有向面积翻转成与外环同方向 // Step 2: 遍历外环所有顶点与洞顶点找距离平方最小的配对 // 再用 intersects 检查连线是否穿过任何边界线段 // 穿过了就不可见换下一对候选 // Step 3: 连接 bridgeStart 和 bridgeEnd把洞链表插入外环链表 // Step 4: 对桥接处两个局部区域做点包含预检避免无效耳朵 }几个关键点展开桥接点的搜索是 O(外环顶点数 × 洞顶点数) 的线性扫描源码里做了一个务实取舍——洞顶点数少时不用 Z 序索引直接双重循环反而更快因为索引本身的构建开销超过了暴力遍历的开销。可视线段的判断是「防翻车」核心。如果选中的桥接线与洞边界相交合并后的链表会出现自交耳切法在自交输入上会输出错误三角形。intersects函数用经典的方向异号法判断线段相交处理共线情况时额外加了容差。多个洞时循环执行eliminateHole每次合并一个洞新的链表顶点数增大再对下一个洞做可见性搜索。洞的顺序不影响正确性但洞之间的空间分布会影响性能——相邻洞的桥接距离短搜索收敛快。如果holeIndices传错单位合并时链表会从错误位置切开生产环境里常见的表现是三角化结果不报错但渲染出来有三角形跨越孔洞区域或者出现诡异的翻面三角形。这类问题特征明显但定位费眼力因为索引换算在函数内部外层拿到的triangles数组看起来完全正常。我现在的调试习惯是带洞多边形先去掉holes参数确认外环单独三角化正确再逐个加洞定位。4.3 从索引到顶点拿到 triangles 之后怎么用triangles数组里存的是顶点序号不是坐标本身。渲染前要做一步映射// vertices 是原始扁平坐标数组triangles 是 earcut 返回值 const positions []; for (let i 0; i triangles.length; i) { const vertexIndex triangles[i]; // 第 i 个索引 positions.push(vertices[vertexIndex * 2]); // x 坐标 positions.push(vertices[vertexIndex * 2 1]); // y 坐标 } // positions 每两个一组交给 WebGL 的 bufferData 即可逻辑说明triangles数组长度是 3 的倍数每组三个索引构成一个三角形。索引按照「输入数组中的原始顶点顺序」编号不是按链表顺序——earcut 内部用Node.i记录原始数组序号算法全程带着这个原始编号所以「输出索引精确对应输入数组位置」这一保证是稳定的前提是两块代码之间不修改输入数组。还有一个经验判断如果triangles.length / 3不等于「(外环顶点数 洞顶点数 - 2)」输入一定有问题。任何简单多边形的三角形总数都满足n - 2这个公式。这个公式可以直接写成单元测试断言每次改代码之后跑一遍比肉眼盯着渲染结果高效得多。5. 跑通与避坑从解压到稳定输出的实战记录5.1 快速跑通最小调用示例这个资源包不需要构建没有 npm install 的必要——直接从src/earcut.js读取模块即可。先用 Node 跑一遍内置测试集node test/run.js正常情况下应该看到每个 fixture 的输出与预期索引数组一致最后打印「全部通过」。如果某个 fixture 断言失败优先检查fixtures.js里数据是否被意外修改过。在自己的项目里使用最基本的调用是// CommonJS 引入 const earcut require(./src/earcut); // 一个正方形四个顶点坐标平铺 const vertices [ 0, 0, 100, 0, 100, 100, 0, 100 ]; const triangles earcut(vertices, null, 2); console.log(triangles); // [0, 1, 2, 0, 2, 3]输出[0, 1, 2, 0, 2, 3]表示两个三角形第一个由顶点 0、1、2 构成第二个由顶点 0、2、3 构成。正方形没有洞holeIndices直接传null。浏览器端同样简单demo/index.html里用script typemodule引入main.jsmain.js内import earcut from ../src/earcut.js。整个模块是纯函数实现没有任何 DOM 依赖因此浏览器环境直接可用。要在自己的打包工程里接入加一行 import 就行不需要任何 polyfill 或配置项。5.2 避坑实录五个高频翻车现场下面五条是实际跑这套代码时踩过的坑每条按「现象 → 原因 → 解决」记录。第一条首尾顶点重复导致三角形退化。现象正方形传了 5 个顶点输出triangles里某个三角形面积为 0渲染时出现黑线或区域不连续。原因输入[0,0, 100,0, 100,100, 0,100, 0,0]最后一个点和第一个点重合。链表构建过程保留了首尾两个相同坐标节点耳点判定选出的三角形包含零面积边。解决调用前过滤掉与上一个顶点坐标完全相同的连续重复点。earcut 内部也会做一次equals检查但它只清理链表层相邻节点的重复数组层面的重复要靠上层过滤。第二条洞索引单位传错三角化结果「看起来正常」。现象带一个洞的凹多边形渲染时三角形跨越洞区域但没有任何报错。原因holeIndices传成了坐标分量偏移。外环有 5 个顶点共 10 个数洞从第 6 个顶点开始正确值是 5错传成 10 之后链表从坐标中间位置切开。解决约定所有调用处统一用「顶点序号」单位传holeIndices不在函数内部做单位换算。给调用处加一个注释写清楚「第几号顶点开始是洞」。第三条自相交多边形的结果无法预期。现象一个「蝴蝶结」形状四点 8 字形三角化结果有些三角形方向反转面积出现负值。原因耳切法要求输入是简单多边形。自交多边形的「内外」定义本身有歧义有向面积在整个边界上符号不稳定isEar的凸角判断随之失真输出结果不满足任何拓扑约定。解决上层接入前先做自相交检测。如果项目里已有几何库可以先做「交点拆分」把自交多边形拆成多个简单多边形再分别三角化。如果不想引入额外依赖至少要在接口文档里醒目标注「输入必须为简单多边形」。第四条浮点精度导致耳点误判。现象对某个城市行政区边界做三角化结果出现「裂缝」相邻三角形的公共边在视觉上缺了一小块。原因坐标值较大时比如经纬度乘以 1e6pointInTriangle内叉积计算的中间结果超出安全整数范围浮点误差导致点包含判断翻转。解决尽量在投影坐标系下作业把坐标归一化到小数位较少的范围或者在调用前对坐标做一次等比缩放让最大坐标落在 1e4 量级以内。earcut 内部没做误差补偿计算所以这层保护必须放在调用端。这类误差型 Bug 只在特定坐标值上触发复现困难我的做法是在测试 fixtures 里混入「真实经纬度放大后的数据」而不是只用整数坐标。第五条大数据量多边形性能骤降。现象顶点数从几百涨到几千三角化时间从毫秒级跳到数百毫秒页面肉眼可见卡顿。原因耳切法最坏 O(n²)Z 序优化在顶点分布极不均匀大量顶点挤在小范围时退化为较慢的线性扫描点包含判定的候选集变大。解决先确认边界数据是否真的需要几千个顶点——很多高精度边界可以先做抽稀到百级别视觉差异极小性能差异巨大。如果确实需要精细三角化把多边形分层切块切成多个子多边形分别三角化再合并索引。earcut 是同步计算浏览器端过大的计算量会阻塞主线程必要时把整套调用丢进 Web Worker。6. 二次开发给耳切法加三个实用的扩展能力核心链路跑通、绕开上面那些坑之后这套代码就到了可以按需改造的阶段。我提供三个扩展方向按投入产出比排序。第一个方向是数据层改造把普通数组换成 TypedArray。earcut 内部大量使用push和索引访问对 JavaScript 引擎来说浮点数组的push有装箱开销。如果要在 3D 场景里处理几十个多边形、每秒更新一次建议把接口调整为接受Float64Array顶点和Uint32Array返回值主循环里改用索引赋值而不是push。这个改动不大收益在顶点数过千时能被 Profile 工具明显测出来而且 TypedArray 可以直接进 WebGL Buffer。第二个方向是增量三角化支持多边形顶点的动态增删。核心思路是在节点结构里增加一个dirty标记每次 push 新顶点时局部重切附近区域而不是全量重跑earcutLinked。实现时有一个技巧在链表中保留上一次剪切结束的stop节点新顶点只影响它所在环的局部耳点判定利用 Z 序定位受影响区间。这样做大约需要额外 100 行代码但可以有效支撑「拖拽顶点实时预览三角化结果」这类交互场景。第三个方向是三角形质量约束耳切法经常会产出极细长的退化三角形在光照计算和碰撞检测里会引起精度问题。可以在isEar判定通过后额外检查生成的三角形最小角度是否低于阈值比如 15 度如果过低则加入 Steiner 点——在最长边中点插入新顶点再局部重切。earcut 源码里已经预留了steiner标记位Node 构造器里那个字段说明原作者本来就考虑过这个扩展路径照着加不会跟现有结构冲突。验证每次改造我都会做两件事一是把改造前后对同一组 fixtures 生成的triangles数组做拓扑相等判断——顶点索引可能不同但三角形集合覆盖的区域必须一致二是渲染到 Canvas 上肉眼对比因为有些拓扑相等但翻转方向的错误是纯几何断言抓不到的。从那以后我每次改这类几何算法都强制走一遍「fixtures 全量断言 浏览器渲染目检」的双保险流程再也不敢只跑一个正方形用例就 commit。希望这些拆解和改造思路对你有帮助。本文还有配套的精品资源点击获取