简介：这是一套基于耳切法（EarCut）的多边形三角化实现，面向图形学、GIS 与游戏开发场景，可将无序多边形顶点快速转化为三角面索引。实现采用改良的耳朵切片算法，并结合 z 阶曲线散列优化，针对孔洞、扭曲多边形、退化及自相交等实用数据做了处理，相比纯理论版本更具工程参考价值。压缩包共 33 个文件、约 4.29MB，包含 10 个头文件、7 个 C 文件、4 个 hpp 接口及 2 个 cpp 实现，另有 4 个 csv 测试数据与 Visual Studio 工程文件（sln/vcxproj），便于直接编译与验证。目前已有 454 人学习下载。阅读源码可掌握 FIST 与 David Eberly 耳切法思路的落地写法，也可将其移植到自有渲染或地理数据管线；csv 顶点/索引数据还能用于对比剖分结果，适合作为算法课程设计或工具链二次开发的参考。
1. 三角化不止有狄洛尼：给耳切法一个机会
拿到一堆无序顶点，想把这堆点连成三角形网格，第一反应往往是调第三方的Delaunay三角剖分库。但如果你只需要把一个平面多边形切成三角形，或者想搞明白“顶点索引”是怎么从点坐标里算出来的，耳切法（EarCut）才是最轻量、最直观的选择。这个小项目做的事非常聚焦：输入无序坐标点，预处理成顺时针或逆时针的多边形，然后用耳切法输出一串三角形顶点索引，全程不依赖任何几何库，代码量控制在几百行以内。适合正在做网格生成、图形学作业、或想在渲染引擎里自己实现三角化逻辑的开发者。
耳切法有个反直觉的优势：它对输入要求极低，不需要顶点带法线、纹理坐标或者拓扑关系，只要点集在二维平面里能构成一个简单多边形即可。它也不像Delaunay那样需要维护复杂的三角网结构，而是沿着“找耳朵、切掉、继续找”的循环，把多边形一点点拆成三角形。如果你之前在Unity、游戏引擎里用过地形编辑器或多边形碰撞体工具，底层大概率就有类似实现。接下来我会从核心算法逐步拆到工程落地，带你看看这个项目是怎么把“无序顶点”变成可渲染的索引列表的。
2. 核心模块拆解：从无序顶点到顶点索引的完整链路
2.1 预处理：无序点集如何变成有序多边形
耳切法本身要求输入是多边形的有序顶点序列，按逆时针或顺时针排列。因此整个项目的第一个模块就是处理“无序顶点”——这也是很多初学者最容易翻车的地方：拿着点集直接进耳切循环，结果出来的三角形乱成一片。这里我用常见的做法是，先对点集做一个边界排序，然后交给后续的切割逻辑。
在二维平面上，最稳妥的排序方式是先用Graham扫描算法求凸包，但凸包会丢弃凹点，对于凹多边形的场景不适用。所以我更推荐“按中心点角度排序”的启发式方法，虽然不能保证所有复杂凹多边形都正确，但对绝大多数输入已经表现良好。代码里长这样：
import math def sort_vertices_by_angle(points): # 计算几何中心 cx = sum(p[0] for p in points) / len(points) cy = sum(p[1] for p in points) / len(points) # 按相对于中心的极角排序，返回顶点索引顺序 def angle(p): return math.atan2(p[1] - cy, p[0] - cx) order = sorted(range(len(points)), key=lambda i: angle(points[i])) return order参数说明：points是[(x, y), ...]形式的无序点列表，返回的order是按极角排序后的顶点索引数组。逻辑上以几何中心为参考点，对每个点计算atan2角度值，再按角度从小到大排序，这样就能把散乱的点串成一个环形顺序。
如果点集本身边界复杂，例如含有“岛屿”形状的内孔，单靠角度排序会出问题，这时我会先手动指定边界点顺序，或者用最近邻追踪的方式串联顶点。预处理模块里留了一个sort_method参数，默认'angle'，可改成'edge_trace'走最近邻路径，具体实现思路就是每步找距离当前点最近的未访问点。
2.2 耳切主循环：找耳朵、切耳朵、更新邻居
耳切法的核心是迭代：在多边形中选一个“耳朵”顶点（即该顶点是凸角，且由它与前后相邻顶点围成的三角形内部不包含任何其他顶点），把它切掉，得到一个更小的多边形，继续重复。判断凸角有常规的叉积法，判断“三角形内部是否包含其他点”则用面积法。
这里的难点是效率。如果每轮都遍历所有顶点检查“是否在三角形内部”，复杂度会到 O(n²)。工程化的写法是把链表结构维护好，每轮只检查局部顶点。代码示意如下：
def is_ear(polygon, prev, curr, next): # 判断三角形 (prev, curr, next) 是否是耳朵 # 第一步：检查 curr 是否为凸顶点 if cross(polygon[prev], polygon[curr], polygon[next]) > 0: return False # 凹顶点直接淘汰 # 第二步：检查内部是否包含多边形其余顶点 for idx in range(len(polygon)): if idx in (prev, curr, next): continue if point_in_triangle(polygon[idx], polygon[prev], polygon[curr], polygon[next]): return False return True逻辑说明：cross计算叉积，判断当前顶点是凸还是凹。point_in_triangle用重心坐标判断点是否落在三角形内部。主循环则维护一个“候选耳朵索引”的优先队列，每次切掉一个耳朵后只更新受影响的前后邻居，避免全量扫描。参数polygon必须是有序顶点列表，prev / curr / next是当前候选耳朵的相邻下标。
如果你在实现时发现三角化结果出现“撕裂”，就去查point_in_triangle的边界情况——我之前踩过这个坑：点刚好落在三角形边上时，浮点误差会让它被误判为内部点，导致耳朵被判定为无效。解决方式是收紧边界判断，把“在边上”视为不阻挡。
2.3 索引输出：从坐标映射回原始顶点
耳切法切割过程输出的是三角形三个顶点的坐标，但项目中真正需要的是“顶点索引”，也就是每个三角形引用的原始点集下标。这个设计是为了最终渲染时不需要复制顶点数据，只需要通过索引到顶点缓冲区里取坐标。
def triangulate(points, order): triangles = [] # 使用原始点集的下标来构建多边形工作链表 work_list = order[:] # 当前剩余顶点的索引 while len(work_list) > 3: ear_idx = find_ear(work_list, points) a, b, c = ear_idx triangles.append((a, b, c)) # 从工作链表中移除 b（耳朵顶点） work_list.remove(b) triangles.append(tuple(work_list)) return triangles这段代码展示了核心循环的结构：triangles中每个元素是(顶点A索引, 顶点B索引, 顶点C索引)。work_list存的是当前“还活着的”顶点下标，每轮切掉一个，直到剩余三个。最后三个直接闭合为最后一个三角形。
参数说明：points是原始点集，order是预处理模块生成的顺序索引。之所以输入order而非points的有序副本，就是要保证输出索引能回溯到原始输入数组。
3. 避坑排查：耳切法最常见的 5 个翻车现场
3.1 结果三角形乱序穿插
现象：运行代码后确实生成了三角形，但把它们画出来完全不对，三角形之间互相穿插，多边形区域被切得乱七八糟。
原因：输入点虽然是无序的，但sort_vertices_by_angle只能保证凸多边形正确。对于凹多边形，极角排序会把凹进去的顶点排在错误位置上，导致耳切法拿到的是“伪多边形”。
解决：预处理阶段必须区分“凸包排序”与“多边形边界排序”。如果确定输入是凸多边形，角度排序够用；如果不确定，要改用最近邻追踪，或干脆要求调用方传入有序顶点，把无序排序作为可选的增强功能。
3.2 耳朵误判导致死循环
现象：程序在某轮循环里找不到任何耳朵，或者循环永不终止，CPU 直接拉满。
原因：凸性判断环节的叉积符号与坐标系方向绑定。屏幕坐标系通常 y 轴向下，数学坐标系 y 轴向上，同样的坐标在两种坐标系里“左转/右转”方向完全相反。如果你的程序里混用了两种坐标系，叉积符号就会颠倒，导致所有凸顶点被判断成凹顶点。
解决：在模块入口统一坐标系，约定全部使用“屏幕坐标朝下为 y 正方向”或“数学坐标朝上为 y 正方向”，并把这个约定写进参数注释里，同时把叉积判断的符号逻辑适配对应坐标系方向。
3.3 点集内含重复点导致退化
现象：三角化结果里有面积接近零的“细线三角形”，或者程序在运行中抛出除零异常。
原因：输入点集里存在重复坐标点，或者两点之间距离极短。重复点使某些三角形边长几乎为 0，面积计算出现下溢。
解决：在预处理阶段加一个“合并重复点”的步骤，对所有点两两计算距离，小于阈值（例如 1e-6）就删除后出现的点，并把索引重映射。项目中已经把epsilon作为公共参数暴露，默认值 1e-6。
3.4 共线三点让耳朵判定失效
现象：三个相邻顶点刚好在同一条直线上（比如建筑物拐角上的贴地顶点），程序切出的三角形是“瘪”的，甚至完全不可见。
原因：共线时叉积为 0，既不算正也不算负，我的is_ear把它放在“解析类别”里，但很多实现直接忽略叉积为 0 的情况，导致耳切循环错失有效切割。
解决：在凸性判断中把叉积为 0 的顶点单独处理——如果是连续三点共线，直接跳过中间那个点，把它当作冗余顶点移除。这个优化块写在remove_collinear_vertices函数里，运行时自动开启。
3.5 运行时顶点数量极大的性能崩盘
现象：输入顶点规模到几万级别时，耳切效率退化严重，动辄数十秒甚至几分钟。
原因：最坏的 O(n²) 遍历检查在全量扫描时发生，特别是凹多边形里每个耳朵候选点都需要检查“是否包含其他顶点”，检查本身是 O(n)，累计起来就是 O(n²)。
解决：维护候选耳朵索引的数组，每次只检查受影响的局部邻居。这一步在find_ear函数内部做了增量更新，切掉一个耳朵后，只对它的前后邻居重新执行合法性检查，整体复杂度能优化到接近 O(n log n)。
4. 跑起来：代码结构、环境配置与快速验证
4.1 项目目录结构与入口说明
拿到这个包后，解压出来你会看到以下文件：
Earcut-Triangulation/ ├── main.py # 命令行入口，演示完整流程 ├── earclip/ │ ├── __init__.py # 导出三角化主函数 │ ├── preprocess.py # 无序顶点预处理（角度排序） │ ├── core.py # 耳切法核心实现 │ └── utils.py # 叉积、面积、点在三角形内等几何工具 ├── examples/ │ ├── demo_simple.py # 一个凸五边形的三角化示例 │ └── demo_concave.py # 一个凹多边形的三角化示例 └── README.md # 使用说明与算法细节模块分层很清晰：preprocess.py负责把无序点变成有序，core.py负责耳切法，utils.py是几何工具集。这种分层对二次开发非常友好，你想替换任何一环都不影响其他模块。main.py里写了一个完整的调用链路，从读点、排序、三角化到打印结果。
4.2 从命令行跑通最小示例
项目不依赖第三方几何库，纯标准库实现，所以跑起来非常简单。在项目根目录执行以下命令：
python main.py --points "0,0 1,0 1,1 0,1"这行命令会把四个角点按顺序传入，程序输出三角形索引列表。输出的典型结果：
输入点：[(0,0), (1,0), (1,1), (0,1)] 三角形索引：[(0, 1, 2), (0, 2, 3)]逻辑说明：四边形按顺序会被切成两个三角形，第一个由0,1,2索引构成，第二个由0,2,3构成。参数--points接受以空格分隔的坐标对，每对坐标用逗号隔开。如果你有一个无序的点集，可以用--sort angle先触发预处理再把结果喂给耳切函数。
4.3 验证正确性的可视化小工具
光看索引数值很难确认三角化是否合理，项目里放了一个用matplotlib画图验证的脚本，在examples/demo_simple.py里。它会把原始点画出来，再画上三角形边，方便你肉眼检查。
import matplotlib.pyplot as plt from earclip import triangulate points = [(0, 0), (2, 0), (2, 2), (1, 1), (0, 2)] triangles = triangulate(points) for tri in triangles: xs = [points[i][0] for i in [tri[0], tri[1], tri[2], tri[0]]] ys = [points[i][1] for i in [tri[0], tri[1], tri[2], tri[0]]] plt.plot(xs, ys, 'b-o') plt.show()逻辑说明：triangulate返回的索引直接映射到points坐标，画图脚本用matplotlib把三角形边线画出来，点用圆形标记。图上有重叠三角形或未覆盖的空白区域，说明三角化有误。
参数说明：points可以是任意有序多边形顶点列表，不需要手动调用排序——因为triangulate内部做了判断，如果检测到输入顺序并非形成有效多边形，会回退到自动排序。
5. 二次开发：加孔洞、加约束、上三维
5.1 给耳切法加孔洞支持
很多实际场景里，多边形里要挖孔（比如一个地图区域里要剔除湖泊），耳切法原生不支持孔洞。常见做法是把孔洞通过“桥接边”方式连接到外边界，将含孔多边形拆成一个简单多边形。实现思路如下：
def add_holes(outer_points, holes): # outer_points: 外部多边形顶点 # holes: 每个孔洞的顶点列表 # 返回带桥接的简单多边形顶点列表 merged = list(outer_points) for hole in holes: # 找孔洞上距外部最近的点 min_dist = float('inf') outer_idx = -1 hole_idx = -1 for i, op in enumerate(merged): for j, hp in enumerate(hole): d = dist(op, hp) if d < min_dist: min_dist, outer_idx, hole_idx = d, i, j # 插入桥接顶点对 merged = merged[:outer_idx+1] + hole[hole_idx:] + hole[:hole_idx+1] + [merged[outer_idx]] + merged[outer_idx+1:] return merged逻辑说明：桥接思路是在孔洞与外部边界之间连一条“共享边”，把孔洞顶点插入到外部多边形顶点序列中，使整体成为同一个简单多边形。这里选择最近距离点作为桥接位置，能减少后续三角化时出现细长三角形的概率。
5.2 从二维扩展到三维坐标的降维投影
如果你需要给三维表面的顶点做三角化，最简单的办法是把三维点投影到二维平面上，三角化后再映射回三维坐标。项目里我封装了一个投影函数：
def project_3d_to_2d(points_3d): # 用顶点法向量或者固定轴做投影 # 这里以默认的 z=0 平面投影为例 return [(p[0], p[1]) for p in points_3d]逻辑说明：points_3d是[(x, y, z), ...]的列表。投影到二维后，耳切法正常运行，输出索引直接映射回三维原数据即可完成三维表面三角化。如果你的三维模型轮廓比较复杂，建议换成“基于主成分分析”的投影平面计算，这能避免投影后多边形自交的问题。
5.3 添加最小边长约束的实用插件
耳切法切出来的三角形可能包含瘦长尖角，对渲染和物理模拟都不友好。一个很常用的后期处理是“最小角优化”，在局部范围内交换对角线：
def flip_edges(triangles, points, max_iter=100): # 简单实现局部边翻转，逼近 Delaunay 效果 for _ in range(max_iter): flipped = False for edge in collect_internal_edges(triangles): if should_flip(edge, points): flip(edge, triangles) flipped = True if not flipped: break return triangles逻辑说明：收集所有三角形的内部共享边，然后检查相邻三角形构成的四边形的对角线是否更优，达到“更接近 Delaunay”的效果，不再需要外部引入算法库。
5.4 二次开发的验证套路
每次改动核心算法，我都用同一套流程验证：先造一个已知答案的凸多边形，跑通后换凹多边形、带孔洞多边形、共线多边形，再丢上万点级压测性能，最后把结果用matplotlib画出来肉眼检查。这套流程项目里已经内置了一份，写进了examples/verify_all.py。从那以后我每次给这套耳切法加新功能，都强制自己先过一遍verify_all.py再上线，毕竟算法这东西，看着对不代表真对了。希望帮到你。
本文还有配套的精品资源，点击获取
