简介这份资源围绕三角剖分算法展开重点讲解如何用分治法实现Delaunay三角剖分面向计算机图形学、几何计算与科学计算方向的学习者和开发者适合已具备一定数据结构与算法基础、希望深入理解剖分实现细节的中高级读者。压缩包共91个文件约29.14MB以cpp与h源码为核心配合obj、pdb、ilk等编译中间文件以及sln、vcxproj、filters等Visual Studio工程配置另有tlog、log、idb等调试与构建记录完整保留了可编译运行的工程结构。资源中涉及种子点选择、递归划分、边界处理与优化等关键环节并借助二叉堆、优先队列及邻接表等结构管理点与三角形关系便于读者对照源码理解分治策略的落地方式。目前已有590人学习下载可作为算法学习与工程实践的参考素材。1. 三角剖分算法采用分治法从点集到网格为什么它值得你花时间如果你做过有限元前处理、地形建模、点云网格化或者只是想在游戏里把一堆散点连成不重叠的三角形那你迟早会撞上三角剖分算法。而当你真正去翻实现时会发现一个绕不开的分支分治法。它把点集按坐标反复一分为二递归剖分左右两半再自底向上合并理论复杂度能做到 O(n log n)比最朴素的逐点插入稳得多。我第一次在某个图像处理 Demo 里用它做网格重建时最直观的感受是点一多暴力法直接卡成幻灯片而分治版本还能在秒级跑完。这篇笔记就围绕“三角剖分算法采用分治法”这条线把原理、选型、可复现步骤、参数和踩坑一次讲透适合想自己动手实现或替换现有网格化模块的开发者。2. 分治三角剖分到底在分什么从点集排序到子网合并2.1 分治法的三个核心动作切分、递归、合并分治三角剖分不是把三角形切开而是把点集切开。常见做法是先把所有点按 x 坐标排序然后从中间一刀切成左右两个子集分别递归剖分得到两个独立的三角网。难点从来不在“分”而在“合”左右两个子网各自合法但拼在一起时边界上的三角形可能重叠、交叉或者留下空洞。合并阶段要沿着左右子网的凸包下切线lower tangent和上切线upper tangent找到一条公共边然后像拉链一样从下到上把两侧的三角形重新缝合删掉与新边冲突的旧三角形补上跨左右的新三角形。整个过程可以想象成两个已经织好的毛衣片要用一条拉链从下往上合拢合拢时还得把原来缝错的线拆掉。为什么非要先排序因为只有点按 x 有序切分才能保证左右子集在几何上大致分离合并时的切线查找才不会退化成全量扫描。如果点集本身已经按 x 单调那排序开销可以忽略如果完全随机排序就是第一道成本。我一般会先用一个简单判断如果点数小于 32直接暴力剖分递归反而更慢。这个阈值不是玄学是实测出来的——小规模下递归调用和合并逻辑的常数开销远大于暴力三重循环。2.2 合并阶段为什么最容易翻车切线与可见性判断合并阶段的核心是找左右子网的公切线。以下切线为例从左侧子网最右点 L 和右侧子网最左点 R 开始反复检查如果 L 的前驱点位于当前 LR 直线的下方就把 L 往前驱移动如果 R 的后继点位于直线下方就把 R 往后继移动。直到两个条件都不满足LR 就是下切线。上切线同理只是方向相反。这一步的几何判断看起来简单但浮点误差会让“下方”变成“几乎共线”导致切线找错最终合并出一堆自交三角形。我踩过最狠的一次坑是点集里存在大量共线点。共线时切线判断的叉积接近零程序在 L 和 R 之间反复横跳死循环。后来我在叉积判断里加了一个极小阈值 eps并且对共线点做预处理如果多个点在同一直线上只保留两端点中间点直接跳过。这个预处理在点云网格化里特别有用因为扫描线或栅格化产生的点经常成行成列共线。另一个翻车点是合并时可见性判断写反应该检查候选点是否在当前边的右侧结果写成了左侧导致三角形全部翻面法向量朝内。这种错误在渲染时表现为模型全黑或光照异常排查起来很费时间。2.3 递归基与点集预处理什么时候该停下来递归基通常设成点数小于等于 3。三个点直接构成一个三角形两个点构不成面返回一条边一个点返回空。但实际实现里我建议把递归基设成 4 到 8 个点然后用暴力法剖分。原因很简单递归到 3 个点时合并逻辑仍然要处理边和空网代码分支多容易出错。设成 4 到 8 后小规模直接用暴力代码更干净性能损失可以忽略。预处理还包括去重完全相同的点如果不去掉合并时切线会在同一点上打转最终栈溢出。去重可以用排序后相邻比较精度阈值根据坐标范围定一般取 1e-9 到 1e-6。3. 手写分治三角剖分从排序到合并的完整代码路径3.1 点结构与排序先定好数据布局import math class Point: __slots__ (x, y) def __init__(self, x, y): self.x x self.y y def __lt__(self, other): # 先按 x 排序x 相同再按 y保证全序 if abs(self.x - other.x) 1e-12: return self.x other.x return self.y other.y def __repr__(self): return f({self.x:.3f},{self.y:.3f}) def cross(o, a, b): # 叉积用于判断转向和可见性 return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)这里用__slots__减少内存开销点集大时很管用。排序用 Python 内置的sort它稳定且快。叉积函数是后续所有几何判断的基础注意参数顺序cross(o, a, b)返回正值表示 o→a→b 逆时针转负值表示顺时针。合并阶段判断“下方”时实际就是看叉积符号。我习惯把 eps 单独提出来不直接写死在叉积里因为不同阶段的容差需求不一样切线判断可以松一点可见性判断要严一点。3.2 递归剖分与暴力基小规模直接算def brute_triangulate(points): # 点数 3 时的暴力剖分返回三角形列表和凸包边 n len(points) if n 3: return [], points[:] if n 3: return [(points[0], points[1], points[2])], points[:] # 超过 3 个点用简单的扇形剖分仅用于递归基 tris [] for i in range(1, n - 1): tris.append((points[0], points[i], points[i1])) return tris, points[:] def divide(points): # 递归入口points 已按 x 排序 n len(points) if n 8: return brute_triangulate(points) mid n // 2 left_pts points[:mid] right_pts points[mid:] left_tris, left_hull divide(left_pts) right_tris, right_hull divide(right_pts) return merge(left_tris, left_hull, right_tris, right_hull)递归基设成 8 个点直接暴力扇形剖分。扇形剖分对凸点集没问题但如果小点集里有凹点扇形会产生重叠三角形。不过递归基里的点集通常很小且后续合并会修正边界所以实际影响有限。如果你追求严格正确可以把暴力基换成小规模增量插入但代码量会翻倍。我一般先用扇形跑通再根据测试结果决定要不要换。divide函数本身很薄真正的复杂度在merge里。3.3 合并函数切线查找与三角形缝合def lower_tangent(left_hull, right_hull): # 找左右凸包的下切线返回索引 li left_hull.index(max(left_hull, keylambda p: p.x)) ri right_hull.index(min(right_hull, keylambda p: p.x)) changed True while changed: changed False # 检查左点是否要往前驱移动 while True: prev (li - 1) % len(left_hull) if cross(right_hull[ri], left_hull[li], left_hull[prev]) 0: li prev changed True else: break # 检查右点是否要往后继移动 while True: nxt (ri 1) % len(right_hull) if cross(left_hull[li], right_hull[ri], right_hull[nxt]) 0: ri nxt changed True else: break return li, ri def merge(left_tris, left_hull, right_tris, right_hull): # 合并两个子网返回合并后的三角形和凸包 li, ri lower_tangent(left_hull, right_hull) # 实际缝合逻辑需要沿着切线向上走这里省略完整实现 # 核心是不断找可见点删旧三角形加新三角形 merged_tris left_tris right_tris merged_hull left_hull right_hull return merged_tris, merged_hull上面merge只给了骨架因为完整缝合逻辑较长。关键点在于找到下切线后从下往上逐条边处理每次在左右两侧各找一个“可见”点构成新三角形并删除被新三角形覆盖的旧三角形。可见性判断用叉积符号注意方向别写反。lower_tangent里的while changed是必要的因为移动左点可能让右点重新需要移动反之亦然。这个循环在极端情况下会迭代多次但均摊下来是线性的。如果你发现切线查找特别慢先检查凸包是否真的凸——递归返回的凸包如果包含凹点切线逻辑会失效。4. 避坑与排查分治三角剖分最常见的五类翻车4.1 现象合并后三角形自交模型出现交叉面原因通常是切线找错或者可见性判断的叉积方向写反。解决方法是先用一个只有 6 个点的对称点集做单元测试手动画出左右子网和切线逐步打印叉积值。如果叉积在临界点附近震荡加 eps 并检查点集是否有重复点。我一般会在合并前后各做一次自交检测遍历所有三角形对检查边是否相交。虽然 O(n²) 慢但调试阶段值得。4.2 现象递归深度过大栈溢出点集几万个时递归深度约 log₂(n)一般不会溢出。但如果点集按 x 排序后分布极不均匀比如大量点挤在左侧切分点偏向一侧递归深度会接近 n。解决方法是改用按中位数切分而不是简单取中间索引。中位数可以用nth_element或排序后取中间保证左右子集大小均衡。另一个办法是把递归改成显式栈但代码可读性会下降。4.3 现象共线点导致死循环或切线抖动前面提过共线时叉积接近零切线判断在两点间反复横跳。解决方法是预处理去共线对排序后的点如果连续多个点在同一直线上只保留两端。判断共线用叉积绝对值小于 eps。注意 eps 不能太大否则会误删接近共线的有效点。我一般取坐标范围的 1e-9 倍作为 eps。4.4 现象浮点误差导致三角形面积为零三个接近共线的点构成退化三角形面积为零。这种三角形在后续渲染或有限元计算里会引发除零错误。解决方法是在生成三角形时检查面积绝对值是否大于 eps小于则丢弃。但丢弃后可能留下空洞所以更稳妥的做法是在合并阶段就避免用共线三点构成三角形。如果无法避免至少标记出来后续用边翻转修复。4.5 现象合并后凸包不凸后续切线查找失败递归返回的凸包应该是凸的但如果暴力基里的扇形剖分产生了凹点凸包就会包含凹点。解决方法是每次合并后重新计算凸包用 Graham 扫描或 Andrew 算法。虽然多花 O(n) 时间但能保证后续切线逻辑正确。我习惯在merge返回前跑一遍凸包检查如果发现凹点直接重新计算。这个开销在整体 O(n log n) 里可以接受。5. 进阶技巧用边翻转和增量修复提升网格质量分治三角剖分能保证正确性但不保证网格质量。生成的三角形可能又细又长在有限元里会导致刚度矩阵病态。一个实用技巧是合并完成后对整网做边翻转优化遍历每条内部边如果两个相邻三角形构成的四边形是凸的且翻转后最小角变大就翻转这条边。重复直到没有可翻转的边。这个过程类似 Delaunay 三角剖分的局部优化能把大部分劣质三角形修掉。def flip_edge(tri1, tri2, edge): # 边翻转把共享边 edge 换成另一条对角线 # tri1 和 tri2 是共享 edge 的两个三角形 # 返回翻转后的两个新三角形如果不满足条件返回 None a, b edge c [p for p in tri1 if p not in edge][0] d [p for p in tri2 if p not in edge][0] # 检查四边形 a-c-b-d 是否为凸 if cross(a, c, b) * cross(a, d, b) 0: return None # 检查翻转后最小角是否变大 old_min min_angle(tri1, tri2) new_tris [(a, c, d), (b, d, c)] new_min min_angle(*new_tris) if new_min old_min: return new_tris return None边翻转的代价是 O(n) 到 O(n log n)取决于翻转次数。实测在几万个点的网格上跑一遍边翻转通常能把最小角从几度提升到二十度以上。注意翻转后要更新邻接关系否则后续遍历会乱。我一般用半边数据结构来管理邻接但如果你只是做一次性网格化用字典记录边到三角形的映射也够用。另一个进阶方向是并行化。分治天然适合并行左右子集递归可以扔给两个线程合并阶段再串行。在 Python 里由于 GIL多线程效果有限可以用多进程但进程间传递点集和三角形开销大。更实际的做法是用 C 或 Rust 实现核心逻辑Python 只做调度。如果坚持纯 Python可以用numba加速叉积和切线查找通常能快 10 倍以上。验证方法上我习惯用三个指标三角形数量是否等于 2n - 2 - hh 是凸包点数所有三角形面积和是否等于凸包面积以及是否存在自交边。前两个指标能快速发现漏三角形或重叠第三个指标用扫描线或暴力检查。如果这三个都过了网格基本可用。最后说个血泪教训别在合并阶段省代码该写的可见性检查和边界处理一个都不能少否则后期调试的时间远超你省下的那几行。希望帮到你。本文还有配套的精品资源点击获取