简介这份资源面向从事地理信息、图形渲染或几何计算的开发者提供基于耳切法Ear Clipping的多边形三角化实现可将无序顶点转换为三角面片顶点索引。代码在经典耳切算法基础上引入z阶曲线散列优化并针对孔洞、扭曲多边形、退化及自相交等实际数据做了容错扩展适合处理地图道路区域等地理形状。压缩包共33个文件、约4.29MB以C/C源码为主体10个.h与4个.hpp头文件承载核心算法与接口7个.c与2个.cpp实现三角化逻辑另有csv数据文件用于输入顶点与输出索引的对照验证并附Visual Studio解决方案与工程配置便于直接编译调试。资源还包含与libtess2的对比实现方便评估三角化效果与性能差异。目前已有454人学习下载适合需要理解耳切法原理、获取可复用三角化代码或进行几何算法对照实验的读者参考。1. 耳切法三角化把无序顶点变成可渲染索引的实战拆解手里有一堆散乱的二维顶点顺序是乱的还带孔洞想直接丢进渲染管线或者导出成网格文件第一步就卡住了——顶点之间谁连谁不知道三角形索引一个都生成不出来。Earcut-Triangulation.zip解决的就是这个环节它把耳切法Ear Clipping的完整实现打包好输入一串无序或半有序的顶点坐标输出三角形顶点索引数组直接能喂给 WebGL、Canvas 或者导出成 OBJ。关键词里的「三角化」「耳切法」「无序顶点」「获取顶点索引」四个词正好对应它的输入输出链路。适合做图形前端、GIS 多边形渲染、切片轮廓处理以及任何需要把多边形拆成三角形的从业者。下面按「它怎么算 → 怎么跑 → 参数怎么调 → 哪里会翻车」的顺序拆。2. 耳切法的判定逻辑为什么它敢处理凹多边形耳切法不是玄学它的核心是一句几何判定一个顶点如果和它相邻的两个顶点构成的三角形完全落在多边形内部且不包含其他顶点这个顶点就叫「耳尖」剪掉它多边形少一个顶点重复直到只剩三个点。整个过程像剥洋葱一层层把耳朵剪下来剪的顺序就是三角形索引的生成顺序。理解这套判定后面调参数和排查失败才有依据。2.1 耳尖判定的三个条件判定一个顶点v[i]是不是耳尖要同时满足三件事。第一它必须是凸顶点也就是由v[i-1]、v[i]、v[i1]构成的转向与多边形整体绕向一致第二这个三角形内部不能落进任何其他顶点第三剪掉之后剩余多边形不能自交。前两条是几何计算第三条是拓扑约束很多实现只做前两条遇到退化输入就会产出错误索引。绕向判断用叉积二维下就是def cross(o, a, b): # 二维叉积0 表示逆时针0 表示顺时针 return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) def is_convex(prev, curr, nxt, ccwTrue): c cross(prev, curr, nxt) # ccw 为 True 时要求叉积为正否则为负 return c 0 if ccw else c 0cross返回值的符号决定转向is_convex把绕向作为参数传进去是因为同一份顶点数据可能来自不同坐标系绕向不统一。这里最容易翻车的是浮点误差当三个点几乎共线时叉积接近 0符号不稳定耳尖判定会随机跳变。常见做法是给叉积加一个极小阈值比如1e-9低于阈值直接当作共线处理跳过该顶点。2.2 点是否在三角形内重心坐标比射线法更稳第二条件「三角形内不含其他顶点」需要做点包含测试。射线法在边界点上容易误判耳切法里更常用重心坐标或者同向叉积法。同向叉积的思路是待测点p相对于三角形三条边的叉积符号必须和三角形顶点顺序一致。def point_in_triangle(p, a, b, c): d1 cross(a, b, p) d2 cross(b, c, p) d3 cross(c, a, p) has_neg (d1 0) or (d2 0) or (d3 0) has_pos (d1 0) or (d2 0) or (d3 0) # 三个叉积同号或含零才在三角形内 return not (has_neg and has_pos)has_neg和has_pos同时为真说明点落在三角形外否则在内或边界上。边界情况要特别小心如果待测点恰好落在耳尖三角形的边上严格判定会把它算作「在内」导致这个耳尖被误判为不可剪算法卡死。工程上的处理是把边界点视为「不在内」因为共线顶点本身就该在预处理阶段被清理掉。2.3 孔洞怎么接进主多边形带孔的多边形不能直接耳切得先把孔「桥接」到外轮廓上变成一条单连通的多边形链。标准做法是找孔上最右的顶点向外轮廓做一条水平射线找到最近的可见边把孔顶点和外轮廓顶点用两条重复边连起来。桥接之后孔就变成了轮廓上的一个「凹口」耳切法照常处理。这一步是整个流程里最容易出问题的地方。桥接边如果和外轮廓的其他边相交后续三角化必然产出重叠三角形。所以桥接前要先做可见性检查桥接后要验证新边不自交。很多轻量实现省掉了这步验证输入规整时看不出问题一旦孔靠近轮廓边界就翻车。2.4 复杂度与适用边界朴素耳切法是 O(n²)每剪一个耳朵都要遍历剩余顶点做包含测试。顶点数上千之后明显变慢上万的轮廓基本不能用。优化方向有两个一是用双向链表维护顶点剪耳时只更新局部邻居把单次剪耳降到 O(1) 摊还二是先做单调多边形剖分把多边形切成若干单调块再耳切整体降到 O(n log n)。Earcut-Triangulation.zip这类实现通常走的是链表优化路线够用且代码量可控。适用边界要说清楚耳切法要求输入是简单多边形不能自交不能有重复顶点孔必须完全落在外轮廓内部。自交多边形、零面积三角形、重合边这些输入耳切法不会报错它会默默产出错误索引这是它最坑的地方——失败是静默的。3. 跑通三角化从顶点数组到索引数组的完整链路拿到压缩包之后先别急着往项目里塞。第一步是确认它的输入格式约定顶点是扁平数组[x0,y0,x1,y1,...]还是点对象数组孔洞是单独数组还是用holeIndices标记起始下标。这两种约定在社区实现里都常见搞错了会得到一堆乱序索引排查半天以为是算法问题。3.1 输入数据准备与格式对齐以扁平数组加孔起始下标为例外轮廓 8 个点、一个 4 点的孔数据结构长这样// 外轮廓逆时针孔顺时针扁平存储 const vertices [ 0, 0, 10, 0, 10, 10, 0, 10, // 外轮廓 4 点 3, 3, 7, 3, 7, 7, 3, 7 // 孔 4 点 ]; // 孔从下标 8 开始第 4 个点之后 const holeIndices [8];注意绕向外轮廓逆时针、孔顺时针是通行约定反了的话桥接逻辑可能找不到正确的可见边。如果原始数据绕向不统一先跑一遍有向面积计算面积为负就反转该环的顶点顺序。function signedArea(flat, start, end) { let sum 0; for (let i start; i end; i) { const j (i 1 end) ? start : i 1; sum flat[i * 2] * flat[j * 2 1] - flat[j * 2] * flat[i * 2 1]; } return sum / 2; // 0 逆时针0 顺时针 }signedArea的start和end是顶点下标区间不是坐标下标调用时别把扁平数组的步长搞混。面积绝对值还能用来做退化检测小于阈值的环直接丢弃省得后面耳切卡死。3.2 调用三角化并校验输出对齐格式后调用主函数输出是三角形索引三元组const triangles earcut(vertices, holeIndices, 2); // 输出形如 [0,1,2, 0,2,3, ...]每三个一组 console.log(三角形数量:, triangles.length / 3);第三个参数2是维度二维固定传 2。输出索引是相对vertices扁平数组的顶点序号不是字节偏移渲染时按triangles[i] * 2取 x、triangles[i] * 2 1取 y。拿到索引后必须做一次校验别直接信。校验两件事索引范围是否都在[0, 顶点数)内以及三角形总面积是否等于多边形面积。面积对不上说明有三角形重叠或遗漏。function validate(vertices, triangles, expectedArea) { const n vertices.length / 2; let area 0; for (let i 0; i triangles.length; i 3) { const [a, b, c] [triangles[i], triangles[i1], triangles[i2]]; if (a n || b n || c n) throw new Error(索引越界); area Math.abs(cross( [vertices[a*2], vertices[a*21]], [vertices[b*2], vertices[b*21]], [vertices[c*2], vertices[c*21]] )) / 2; } // 允许 1e-6 量级的浮点误差 if (Math.abs(area - expectedArea) 1e-6) { console.warn(面积不匹配可能存在重叠三角形); } }expectedArea用 3.1 里的signedArea对每个环取绝对值累加得到。这个校验我一般会留在调试分支里上线前跑一遍能拦住大部分静默失败。3.3 参数与常见配置项不同实现的函数签名有差异但核心参数就几个列出来对照着看参数含义常见取值注意点data扁平顶点数组[x,y,...]维度必须和dim一致holeIndices孔起始顶点下标[8, 20]是顶点序号不是坐标下标dim每点维度2 或 3三维时只取前两维投影maxVertexCount顶点上限按实现超限需先简化轮廓dim传 3 时实现通常只读 x、yz 被忽略用于三维点云投影到平面后三角化。maxVertexCount不是所有实现都有但做 GIS 的一定要留意几千个点的行政边界直接耳切会明显卡顿先做道格拉斯-普克简化再三角化是常规操作。3.4 输出接渲染或导出索引拿到后接 WebGL 就是gl.drawElements(gl.TRIANGLES, triangles.length, gl.UNSIGNED_INT, 0)接 Canvas 就按三元组逐三角形moveTo/lineTo。导出 OBJ 时顶点和面分开写# OBJ 面索引从 1 开始三角化输出从 0 开始导出时统一 1 f 1 2 3 f 1 3 4这个 1 是血泪经验忘了加的话模型在部分查看器里整个面片错位看起来像三角化算法坏了其实是索引基准差一。4. 避坑与排查耳切法静默失败的五个现场耳切法最让人头疼的不是报错是它不报错。下面五条是我在实际项目里反复遇到的按「现象 → 原因 → 解决」记下来遇到对得上号的直接查。4.1 三角形数量对但渲染有空洞现象索引数组长度正常面积校验也过但渲染出来多边形中间缺一块。原因多半是孔洞桥接边选错了可见顶点桥接边穿过了外轮廓导致局部三角形绕向反转被背面剔除。解决桥接前做可见性检查桥接后对每个输出三角形算一次有向面积符号与整体绕向相反的三角形标记出来回溯到桥接边修正。4.2 顶点数超过几百后卡死现象小轮廓秒出结果上千点的轮廓浏览器直接无响应。原因是朴素 O(n²) 实现每剪一个耳朵全量扫描。解决先做轮廓简化把共线点和间距小于阈值的点合并仍不够就换链表优化的实现或者先做单调剖分。别指望调参数能救复杂度摆在那。4.3 共线顶点导致死循环现象算法跑不完CPU 占满。原因是三个连续顶点共线叉积为 0凸性判定在「是」和「否」之间摇摆耳朵永远剪不掉。解决预处理阶段清理共线点判定时给叉积加1e-9阈值共线直接跳过该顶点。这个坑在 CAD 导出的轮廓数据里特别常见因为导出时经常保留冗余共线点。4.4 孔洞完全落在轮廓外现象输出三角形覆盖了孔以外的区域孔没被挖掉。原因是输入数据本身有问题孔环的顶点落在外轮廓之外桥接时找不到合法可见边实现退化成忽略孔。解决三角化前做一次包含测试孔的每个顶点必须在外轮廓内不满足直接拒绝输入并报错别让算法自己猜。4.5 浮点坐标下面积校验偶尔失败现象同一份数据面积校验有时过有时不过。原因是坐标量级大时浮点精度不够叉积累加误差放大。解决三角化前把坐标平移到原点附近减去包围盒中心缩小数值量级校验阈值按坐标范围动态调整别写死1e-6。提示这五条里4.1 和 4.3 占了实际排查量的大头遇到诡异结果先查这两处。5. 进阶用面积守恒做回归验证把静默失败挡在提交前耳切法这类几何算法单元测试写「输出长度对不对」意义不大长度对了内容可能是错的。真正管用的是面积守恒三角化输出的三角形面积之和必须等于输入多边形外轮廓减孔洞的面积。这个断言对重叠、遗漏、绕向反转全都敏感是我验证三角化实现的第一道闸。具体做法是把它做成一个可复用的校验函数输入原始顶点、孔下标和输出索引返回布尔值和误差值function areaConservation(vertices, holeIndices, triangles, dim 2) { // 输入多边形净面积外轮廓面积减去各孔面积 const ringStarts [0, ...holeIndices]; const ringEnds [...holeIndices, vertices.length / dim]; let netArea 0; for (let r 0; r ringStarts.length; r) { const a Math.abs(signedArea(vertices, ringStarts[r], ringEnds[r])); netArea (r 0 ? a : -a); // 第一个环是外轮廓其余是孔 } // 输出三角形面积累加 let triArea 0; for (let i 0; i triangles.length; i 3) { const p (k) [vertices[triangles[ik]*dim], vertices[triangles[ik]*dim1]]; triArea Math.abs(cross(p(0), p(1), p(2))) / 2; } const err Math.abs(netArea - triArea); return { ok: err 1e-6 * Math.max(1, netArea), err }; }signedArea复用第 3 章的版本netArea的符号处理是关键外轮廓取正、孔取负这样带孔多边形的净面积才是对的。误差阈值用1e-6 * max(1, netArea)做相对判断避免大坐标下绝对阈值失效。回归测试的写法是把一批已知正确的输入输出对存成 fixture每次改实现都跑一遍面积守恒。我一般会准备三类样本纯凸多边形最简单先保证基础路径通、带一个孔的凹多边形覆盖桥接逻辑、带多个孔且孔靠近边界的多边形覆盖可见性边界。第三类最容易暴露问题建议必测。还有一个容易被忽略的点三角化结果的顶点索引顺序会影响后续法线计算。如果下游要做光照三角形绕向必须统一面积守恒校验通过不代表绕向一致。补一个绕向检查对每个输出三角形算有向面积统计正负号出现混合符号就说明桥接或剪耳过程中绕向被打乱了得回去查桥接边的方向。从那以后我每次接入新的三角化实现都强制先跑面积守恒加绕向一致性这两道校验再谈性能优化。几何算法的静默失败太隐蔽等渲染出来才发现问题回溯成本翻好几倍。希望这套校验思路能帮到你少走几段弯路。本文还有配套的精品资源点击获取