简介：这份资源围绕耳切法（EarCut）三角化展开，面向从事地理形状处理、图形渲染或几何算法实现的开发者，尤其是需要将无序顶点转换为三角面片索引的工程场景。包内以C/C++源码为主体，含10个h头文件、7个c源文件及4个hpp、2个cpp实现文件，另有4个csv数据文件用于存放顶点与索引样例，配合txt说明、sln与vcxproj工程文件，可直接在Visual Studio中编译调试，压缩包约4.29MB，共33个文件。算法在经典耳切基础上引入z阶曲线散列优化，并针对孔洞、扭曲多边形、退化与自相交等情形做了扩展处理，虽不保证严格正确的三角剖分，但对地图道路面等实用数据较为友好。资源还附带libtess2对照实现与测试数据，便于比较不同三角化方案的输出差异。已有454人学习，适合想理解耳切法原理、获取顶点索引并快速验证效果的读者参考。

1. 耳切法三角化：为什么一堆无序顶点能变成合法的三角形索引

拿到一组多边形顶点，顺序是乱的，没有拓扑关系，只有坐标。你想把它喂给渲染管线，管线只认三角形。这中间缺的那一步，就是三角化。耳切法（Ear Clipping）是这件事最经典、最不依赖玄学的解法之一：它不建复杂的数据结构，不搞网格细分，只靠一个朴素到近乎笨拙的循环——每次从多边形上"咬"下一个凸耳，直到只剩三个点。听起来简单，但它能保证在 O(n²) 内把任意简单多边形拆成 n-2 个三角形，并且输出的顶点索引严格对应原始输入顺序。这正是"无序顶点 → 获取顶点索引"这条链路的核心价值：你给的是坐标数组，它还给你的是一组组三元索引，直接可以塞进索引缓冲区。搞懂它，你就搞懂了为什么很多图形库在三角化失败时不是报错，而是悄悄吐出一个退化三角形——那背后是耳切判定和自交检测的取舍。

2. 耳切法的判定机制：一个顶点凭什么算"耳朵"

2.1 凸性判定与叉积符号

耳切法里，"耳朵"的定义非常具体：一个顶点是耳朵，当且仅当它和前后两个邻居构成的三角形是凸的，并且这个三角形内部不包含多边形上任何其他顶点。凸性判定靠叉积。给定连续三点 A、B、C，计算向量 AB 和 BC 的叉积 z 分量，符号决定 B 是左转还是右转。对于逆时针多边形，凸顶点对应正叉积。这个判定看起来简单，但它是整个算法的地基，符号搞反了，后面全盘皆输。

def cross(a, b, c): # 向量 AB 与 BC 的叉积 z 分量 # 正值表示逆时针左转（凸），负值表示右转（凹） return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0]) def is_convex(a, b, c): # 仅对逆时针多边形成立；顺时针需整体取反 return cross(a, b, c) > 0

参数说明：a、b、c 是三个连续顶点的二维坐标元组。返回值是浮点数，实际使用中通常配合一个极小阈值 eps 来避免共线点导致的数值抖动。这里有个血泪经验：如果多边形顶点是顺时针存储的，is_convex会全部判反，算法会立刻卡死在一个永远找不到耳朵的死循环里。常见的实现思路是先算一遍有向面积，面积为负就整体反转顶点顺序，再进入主循环。

2.2 点是否在三角形内：耳切法的第二道闸

光凸还不够，还得确认这个凸三角形里没有别的顶点。否则你咬下的"耳朵"会切穿多边形，产生自交。判定点 P 是否在三角形 ABC 内，标准做法是三次叉积同号：P 相对 AB、BC、CA 的叉积符号都与三角形朝向一致。这里有个性能陷阱——朴素实现会对每个候选耳朵遍历全部剩余顶点，复杂度直接顶到 O(n³)。成熟的实现（比如 Earcut 库）会维护一个链表结构，只检查活跃顶点，并且用包围盒做粗筛，把实际开销压回 O(n²) 量级。

function pointInTriangle(ax, ay, bx, by, cx, cy, px, py) { // 三次叉积同号判定，允许边界上的点算作"在内" const d1 = (px - bx) * (ay - by) - (ax - bx) * (py - by); const d2 = (px - cx) * (by - cy) - (bx - cx) * (py - cy); const d3 = (px - ax) * (cy - ay) - (cx - ax) * (py - ay); const hasNeg = d1 < 0 || d2 < 0 || d3 < 0; const hasPos = d1 > 0 || d2 > 0 || d3 > 0; return !(hasNeg && hasPos); }

这段代码的关键在于!(hasNeg && hasPos)：只要三个叉积不全为正也不全为负，点就在三角形内或边界上。边界算"在内"是刻意的保守策略——宁可少咬一个耳朵，也不切穿多边形。代价是共线点多的多边形会多绕几圈，但正确性优先。

2.3 链表结构与耳朵缓存

真正让耳切法从教科书走进工程的是链表。顶点用双向链表串起来，每次咬掉一个耳朵就删一个节点，前后邻居自动接上。Earcut 的实现里还维护了一个ear标记数组和候选队列，避免每轮都从头扫描。这个设计动机很直白：三角化是交互式场景的常客，用户拖一个顶点就要重算一次，O(n³) 的朴素版在几千个点的多边形上会直接翻车。链表加缓存把常数项压下来，才让它能跑在实时路径上。

3. 从坐标到索引：Earcut 主循环怎么吐出三角形

3.1 主循环的骨架

Earcut 的主循环可以概括成一句话：只要剩余顶点超过三个，就找一个耳朵，输出它的三个索引，删掉耳朵顶点，继续。听起来像废话，但魔鬼在"找"的方式上。它维护一个ear数组标记当前哪些顶点是候选耳朵，每轮从队列里取一个，验证通过就输出，然后只更新被删顶点的前后两个邻居的耳朵状态。这个局部更新是性能的关键——大部分顶点在大部分轮次里状态不变，全量重算纯属浪费。

// 简化后的主循环骨架，保留索引输出逻辑 while (remaining > 3) { let earFound = false; for (let i = 0; i < earQueue.length; i++) { const idx = earQueue[i]; if (!isEar(idx)) continue; // 凸性 + 空耳双重校验 const prev = prevNode(idx); const next = nextNode(idx); triangles.push(prev, idx, next); // 输出原始顶点索引 removeNode(idx); // 链表摘除 earQueue.splice(i, 1); updateEar(prev); // 只刷新两个邻居 updateEar(next); earFound = true; break; } if (!earFound) { // 退化处理：切一个最不坏的角，或直接放弃 break; } }

参数说明：triangles是最终输出的索引数组，每三个一组；prevNode/nextNode走链表指针；updateEar重算单个顶点的凸性和空耳状态。注意earFound为 false 的分支——这是耳切法最诚实的部分：它承认自己可能失败。自交多边形、重复顶点、共线退化都可能让队列里一个合法耳朵都没有。成熟实现不会死循环，而是走一个"切角"兜底，输出一个可能退化的三角形，保证索引数量对得上。

3.2 索引映射：为什么输出的是原始下标

这是很多人第一次读 Earcut 源码时的困惑点：内部明明用了链表、重排了顺序，为什么输出的索引还能直接对应输入数组？答案在于节点里存了i字段，记录该顶点在原始坐标数组中的位置。链表只改变遍历顺序，不改变身份。删除节点时，被删顶点的索引不再出现，但幸存节点的i始终指向原始位置。所以最终triangles里的每个数字，都是你输入数组的合法下标。这个设计让调用方完全不需要关心内部重排，拿到索引直接建 buffer 就行。

3.3 孔洞与多边形的桥接

带孔多边形是三角化的真实战场。Earcut 的处理方式是"打桥"：把每个孔洞用一个可见的桥边连到外轮廓上，把多连通区域变成单连通简单多边形，再跑耳切。桥接点的选择有讲究——要保证桥边不穿过多边形边界，否则打桥本身就制造了自交。常见实现是找孔洞最右点，向外轮廓投射射线找可见顶点。这一步的鲁棒性直接决定带孔三角化的成败，也是很多库在复杂孔洞上翻车的根源。

4. 避坑与排查：耳切法落地时的五类翻车现场

4.1 现象：算法卡死，索引数量永远凑不够

原因几乎总是顶点绕序不一致。外轮廓逆时针、孔洞也逆时针，打桥后凸性判定全乱。解决：进入主循环前统一绕序，外轮廓逆时针、孔洞顺时针，用有向面积符号判断并反转。

4.2 现象：输出三角形互相重叠，渲染出破面

这是自交多边形被强行三角化的典型症状。耳切法假设输入是简单多边形，自交输入下"空耳"判定会失效。解决：预处理阶段做一次自交检测，或者接受退化输出并在渲染层用模板缓冲兜底。别指望耳切法自己修复自交。

4.3 现象：共线顶点导致耳朵永远找不到

三个连续共线点构成的"三角形"面积为零，凸性判定在浮点误差下摇摆。解决：预处理剔除共线冗余点，或者在叉积判定里加 eps 阈值，把接近零的叉积当作凹处理。

4.4 现象：大坐标下判定失准

顶点坐标动辄上万时，叉积的浮点误差被放大，点在内判定开始误判。解决：三角化前把坐标归一化到单位范围，输出索引不受影响，因为索引与坐标尺度无关。

4.5 现象：孔洞桥接点选错，桥边穿边界

孔洞最右点投射射线时，如果外轮廓有凹陷，可能连到不可见顶点。解决：桥接前做可见性检查，或者改用更稳的扫描线打桥策略。这块没有银弹，只能靠测试用例堆。

5. 设计取舍：为什么耳切法至今没被更快的算法淘汰

三角化领域不缺更快的算法。单调多边形剖分能把复杂度压到 O(n log n)，约束 Delaunay 三角化在质量上更优。但耳切法依然活得很好，原因在于它的取舍非常诚实：用 O(n²) 换实现简单、无外部依赖、索引输出直接可用。单调剖分需要先做梯形分解再逐块处理，代码量和调试成本翻几倍；Delaunay 需要维护边翻转和空圆判定，对退化输入更敏感。耳切法不追求三角形质量，只追求"能出合法索引"，这在渲染、GIS 瓦片、字体轮廓填充这些场景里恰好够用。

验证一个耳切实现是否靠谱，我一般会跑三组用例：纯凸多边形（应输出 n-2 个三角形且无退化）、带一个凹口的简单多边形（检查凹点不被误判为耳朵）、带孔洞的环形（检查桥接后索引总数是否等于 n+2h-2）。如果三组都过，基本可以放心用。

从那以后我每次接入三角化库，都强制先跑一遍绕序归一化和共线剔除，再进主循环——这两步省掉的调试时间，比任何优化都值。希望帮到你。

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