简介这是一份基于耳切法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[i1]判断这三个点组成的三角形是否满足两个条件——一是中间点相对于多边形是凸的二是该三角形内部不包含多边形其他任何顶点。满足条件就称 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_i1) - (x_i1 * y_i))遍历一个环的所有顶点得到的结果是正数说明环为逆时针负数说明环为顺时针绝对值等于环面积。Earcut 内部用这个公式完成三件事判断外环与孔洞的面积量级、给孔洞配对到正确的外环、在必要时反转孔洞顶点的遍历方向。对外表现上最重要的设计是它不修改你传入的顶点数组而是返回“顶点索引”。每个索引都是原数组的下标从 0 开始计数。这意味着你把顶点 Upload 到 GPU 顶点缓冲后只需要替换索引缓冲不需要重排顶点坐标。图形渲染里最耗带宽的操作之一就是顶点重排Earcut 把这个开销直接省掉了。2.3 选型对比为什么先试 Earcut 而不是 Delaunay方案主要优势主要限制适用场景Delaunay 三角化三角形最小角最大化剖分质量均匀不保证三角形边贴合多边形凹边界地形网格、点云构网通用 tessellator功能全支持复杂输入与容错初始化重API 陈旧跨平台成本高桌面图形系统内部Earcut 耳切法轻量、无依赖、严格沿边界切分输入需为简单多边形不自相交修复地图、CAD、UI 裁剪、碰撞体生成耳切法一个容易被低估的优势是“边界锁定”。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*21] - p[a*21]) - (p[b*21] - p[a*21]) * (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[i1], indices[i2]) ); } // 与多边形总面积比较容差建议在 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 接入新模块我都会强制走一遍面积守恒、三角形数量约束、描边可视这三道检查。看似多花几分钟实际省掉的是在集成阶段反复排查多边形漏洞的时间。希望帮到你。本文还有配套的精品资源点击获取