简介一套基于VC6.0的TIN三角网快速生成算法完整工程面向GIS、测绘与计算机图形学学习者解决大规模散点构建不规则三角网的效率问题。工程采用面向对象方式组织通过三角形、边、顶点等核心类完成Delaunay三角网的数据结构与构建流程并配有参数输入对话框和视图绘制模块便于观察插点、连边及成网结果。压缩包共含88个文件其中26个目标文件、13个头文件与13个源文件构成核心代码另有2个可执行文件直接运行并保留调试过程文件整体仅769KB结构紧凑。已有1319人学习适合希望深入理解Delaunay三角网生成细节的开发者可对照源码、调试信息与成品程序快速掌握TIN的构建逻辑并在此基础上改进或扩展。工程同时提供调试版与发布版两种配置方便对比不同编译模式下的执行效率。1. 最快的TIN三角网生成算法从逐点插入到分治归并的这条路TIN不规则三角网是从点云生成地形网格的核心结构坡度分析、土方量计算、洪水模拟都要依赖它。点少的时候无所谓点一多差距就出来了用逐点插入法生成十几万点就要等上几秒到百万级直接不可用分治归并算法可以把时间压到接近排序的代价这也是高性能流水线里真正在跑的路线。这篇文章围绕“最快”展开先讲清分治归并为什么快再给可复现的 C 骨架最后把 leafSize、坐标精度、内存分配这些决定实际速度的参数和踩坑点说透。适合正在做点云处理、需要把 TIN 生成从能跑优化到跑得快的开发者。2. 分治归并为什么比逐点插入快复杂度与内存布局的取舍2.1 满足空圆性质的三角网TIN 质量与 Delaunay 底色大多数工程场景里要的 TIN 不是随便连的三个点而是满足 Delaunay 条件的三角网每个三角形的外接圆内不允许出现第四个顶点。这个性质保证三角形不会出现极细长的形状线性插值出来不会因为单元质量差而产生锯齿。很多人跳过这一步直接用最近邻或者排序后顺序连线生成速度很快但地形分析一跑就出问题等值线毛刺、体积算不准回头还是要换回 Delaunay。分治归并相比逐点插入的优势在于它不是在已有网格上反复插入点然后局部重建而是把点集一分为二、各自建网、再缝合。缝合时两个子网的边界会优先连接再通过局部翻转边恢复空圆性。整个过程不需要全局重建操作范围永远被限制在左右两个子网的交界带上。所以“最快”和“质量”在分治归并里不冲突速度来自于减少无效操作质量来自于每一步的局部论文检查。我一般会先确认一个前提你需要的 TIN 是否要求 Delaunay 性质。只做简单可视化、不用于插值和体积计算可以不追求严格 Delaunay用更简单的带状三角化但只要涉及坡度、土方、汇水分析分治归并生成的 Delaunay TIN 是唯一值得投入的实现方向。2.2 逐点插入、扫描线与分治归并O(n log n) 的分界点逐点插入的本质是每来一个点就找一个包含它的三角形然后把三角形拆成三个再对三条边做 LOP局部优化过程。定位三角形这一步在十万点点集里会变成双重循环的代价最坏情况 O(n²)。虽然可以用空间索引把定位优化到接近 O(log n)但每个点进去都要访问数组、更新邻接信息常数非常大。到百万点级别逐点插入基本是放弃治疗的方案。扫描线算法理论上也是 O(n log n)先按 y 坐标排序然后用扫描线切分事件点逐个生成三角形。它的问题在于事件类型多处理退化点集水平线、共线点、重合点时分支极其繁琐。我在一个图像处理 Demo 里试过自己实现的扫描线版本单点插入、多点同步、边界闭合三种情况各写一套逻辑最后 debug 的时间比实现分治归并多一倍速度还未必占优。分治归并的做法是按 x 排序 → 不断对半递归 → 每个叶子用简单方法建网 → 归并时只处理左右交界带的边。排序 O(n log n)递归每层线性扫描总复杂度稳定在 O(n log n)。关键是它没有“在平面里找点”这种跳跃操作所有访问都顺着排序后的数组和局部邻接链表走cache 命中率比逐点插入好一个量级。算法最坏复杂度实现难度常数因子百万点实测观感逐点插入 线性定位O(n²)低极高数十秒到分钟逐点插入 网格索引O(n log n)中高数秒扫描线O(n log n)高中容易卡在退化分治归并O(n log n)中高低百毫秒级这里的分界点不是十万还是二十万而在于你的数据量是否长期停留在十万以下。超过这个规模分治归并的收益是成倍的值得在初期就选它。2.3 时间都花在哪排序、递归、公切线缝合与 LOP很多人以为复杂度的优化意味着“步骤变少”实际分治归并的步骤一个不少但它把每一步都控制在线性范围。我拆解过一次一百二十万点的生成耗时排序占大概 15%递归建叶节点占 12%剩下 70% 以上都花在归并缝合和 LOP 上。缝合是分治归并的灵魂也是和逐点插入最大的区别先找左子网最右点和右子网最左点之间的上下公切线然后从下切线开始沿着两道切线的边界逐条构造新三角形一边构造一边用 LOP 恢复 Delaunay 性质。这里有个常见的误区认为 LOP 也要全局扫一遍。其实分治归并里的 LOP 只在缝合形成的三角形邻接边附近传播每条边最多被翻转几次总和还是线性的。排序省不掉但它只是简单的 std::sort真正决定快慢的是缝合阶段的数据结构——每次从一个边界顶点跳到下一个边界顶点是不是 O(1)判断“该往哪边走”是不是只查局部邻居。内存布局也需要顺着递归走顶点数组保持排序后的连续存储三角形表预先分配好容量缝合时只往里填不做动态 push_back 频繁扩容。我见过最慢的分治实现就是把三角形表用 std::vector 默认行为一点一点涨三百万点生成完性能直接掉到和逐点插入没差别问题不在算法在内存抖动。3. 用分治归并在本地跑通最小生成C 骨架与数据流3.1 输入与去重把任意点集变成有序顶点缓冲区分治归并的第一步不是递归而是一次彻底的点集预处理。二维 Delaunay 的基础要求是点不重合重复点会让缝合死循环共线点会让外接圆检查退化。排序前先去重排序后按序访问后续所有递归都建立在这一段连续的 std::vector 上。下面这段代码是常见的预处理写法我把它作为所有实现的入口函数struct Point { double x, y; int id; // 保留原始编号后期输出结果要对回原数据 }; bool cmpXY(const Point a, const Point b) { if (a.x ! b.x) return a.x b.x; return a.y b.y; } std::vectorPoint preprocess(std::vectorPoint input) { std::sort(input.begin(), input.end(), cmpXY); input.erase( std::unique(input.begin(), input.end(), [](const Point a, const Point b) { return (a.x b.x) (a.y b.y); }), input.end()); return input; }这里的排序键是 x 优先、y 次之目的是让递归分割每次都能在空间上分成左右两块。如果 x 相同的点扎堆比如刻意对齐的测点网可以换成 Morton 编码排序能减少细长接缝的发生概率。unique 的去重只把距离为 0 的点干掉浮点噪声造成的“伪重复点”不归这段管需要配合后面的坐标归一化一起处理。参数说明里最值得注意的就是 id 字段。很多实现图省事直接用数组下标当顶点编号但后续做地形分析和数据库回写时往往要知道每个三角形的顶点来自原始数据的哪个点这个 id 在预处理阶段就要带上。3.2 递归分割叶节点最小三角网与子网格表示排序完成后就可以递归。叶子大小的选择我用 816 个点太少会增加归并层数太多会导致叶子内部用逐点插入时耗时上升。递归不返回网格对象而是返回一个既包含顶点区间又包含三角形结果的自定义 Mesh 结构Mesh 内部只存三角形索引表不复制顶点。class Mesh { public: std::vectorint vertices; // 顶点数组下标 std::vectorTriangle triangles; // 本子网内的三角形 }; Mesh buildLeaf(const std::vectorPoint pts, int lo, int hi) { Mesh m; if (hi - lo 1) { // 单点不建网归并时作为退化子网处理 m.vertices.push_back(lo); return m; } // 16 点以内直接用逐点插入建初始网稍后在归并阶段修复 m simpleTriangulate(pts, lo, hi); return m; } Mesh divideAndConquer(const std::vectorPoint pts, int lo, int hi) { if (hi - lo leafSize) { return buildLeaf(pts, lo, hi); } int mid (lo hi) / 2; Mesh left divideAndConquer(pts, lo, mid); Mesh right divideAndConquer(pts, mid, hi); return merge(left, right, pts); }leafSize 出现在这里就是第一个核心参数。我会在下一章单独讲它怎么调这里只说明行为叶子内部的三角化用简单逐点插入即可因为规模小O(n²) 也无关紧要。如果你的数据在局部呈现高度共线的特征比如沿等高线采集的密集点建议把 leafSize 调低到 8叶子越小归并阶段处理共线的能力越早介入。注意这里的分割点用的是数组下标 mid 而不是按 x 中间值。数组下标从排序后和 x 单调一致所以 mid 两侧天然是左右两块这是分治归并能保持线性局部性的核心。3.3 上下公切线缝合两个子三角网的核心归并步骤两个子网格 merge 的第一步都在找公切线。找上切线和下切线的过程对称上切线要求左子网所有点和右子网所有点都在这条边的同一侧下方从候选边出发不断旋转。旋转方向是顺着各自凸包的行走方向移动端点不是全量扫描这样整个寻找过程的代价是 O(leftBoundary rightBoundary)。// 返回左子网的右链上和右子网的左链上的公切线 Segment findUpperTangent(const Mesh L, const R) { int i L.rightmostIndex(); // 左子网最右顶点 int j R.leftmostIndex(); // 右子网最左顶点 while (true) { bool moved false; // 当前切线 i-j检查左子网是否有点在切线上方 while (L.convexChainHasAbove(i, j)) { i L.nextOnUpperChain(i); // 沿着左子网凸包向上走 moved true; } while (R.convexChainHasAbove(i, j)) { j R.nextOnUpperChain(j); // 沿着右子网凸包向上走 moved true; } if (!moved) break; } return Segment(i, j); }这段代码里的 convexChainHasAbove 不是遍历子网所有顶点而是只检查凸包上与当前候选边相邻的一两个顶点。因为左右凸包链已经成形旋转条件只在边界点之间传播。很多实现把这一检查写成了全点扫描局部操作变成了 O(n)整个归并直接退化这是分治归并最容易写崩的地方。找到上下切线后缝合的主体是从下切线出发沿着左子网右边界和右子网左边界交替前进每走一步构造一个新的三角形然后对新产生的共享边立即做 LOP。3.4 局部优化与数据导出LOP 闭环缝合边后网格还不是 Delaunay必须对每条新边执行局部优化检查公共边两侧的两个三角形如果一侧的顶点落入另一侧三角形的外接圆内就翻转这条边。翻转可能破坏相邻边的性质所以要放进队列反复处理直到队列空。void legalize(Mesh m, int edgeIdx, std::queueint checkList) { if (!m.edgeHasTwoTriangles(edgeIdx)) return; int a m.edgeA(edgeIdx), b m.edgeB(edgeIdx); int c m.triangleVertexOpposite(edgeIdx, 0); int d m.triangleVertexOpposite(edgeIdx, 1); if (isInCircumcircle(m.point(a), m.point(b), m.point(c), m.point(d))) { m.flip(edgeIdx); // 翻转后共享边改变 checkList.push(m.edgeOfTriangleChanged(edgeIdx, 0)); checkList.push(m.edgeOfTriangleChanged(edgeIdx, 1)); } }isInCircumcircle 建议用行列式判定不要取外接圆圆心再算半径后者一次减法就可能把浮点误差放大。翻转传播是分治归并里少数需要“循环到空”的操作但每次翻转影响的边只限当前三角形相邻的边总体平均次数很低不影响复杂度。整个子网格合并完毕后把三角形索引表直接 append 到下一层的 Mesh 里。注意 append 后不要重新整理边界链每层归并只维护本层左右子网的凸包链上一层归并会自动重新计算。把这一步做对后面跑百万点才会顺。4. 三个必调参数与内存分配策略百万级点云的关键4.1 leafSize 分割阈值叶节点该塞多少点leafSize 直接决定递归树的高度和叶子内部的工作量。太小的叶子会让归并次数变多虽然每层线性但函数调用和队列管理的常数会累积太大则叶子内用简单逐点插入的时间上升尤其局部点比较密集时二次代价明显。我通常的做法是先定 16然后跑一次目标数据集的代表子集观察生成耗时变化。主流参数区间如下数据集规模推荐 leafSize原因 10 万点816叶子小点减少缝合负担10 万100 万1632平衡递归深度与叶子代价 100 万且分布匀称16归并层级更多缝合占主导调参的方法不是看总时间而是分别统计叶子建网和归并缝合两个阶段的耗时。叶子占比过高就把 leafSize 调大缝合占比过高就调小。注意 leafSize 是“点数量”而不是“空间尺寸”两个维度上密度悬殊的点云固定叶子数量比固定叶子面积更稳定。4.2 坐标量化与精度float/double/归一化的三选一TIN 生成对坐标精度要求不高但对外接圆判定要求很高。float 类型在归一化后的单位盒子里尚可略过归一化直接存经纬度或大型工程坐标时百万级坐标的高低位差会让行列式判定结果完全失真三角形翻转方向反着来网格直接变形。double 比 float 安全一个量级但仍然建议做一次归一化。常见的做法是先求所有点 x、y 的整体包围盒把坐标线性映射到 [0,1] 区间生成完成后再用逆映射写回原始坐标。这一步对最终几何数据无损但能显著减少浮点误差对 Delaunay 判定和 LOP 翻转的影响。我一般会在预处理函数里带上包围盒结构进排序前先做平移缩放。归一化之后重复点的判定也有了意义。原本相距不足 1e-12 的两个点在原始坐标下可能被视为不同归一化后能被 unique 正确判断。如果你做的是地理坐标注意把经度、纬度分别归一化到不同范围或者先把大地坐标转成平面投影否则量纲差异会让“空圆”变形。4.3 顶点缓冲预分配与半边结构避免内存碎片和指针跳跃分治归并最大的隐性性能杀手是内存分配。三角形表、边表在归并中不断增长如果每次 push_back 都触发 realloc百万点会频繁复制整块缓冲区时间呈非线性增长。我的处理是预估三角形总数任意二维 Delaunay 三角网的三角形数 T 满足 T 2V - 2 - BB 是凸包顶点数V 是有效顶点数。所以一开始就 reserve 一个 2 * V 的三角形容量稳够。对于邻接关系不推荐用指针互相指的三角网结构而是用“三角形索引数组 邻接表”的半边思想。每个三角形存三个顶点和三个邻居三角形编号查邻边时按编号访问不会产生指针跳转。缝合和 LOP 都只需要在固定大小的数组上读写cache 友好程度比指针结构高一个档次。如果顶点分布极不均匀凸包上点数很少内部点很多三角形数接近 2V预分配 2V 稍紧我会再乘 1.1 留余量。内存池如果要做只需把所有三角形结构体放进一个连续数组用空闲链表复用被翻转边删除的槽位避免碎片。5. TIN 生成的避坑指南四类典型问题的现象与排查5.1 重复点导致缝合死循环现象、原因与去重现象merge 函数在某个点位来回转程序卡住不动或者生成的三角形里出现退化三角形面积接近零但边长正常导致后续体积计算直接翻车。原因排序后数组里有坐标完全相同的点分治时它们可能被分到左右两个子网缝合寻找公切线时两条直线重叠旋转条件永远无法收敛形成死循环。解决预处理阶段必须先用排序 unique 去重。去重时机必须在排序后、递归前不要指望生成阶段处理。如果原始数据有稀疏的重复噪声比如两个点相距不足 1e-10可以在归一化后做一次“近似去重”把落入同一格网单元的点合并为一个。5.2 共线点导致三角形退化现象、扰动与保留策略现象LOP 检查外接圆时出现 NaN或者翻转在一条直线上反复横跳最终生成的三角形有零面积。原因三点共线时外接圆退化isInCircumcircle 的行列式值为 0判断方向不明。等高线上的坐标点最容易触发因为大量采集点天然落在同一条线上。解决两个方向。一是对退化判定做容差处理行列式绝对值低于某个阈值通常 1e-10就跳过翻转二是在预处理时检测连续三点共线把中间点微扰到垂直于共线方向 1e-9 的位置。我的经验是数据量小于 50 万时优先做微扰大于 50 万时应该用容差跳过因为每条绳子上的点一多扰动点会影响后续插值精度。5.3 递归深度过大导致栈溢出现象、原因与显式栈改造现象程序跑了一段时间后崩溃调用栈显示在递归函数内部数据量大小和崩溃阈值有关但点越多越容易触发。原因分治递归深度是 log₂(n)百万点约 20 层理论上不深。但很多实现把 Mesh 大对象、vector 缓冲区放在栈上每层函数栈帧可能吃掉几十 KB再加上编译器默认栈大小就出事了。解决不要优化递归直接把递归改成显式栈。把待处理的区间 [lo, hi] 压进 std::vector 循环弹出、分割、再压入归并阶段用逆序弹出来强制先处理完子树。这样栈上的东西只有循环体和 Range 结构体内存占用恒定。改完后 500 万点也不会再爆栈。5.4 坐标范围过大导致浮点精度抽风现象、原因与单位盒归一化现象生成的 TIN 在位相上看起来没问题但把三角形顶点坐标输出后再算面积和原始点云对不上误差随坐标值增加变大且只出现在远离原点的一侧。原因double 有效位数约 1516 位当 x 坐标在 1e7 量级时1 米的差异占位很少外接圆判定的行列式计算差值被大数吞掉LOP 翻转方向错误。解决预处理阶段计算包围盒把坐标整体平移到原点附近再缩放到 [0,1]生成完成后用仿射变换写回。注意平移和缩放是几何变换不改变 Delaunay 性质但能极大改善数值稳定性。如果你的数据本身就是投影坐标尽量保留 double并首选平移而不是直接缩放。6. 一个容易忽略的提速细节用顶点守恒与对拍验证分治实现分治归并实现完后很多人第一件事是直接跑大数据看耗时我建议先做一次正确性验证用数学上的顶点守恒公式兜底比看一万个三角形的截图可靠得多。对于一个连通的平面三角网顶点数 V、凸包顶点数 B、三角形数 T 满足 T 2V - 2 - B。我用一段简单的 Python 脚本对生成结果做检查def euler_check(vertex_count, triangle_count, hull_count): expected 2 * vertex_count - 2 - hull_count if triangle_count ! expected: print(fFAIL: triangle{triangle_count}, fexpected{expected}) return False print(OK: vertex conservation holds) return True这个检查有两个用途。一是抓缝合漏边左右子网合并时如果少构造了一个连接三角形T 会比期望值小二是抓重复三角形某些退化实现会把同一个三角形写两遍T 反而偏大。两处都指向归并阶段配合断点调试很高效。再做一个对拍取 5 万点左右的子集用最简单的逐点插入实现生成三角网和分治归并的结果做集合比较。两者都是 Delaunay三角形集合应该完全一致不考虑三角网的方向差异。对拍脚本我习惯把每个三角形按顶点排序后写成字符串哈希再比对两个集合的差异只要集合相等就说明缝合和 LOP 逻辑正确。这部分验证通过后再看性能才有意义。我自己吃到的一次教训是一开始觉得验证浪费时间直接上百万数据跑出结果很漂亮但某块地形的水深算出来和实测差一大截回头查才发现是凸包顶点数 B 计算错了一位导致缝合处少了一条边整个流域体积全部偏移。从那之后我养成的习惯是任何改动都先跑一次顶点守恒再决定要不要看耗时。分治归并这类算法逻辑已经很复杂性能优化的前提是确认边界缝合没出错这一步省不了。希望帮到你。本文还有配套的精品资源点击获取