简介一套基于改进耳切法EarCut的多边形三角化工具库源码包面向GIS数据处理与桌面或Web图形开发场景中需要输入无序顶点、输出三角形索引的开发者。算法采用z阶曲线散列优化能够处理带孔洞、扭曲、退化与自相交等复杂多边形设计思路借鉴FIST和David Eberly提出的经典耳切法既可用于工程项目落地也适合算法原理学习。压缩包共33个文件以C/C头文件与源文件为主体配有Visual Studio解决方案和工程配置、Mapbox风格的earcut.hpp核心实现、libtess2三角化对比程序以及顶点坐标、三角形索引等多组CSV样例数据整体大小约4.29MB。已有454人学习下载。读者解压后可直接编译运行对照ReadMe快速验证从无序顶点到三角面片索引的完整流程并可比较耳切法与libtess2在不同数据下的表现便于迁移、二次开发或整合进地图、建模相关项目。1. 无序点集三角化这个项目解决的第一类痛点是“顶点索引”做地图围栏、室内定位、餐厅选址覆盖分析这类需求时手里是一堆散乱坐标点想算覆盖面积、画网格、给渲染管线喂数据第一件事就是把多边形切成三角形。手写三角剖分容易在凹多边形和孔洞上翻车输出还往往只有坐标没有索引。Earcut-Triangulation.zip 就是这个问题的最直接答案核心采用耳切法EarCut用一份带回注释的算法源码、一个网页演示、一条命令行转换链路把无序顶点变成「三角形顶点索引」。新手可以点开演示页看效果熟手则可以直接把 earct-readable.js 抽出来接进自己的 GIS 或图形项目。2. 项目拆解一个演示页、一个核心算法、一个预处理器的分工2.1 目录结构压缩包里的几个文件各守一道关卡拿到压缩包后先别急着跑把文件铺开看一遍。这个包的结构很干净没有工程脚手架也没有 node_modules核心就三个 JS 文件和一个演示页文件角色关键行为index.html交互演示画布点选顶点、拖拽调整、实时三角化预览导出索引 JSONsrc/earcut-readable.js核心算法带注释版耳切法完整实现供阅读和二次开发src/earcut.js压缩生产版去掉注释和空行体积更小可直接引入业务src/converter.js无序点集预处理把散点重排成环再交给 earcut 解析cli.jsNode 命令入口读入点集 JSON 文件输出三角形索引 JSONexamples/商圈围栏.json示例数据一组带凹多边形和孔洞的坐标点集整条数据链路是固定的用户或脚本拿到点集 → converter.js 把散点整理成带顺序的环 → earcut 把环切成三角形 → 返回索引数组 → Canvas 画出来或脚本写回文件。这里值得注意的一点是earcut 本身只负责「按环切三角」不负责「把乱序点云还原成环」。所以 converter.js 这个预处理器正是这个项目比裸算法更好上手的原因。2.2 输入输出约定平铺坐标数组和三角形索引earcut 的接口签名很简短核心函数就一个/** * 对多边形顶点做耳切法三角化 * param {Arraynumber} data 顶点坐标平铺数组 [x0,y0, x1,y1, ...] * param {Arraynumber} holeIndices 孔洞起始顶点索引列表无孔洞传 null * param {number} dim 每个顶点的分量数默认 23D 投影场景可传 3 * returns {Arraynumber} 三角形顶点索引 [a0,b0,c0, a1,b1,c1, ...] */ function earcut(data, holeIndices, dim) { // ... }这里最容易误解的是 data 的形态。它不是[{x: 0, y: 0}, ...]这种对象数组而是一维平铺数组。比如一个正方形四个顶点按逆时针排列传入的 data 是[0, 0, 10, 0, 10, 10, 0, 10]。这样设计是为了减少对象开销也方便直接对接 WebGL 的 typed array。返回的 triangles 数组每三个数构成一个三角形里面的数字不是坐标而是顶点在 data 中的索引位次。比如[0, 1, 2, 0, 2, 3]表示两个三角形第 0、1、2 号顶点组成一个第 0、2、3 号顶点组成另一个。如果多边形带孔洞比如一个城市地块中间有个湖外环顶点和湖的顶点会全部平铺在 data 里holeIndices则用来告诉算法「外环结束、湖开始」的顶点位置。注意方向约定外环建议逆时针内环顺时针这个项目在 converter.js 里做了强制矫正不依赖调用方自觉。2.3 可视化与导出为什么三角化必须能「看见」三角化算法最怕的不是慢是静默出错。顶点顺序反了、孔洞方向错了、自相交多边形被硬切结果在数据上看都是「能算完」但你没法确定对不对。这个项目用 Canvas 做了实时预览把抽象索引变成肉眼可见的三角形网格。function drawTriangles(ctx, data, triangles) { ctx.fillStyle rgba(80, 140, 220, 0.35); ctx.strokeStyle #333; ctx.lineWidth 1; for (let i 0; i triangles.length; i 3) { const a triangles[i], b triangles[i 1], c triangles[i 2]; ctx.beginPath(); ctx.moveTo(data[a * 2], data[a * 2 1]); ctx.lineTo(data[b * 2], data[b * 2 1]); ctx.lineTo(data[c * 2], data[c * 2 1]); ctx.closePath(); ctx.fill(); ctx.stroke(); } }这段代码的核心不是绘图本身而是data[a * 2]这种取坐标方式索引数组和坐标数组通过乘法建立映射正好对应 earcut 返回索引而不是坐标的设计。演示页里你还可以用鼠标拖拽任意顶点三角形会实时重算拖到某个极端位置时能直观看到「耳朵」被割掉的过程。页面右侧控制台会同步打印每个三角形的索引导出按钮会把{ points, triangles }打包成 JSON 下载。这个 JSON 可以直接喂给 WebGL 的ELEMENT_ARRAY_BUFFER也可以交给某个 GIS 平台做面数据重建。项目的实用路径基本就是这样先在演示页里看效果确认无误后再把同一份索引数据落到业务里。3. 耳切法核心实现从有序环到三角形索引的三步落码3.1 第一步把一维坐标数组加工成双向链表耳切法在实现层面有个特点它要频繁判断某个顶点和前后相邻点的几何关系还要在「割掉一只耳朵」后立刻删除该顶点并继续遍历。用数组来做删除操作的时间复杂度是 O(n)但用双向链表删除节点是 O(1)。所以带注释版源码里第一步就是把 earcut 入口收到的平铺数组整理成一个双向链表。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, last); } } else { for (let i end - dim; i start; i - dim) { last insertNode(i, last); } } // 首尾点重合时移除重复节点防止除零 if (last equals(last, last.next)) { removeNode(last); last last.next; } return last; }signedArea是这里的哨兵角色它计算的是多边形的有向面积正值表示逆时针负值表示顺时针。clockwise参数是调用方预设的方向要求两者异号时说明环方向不对算法会反着遍历数组用倒序插入的方式把链表修正过来。这一步做完之后后续的所有操作都不用再关心原始数组只需要在链表节点间游走。节点本身的结构也值得看一眼每个节点存的是顶点在 data 里的起始位置i以及prev和next两个指针。用i而不是坐标值存节点是为了最后输出索引时能直接拿到node.i / dim不需要反向查找。这是整个算法里第一个「索引优先」的设计决策。3.2 第二步耳朵判定用叉积找凸顶点用点在三角形内排除凹角耳切法的核心循环只有一个动作找到一个「耳朵」割掉继续找下一个耳朵。一个顶点要被判为耳朵需要满足两个条件它是凸顶点且它与前后两个邻居组成的三角形内部不包含其他任何顶点。function isEar(ear) { const a ear.prev, b ear, c ear.next; // 叉积 0 表示该顶点是凹角或共线不可能是凸耳朵 if (area(a, b, c) 0) return false; // 检查是否有其他顶点落入三角形 abc 内部 let p ear.next.next; while (p ! ear.prev) { if (pointInTriangle(a, b, c, p) area(p.prev, p, p.next) 0) { return false; } p p.next; } return true; }area函数计算的是三个顶点的叉积值(b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])。叉积为正时三个点是逆时针排列对这个算法而言它代表该顶点处内角小于 180 度也就是凸。叉积为负则是凹角凹角不可能成为耳朵直接跳过。等于 0 是共线情况也跳过避免切出零面积三角形。内点判断pointInTriangle用的是重心坐标法判断p是否落在a b c包围盒内。这里有一处容易忽略的细节即使p落在了三角形内只要p本身不是凸顶点也不会否决当前耳朵。这是 Earcut 相对早期耳切算法的优化点可以让凹顶点区域的相邻顶点更早被切除减少失败回溯。3.3 第三步主循环、输出索引、兜底分割主循环的结构比想象中短关键逻辑就十几行function earcutLinked(ear, triangles, dim) { let stop ear; while (ear.prev ! ear.next) { const prev ear.prev; const next ear.next; if (isEar(ear)) { // 找到耳朵输出三个顶点的索引 triangles.push(prev.i / dim, ear.i / dim, next.i / dim); removeNode(ear); // 割掉耳朵 ear next.next; // 跳到被割耳朵的后一个顶点继续 stop ear; continue; } ear ear.next; // 转了一圈都没找到耳朵说明多边形退化或自交了 if (ear stop) { splitEar(ear, triangles, dim); // 兜底分割 break; } } }这个循环的巧妙之处在于stop指针。正常情况下每轮循环至少能找到一个耳朵割掉后链表长度减一循环继续。但如果多边形发生了退化比如所有点共线、自相交、重复点连续完整三圈都找不到合法耳朵就会进入splitEar兜底逻辑强制从当前点连一条对角线把多边形切成两个子多边形递归处理避免死循环。观察triangles.push的内容会发现输出的是prev.i / dim而不是i本身。因为节点里存的i是原始平铺数组的下标当dim为 2 时要把下标除以 2 才得到「第几个顶点」。举例如果 data 是[0,0, 10,0, 10,10, 0,10]第一个顶点在数组里的位置是 0第二个顶点是 2第三个是 4所以i / dim后得到 0、1、2。这套换算关系贯穿整个源码改dim 3处理三维坐标时尤其要小心索引算错一位三角形就会扭曲。4. 避坑记录耳切法生产环境的五个翻车现场4.1 顶点顺序反了三角网被剔除到看不见有一次在某个室内定位 Demo 里我拿到的 GIS 面数据外环顶点是顺时针的。earcut 算法内部会自动修正绕序输出的三角形法线方向也统一朝外但 Canvas 预览时却黑屏一片三角形像被「吃掉」了。原因渲染环节开启了背面剔除浏览器默认按顺时针/逆时针判断法线朝向而我的三角形恰好是顺时针绕序被当成背面全部剔掉。解决预览绘制时不开启剔除如果接入 WebGL则把绘制顺序从逆时针翻成顺时针或者在 shader 侧关闭CULL_FACE。最省事的办法是强制外环逆时针可以用signedArea判断方向为负时把数组反转一次if (signedArea(data, start, end, 2) 0) { for (let i start, j end - 2; i j; i 2, j - 2) { const tx data[i], ty data[i 1]; data[i] data[j]; data[i 1] data[j 1]; data[j] tx; data[j 1] ty; } }4.2 自相交多边形三角网碎成一堆破面多边形两条边交叉在中间打了一个 Xearcut 不会报错而是正常返回一堆三角形但三角形之间互相重叠面积计算也完全不对。原因耳切法基于「简单多边形」假设。所谓简单多边形是边与边只在端点相交。一旦自相交顶点顺序和无向面积的语义就崩了算法把交叉区域当成可分割空间产生了碎面。解决在喂给 earcut 之前先做自交检测。常见做法是把每条边与除相邻边之外的所有边做线段相交判断O(n²) 复杂度对几百个顶点完全够用。发现相交就把多边形沿交点切分成两个独立子多边形分别三角化再合并索引。4.3 孔洞方向写错湖被当成陆地填上在地块加载器里外环是地块边界内环是中间的湖。结果三角化之后湖的位置也被三角形填满整个面变成一个实心多边形。原因holeIndices传了但内环顶点方向和外环方向一致。earcut 依赖方向和孔洞索引的组合来判断内外一旦方向错误内环会被当成另一个外环的子环三角化后自然把孔填平。解决在 converter.js 入口强制处理外环逆时针、内环顺时针两者方向必须相反。检验方法很简单分别对外环和每个内环跑一次signedArea符号不符合就反转对应区间的数组元素。4.4 无序点集直接喂给 earcut三角形变成蜘蛛网这是我最初最常踩的坑也正好对应项目关键词里的「无序顶点」。把几十个散点直接平铺进 dataearcut 把它当成一条环来切结果三角形的边乱成一团蛛网。原因earcut 依赖「环」的顺序来推断顶点之间的相邻关系。散点没有环结构算法读到的是一条首尾乱接的折线切出来的三角形自然全错。解决先用 converter.js 做最近邻重排。具体做法是从第一个点出发每次找离当前点最近的未访问点依次连接成一条闭合环。注意这只对边界整体呈凹度不大的点集有效凹入太深或有多个岛屿时最近邻可能会把不该连的边连上。这种场景下更稳的做法是先生成点集的凸包作为外环再做凹陷分割。4.5 大坐标导致浮点精度失控河道边线出现锯齿处理真实 GIS 坐标时坐标动辄几十万米叉积值会变得非常巨大float 精度在小数点后几位开始抖动三角形面积出现微小但刺眼的异常。原因叉积(b - a) x (c - a)是两个坐标差的乘积。坐标值越大浮点尾数表示的有效精度越低小三角形几乎被噪声吞掉。解决三角化前把整个点集平移到以质心为原点的坐标系里算完索引再平移回真实坐标。因为 earcut 返回的是索引平移操作只影响数据喂入不影响输出。这个处理几乎零成本是所有 GIS 场景接入耳切法的必备前置步骤后续第六章我会展开写这个改造。5. 跑通与验证浏览器预览、Node 批处理与面积核对5.1 浏览器预览双击 index.html 就能出图这个项目真正的零门槛体验是用浏览器直接打开 index.html不需要 npm install不需要构建工具。页面打开后左侧是一块画布右侧是顶点列表和三角形索引输出。你可以在画布上按「逆时针」依次点击若干个点每点一个点三角网就实时更新一次。内置的两组示例数据可以一键载入一组是带凹槽的商圈围栏另一组是带孔洞的地块。载入后你还能用鼠标拖拽任意顶点看局部移动时周围三角形如何重排。这一步建议花十分钟做的事情是刻意把某个顶点拖到凹进去很深的位置观察它两侧的三角形如何向外翻转再往多边形内部加一个点看它是否会成为「孤岛」。这些操作能帮你快速建立对耳切法行为模式的直觉它永远切凸角凹角会被留到最后。5.2 Node 命令行批处理把多个点集转成索引文件演示页做的是交互验证实际业务里更多是「批量计算」。项目里的 cli.js 就是干这个的用法很简单node cli.js examples/商圈围栏.jsoncli.js 内部做的事情可以归纳为三步读 JSON、调 converter 和 earcut、写输出文件。核心代码是这样const fs require(fs); // 输入文件路径source.json const source JSON.parse(fs.readFileSync(process.argv[2], utf8)); const { pointsToRing } require(./src/converter); const { earcut } require(./src/earcut-readable); // 1. 无序点集先重排成环 const ring pointsToRing(source.points); // 2. 平铺成 [x0,y0, x1,y1, ...] const flat []; for (const p of ring) { flat.push(p[0], p[1]); } // 3. 三角化并输出索引 const triangles earcut(flat, null, 2); console.log(JSON.stringify({ vertexCount: ring.length, triangleCount: triangles.length / 3, triangles }, null, 2));使用时把任意点集 JSON 按{ points: [[x, y], ...] }的格式准备好命令行跑完后会看到三角形数量和索引数组。因为输入是「无序点集」所以在喂给 earcut 前必须先经过pointsToRing这一步也是直连第 4 章避坑点 4.4 的正确姿势。5.3 验收自检面积核对法验证索引没乱拿到 triangles 之后怎么确定它是对的最直接的办法是「面积守恒」把三角形索引还原成坐标累加所有三角形面积然后和原始多边形面积对比数值应该完全一致。function verifyArea(flat, triangles) { let total 0; for (let i 0; i triangles.length; i 3) { const a triangles[i] * 2; const b triangles[i 1] * 2; const c triangles[i 2] * 2; const ax flat[a], ay flat[a 1]; const bx flat[b], by flat[b 1]; const cx flat[c], cy flat[c 1]; // 叉积求三角形面积 total Math.abs((bx - ax) * (cy - ay) - (cx - ax) * (by - ay)) / 2; } return total; }把verifyArea的结果和signedArea算出的多边形面积对比误差应在 1e-6 量级。超过这个量级多半是某个三角形索引越界或者取错了坐标位。这个验收方法在餐厅选址、区域面积统计这类场景里特别重要业务方要的是「覆盖面积」三角化只是中间产物如果最后面积对不上后续所有分析都会失真。所以每批索引导出之后我都会强制跑一遍面积核对再交付给下游。6. 二次开发把 Earcut 接进 GIS 坐标管线的小技巧6.1 先做「平移归一化」再喂给 Earcut如果你的坐标是从地图平台拿到的经纬度或者投影坐标数值通常非常大。比如某个城市的一个地块中心点可能在[3400000, 5100000]这样的量级。把这样的坐标直接丢给 earcut浮点精度会损失三角形面积在小数点后几位开始抖。一个很小的封装就能解决class TriangulationPipeline { center [0, 0]; run(rawPoints) { // 1. 平移到原点附近 let sumX 0, sumY 0; for (const p of rawPoints) { sumX p[0]; sumY p[1]; } this.center [sumX / rawPoints.length, sumY / rawPoints.length]; const shifted rawPoints.map(p [p[0] - this.center[0], p[1] - this.center[1]] ); // 2. 环顺序整理 三角化 const flat shifted.flat(); const ring pointsToRing(shifted.map((p, i) p, 2)); const triangles earcut(flat, null, 2); // 3. 返回索引调用方再按需把坐标平移回原值 return { triangles, center: this.center }; } }关键点在于earcut的输出是「索引」而不是坐标所以平移只影响输入不影响返回结果。下游渲染时用flat[triangles[i] * 2] center[0]就能还原真实坐标。这个封装几乎零成本却能把地图数据导致的精度问题一次性挡住。我一般会把这种「数据预处理 算法调用 结果自检」三段式结构固化成自己的工具函数。从那以后每次接到新的三角化需求我都会先问自己三句话顶点有环吗有自交吗坐标量级有多大这三个问题问完用不用 earcut、要不要前置处理基本就有答案了。希望帮到你。本文还有配套的精品资源点击获取