简介这是一套基于耳切法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)), keylambda 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_idx1] hole[hole_idx:] hole[:hole_idx1] [merged[outer_idx]] merged[outer_idx1:] return merged逻辑说明桥接思路是在孔洞与外部边界之间连一条“共享边”把孔洞顶点插入到外部多边形顶点序列中使整体成为同一个简单多边形。这里选择最近距离点作为桥接位置能减少后续三角化时出现细长三角形的概率。5.2 从二维扩展到三维坐标的降维投影如果你需要给三维表面的顶点做三角化最简单的办法是把三维点投影到二维平面上三角化后再映射回三维坐标。项目里我封装了一个投影函数def project_3d_to_2d(points_3d): # 用顶点法向量或者固定轴做投影 # 这里以默认的 z0 平面投影为例 return [(p[0], p[1]) for p in points_3d]逻辑说明points_3d是[(x, y, z), ...]的列表。投影到二维后耳切法正常运行输出索引直接映射回三维原数据即可完成三维表面三角化。如果你的三维模型轮廓比较复杂建议换成“基于主成分分析”的投影平面计算这能避免投影后多边形自交的问题。5.3 添加最小边长约束的实用插件耳切法切出来的三角形可能包含瘦长尖角对渲染和物理模拟都不友好。一个很常用的后期处理是“最小角优化”在局部范围内交换对角线def flip_edges(triangles, points, max_iter100): # 简单实现局部边翻转逼近 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再上线毕竟算法这东西看着对不代表真对了。希望帮到你。本文还有配套的精品资源点击获取
