简介：面向TIN不规则三角网的高效构建需求，这套基于VC6.0的完整工程实现了被称为“最快”的Delaunay三角网生成算法，提供可直接编译运行的C++源码及演示程序，适合GIS、测绘、地形可视化与计算机图形学方向的开发者学习或二次复用。资源共88个文件，压缩包仅769KB，核心代码由13个头文件与13个C++源文件组成，涵盖CTriangle、CEdge、CVertex等关键数据结构；同时包含obj、sbr、pdb等编译过程文件以及exe可执行演示，便于在Visual C++ 6.0中打开工程并对照调试。从输入对话框、绘制信息模块可以看出，项目不仅实现了算法内核，还附有点集输入、三角网渲染与结果显示等完整示例，有助于理解Delaunay剖分中顶点插入、边翻转、三角网更新等核心步骤，并可在Debug/Release两种模式下比较运行效率。目前已有1318人浏览学习，适合欲深究快速TIN算法原理、或需要将算法移植到新项目的开发者参考借鉴。
1. 最快的 TIN 三角网生成算法：先别急着写代码
无人机航测或地面激光扫描得到的点云，动辄几十万上百万个点；让这些点变成 TIN 三角网，是等高线绘制、填挖方计算、地质建模共同的第一道工序。所谓最快的 TIN 三角网生成算法，不是一个固定的程序名，而是选型、数据结构和浮点处理的组合拳。同一个数据集，有人十几秒出结果，有人要等两分钟，差的就是这套组合拳里的细节。这篇笔记先讲怎么选算法，再给出一个最小实现骨架，最后把我在实践里反复踩过的坑一起说透。适合手里已经有点云数据、正被生成耗时折磨的开发者；如果你的数据只有几千个点，读到这里可以先跳过，十万点以上，后面内容会直接变成你的参考路径。
2. 分治 vs 增量：先立住“最快”的算法选型
2.1 空外接圆判据：一条公式决定正确与速度
TIN 三角网的标准骨架是 Delaunay 三角网：任意一个三角形的外接圆内，不包含点集中的其他点。这个“空外接圆判据”是几乎所有生成算法的总开关。判断流程通常是两步：先确定三个顶点是逆时针排列，再做圆内/圆外检测。别看它只有一行行列式，它同时决定结果正确性和速度——点接近共圆时符号出错的代价，是整个后续逻辑全乱。
我在实际项目里见过最快也最惨的错误：判据里用了不精确的比较，导致该翻转的边没翻，不该翻的边翻了。于是一条错误的边一直留在三角网里，后续合并和查找全部错位，速度随之崩坏。很多号称 O(n log n) 的算法跑成 O(n²)，不是算法不行，是判据没有给算法提供稳定输入。
所以结论先放在这：判据的正确性先于速度。先让空外接圆判据在“点接近共圆”时仍能给出正确符号，再去谈算法快不快。这一步省不了，否则后面所有优化都是给错误的网格加速。
2.2 分治法：为什么它是十万点以上最稳的“快”
分治法的思路很直白：点集先按 x 或 (x, y) 排序，从中间切一刀，左右两半分别三角化，再把两块沿交界缝合成一个完整的 Delaunay 三角网。缝合要做两件事：找到左右两个子集之间的公共切线，然后沿切线逐一加入新三角形，每加一步就查一次空外接圆性质，不满足就立即翻转。因为每一层每个点只参与常数次翻转，整体复杂度能做到严格的 O(n log n)。
工程上分治法另一个好处是内存访问模式稳定。点按排序后左右两半天然落在连续区间，合并时数据局部性好，缓存命中率高；在百万点随机分布数据上，稳定实现能压到秒级。这也是我常用它作基准的原因：不管最后选哪个算法，先用一个标准分治实现测出基线，后面的优化才有参照。
分治的代价是代码量。递归、合并、切线、翻转，每一部分都有边界条件。十万点以下，它不一定赢过实现良好的增量法，常系数摆在那；但数据一旦过了百万，复杂度的下限优势就会体现出来，增量的最坏情况是 O(n²)，随机分布也很难保证每次定位都在常数步内。
2.3 Bowyer-Watson 增量法：什么时候它能反超
增量法的流程更直观：先构造一个足够大的超级三角形，把全部点罩住；每插入一个新点，先定位它落在哪个三角形里，把那个三角形拆成三个新三角形，再从这三个三角形出发检查相邻三角形是否违反空外接圆判据，违反就翻转，直到局部满足 Delaunay 性质。
它快不快，几乎全看“定位”这一步。常见做法是把三角形按网格或四叉树索引，从点出发找三角形；当输入数据本身有空间顺序，比如扫描线顺序输出的点云，定位几乎就是 O(1)，整体速度能非常接近分治法。我实际见到的反超场景，往往是数据点在空间上有强相关性：增量算法利用上一轮留下的上下文，移动窗口式插入，缓存友好，常数小得惊人。
但增量法的翻车点也在定位和回溯。如果点坐标分布很随机，又只用一个不划分的全局三角形表去线性扫，每插一个点都扫大片三角形，百万点数据会慢到让人怀疑人生。即使有索引，当翻转链跨度很大时，递归回溯的代价也远高于分治的局部优化。总结成一条经验：十万点以下、数据有序，增量法更省事；百万点以上、随机分布，我宁愿选分治。
2.4 选型决策表：什么数据选什么算法
把上面几条放进一张表，边界一眼就能扫出来。
| 数据特征 | 推荐算法 | 理由 |
|---|---|---|
| 1 万点以下 | 增量法或直接枚举 | 常数小，实现短 |
| 10 万~100 万，随机分布 | 分治法 | 严格 O(n log n)，行为稳定 |
| 10 万~100 万，扫描线有序 | 增量法配网格索引 | 定位 O(1)，缓存命中好 |
| 大量共线、重复点 | 先排序去重，再走主算法 | 判据稳定性是前提 |
| 需要增量更新结果 | 增量法 | 局部修改，不用全量重建 |
这套选型不是拍脑袋。理论复杂度相同时，常数、内存布局和退化点处理决定胜负。算法选型这一关过了，后面实现才有意义；选错了，后面再怎么调参都是给一辆跑偏的车换轮胎。
3. 把分治法写成能跑的最小 TIN 生成器：数据结构、递归与归并
这里给一个最小实现骨架。我常用 Python 讲逻辑，因为可读性好、能直接跑；生产环境建议换 C++ 或 Rust，数据结构思路完全一致，后面我也会点出工程版要改的地方。
3.1 数据结构：点数组与三角形数组，别用对象链表
三角网生成里最隐性的坑，是把每个三角形建成独立对象、再用指针互相指。每次翻转要改三四个指针，合并时还要从链表头找邻居，日积月累就是慢。数组顺序存储才是正解。
class Vert: __slots__ = ("x", "y", "idx") def __init__(self, x, y, idx): self.x = x self.y = y self.idx = idx class Tri: __slots__ = ("v0", "v1", "v2", "nb0", "nb1", "nb2") def __init__(self, a, b, c): self.v0, self.v1, self.v2 = a, b, c self.nb0 = self.nb1 = self.nb2 = None每个三角形存三个顶点和三个邻居。邻居不带左右区分，按顺序对应：nb0是v0-v1这条边对面的三角形，nb1对应v1-v2，nb2对应v2-v0。合并操作里最高频的动作是“拿到一个三角形，沿某条边找邻居再走过去”，这个结构一次就能查到。
参数说明：顶点idx保留原始点编号，最后写回结果时要靠它。三角形类的六个引用不要省，很多实现因为“只存顶点、需要时全图搜索”而直接拖慢 LOP 阶段。工程版我建议把六个引用改成三个整数索引数组，顶点坐标再用两个单独的浮点数组存放，缓存能再上一个台阶。
3.2 预处理：排序、去重、再谈递归
分治的第一步不是递归，而是预处理。我在同一段逻辑里做排序和去重，一并返回去重后的新数组。
def prepare(pts): pts = sorted(pts, key=lambda p: (p.x, p.y)) # x 主序，y 次序 uniq = [] last = None for p in pts: if last and last.x == p.x and last.y == p.y: continue # 精确比较去重 uniq.append(p) last = p return uniq按 (x, y) 字典序排序，能让后续递归切分天然产生空间连续性。分治所有性能都建立在“切开的两个子集各占连续内存段”之上，排序这一步宁可多花几十毫秒，也要保证后面的局部性。
去重是关键中的关键。重复点进入三角网会生成零面积三角形，空外接圆判据在这种面上退化，翻转逻辑会变成来回循环的鬼打墙。这里用精确比较，不吃 epsilon；坐标来自采集端时通常已经整理过，直接按明文去重即可。
3.3 切分与基线条件：小于等于多少点就暴力
递归终止条件不是 n==1，而是一个阈值。点足够少时，直接枚举所有三点组合，用空外接圆判据筛出合法三角网，比继续递归更快。
MIN_T = 12 def triangulate(pts): n = len(pts) if n <= MIN_T: return brute_force_tri(pts) # 枚举三点组合，保留 Delaunay 边 k = n // 2 left = triangulate(pts[:k]) right = triangulate(pts[k:]) return merge(left, right, pts, k)阈值取 12 是我常用的起点。太小，递归层数多，函数调用和数组切片开销浪费；太大，暴力枚举的排列组合又会吞掉收益。我试过 8 到 20 之间差别不大，从 12 开始调没问题。
这段代码还要注意切片开销：pts[:k]在 Python 里是复制数组，并未共享内存。工程版我只传(start, end)区间，避免每层复制。分治递归深度大约是 log2(百万)≈20 层，栈没有风险，真正的风险在归并层，下面细说。
3.4 合并与 LOP：快慢分水岭在这里
归并函数是分治实现真正的难点。两半递归各自生成了三角网，合并要做三件事：找下切线、沿切线推进、对每条新边做局部优化。合并骨架的示意代码如下。
def merge(left, right, tris): L, R = lower_tangent(left, right) # 左右子集的下侧公切线 while True: cl = next_cand_left(left, L, R) # 左侧候选点 cr = next_cand_right(right, L, R) # 右侧候选点 if cl is None and cr is None: break # 到达上切线，合并结束 # 右候选若落入左候选的外接圆，右候选更优；否则左候选更优 if cr is not None and (cl is None or inside_circle(R, L, cl, cr)): add_triangle(L, R, cr) R = cr else: add_triangle(L, R, cl) L = cl local_optimize(L, R, tris) # 对邻接边做 LOP 翻转inside_circle(R, L, cl, cr)的含义是：以 R、L、cl 三点做外接圆，判断 cr 是否落在圆内。若 cr 在圆内，说明 cl 对应的三角形不满足空外接圆判据，要用 cr 这一侧前进。这个方向在教科书里经常一句话带过，实际编码时最容易写反，写反的后果就是合并不收敛，程序卡死在同一组边上。
local_optimize就是 LOP：加入新三角形后，检查它对侧的三角形，如果对侧顶点落入新三角形外接圆，就翻转公共边，翻转后可能波及下一条邻接边，于是循环检查直到局部全部合法。LOP 是 O(1) 的局部操作，实现时别把它写成全图搜索，否则分治的复杂度优势就白搭了。
注意：上面是教学骨架，去掉了几何边界判断。生产实现里，
next_cand_left和next_cand_right要顺着凸包链走，每走一步都要用一次方向判据确认“线两侧不再有点”，这是合并步最容易漏的环节。
4. 三角网生成避坑笔记：五个必踩的坑和排查方法
4.1 外接圆漏判与三角形撕裂：浮点误差在作怪
现象：一百万个点跑完，局部检查发现少了几条边，三角形互相穿过，面积出现负值。
原因：空外接圆判据用 double 直接算行列式，共圆或近共圆时符号被舍入误差反转。该翻的边没有翻，后续邻接关系就按错误网格传播，越传越乱。
解决：把空外接圆判据统一成一个独立函数，不内联散落。先用 double 算，当行列式绝对值接近零（比如小于 1e-12，或相对机器精度的数十倍），落回扩展精度重新算一遍。这个分支在普通数据上基本进不去，几乎不影响性能，却能把稳定性拉回正轨。
4.2 递归栈溢出：百万点退化成一条直线
现象：普通数据跑得好好的，换成沿道路扫描的窄长条点云后，程序直接栈溢出。
原因：分治按 x 切分，但窄长条点云排序后“左半”和“右半”贴在同一侧，子集仍然严重共线，三角形退化，合并时切线找来找去找不到，归并又套递归，栈就越压越深。
解决：排序时用 (x, y) 字典序；切分阈值往上调到 16 或 32，让退化点集在更早的暴力阶段结束；平台栈浅就改成显式工作栈。这个坑一踩就是大半天，建议开发期先拿窄长数据测一轮，再谈百万点。
4.3 重复点与共线点：现象随机、原因明确
现象：同样一版数据，有时少几个三角形，有时多出几条零面积边，结果不稳定。
原因：重复点没被预处理干掉；共线点让多个三角形同时符合“空外接圆”判据，同时进入候选集，翻转循环在等价解之间来回试错。
解决：预处理阶段严格去重；遇到共线点，按“只选第一个进入决策”的策略处理，LOP 阶段用“严格大于 0 才翻转”来终止循环。这个“严格大于 0”是许多实现翻车的静默点，用>=的话，边界会反复触发翻转，结果就是看着正常、实际慢一倍。
4.4 合并桥架错：起始点选错导致死循环
现象：合并函数卡住，日志停在同一条切线边上反复打印，手动中断才发现程序没退出。
原因：找下切线时，起点选了左子集的任意边界点或右子集的任意边界点；两点连起来的那条线并没有真正把两个点集分开，候选点始终落在线的错误侧，循环来回换边，永远不收敛。
解决：找切线时先各自取凸包边界链，从最左、最右端点出发往下走；每一步用一次方向判据确认“所有点都在连线同侧”，这个方向判断单独写成一个函数。死循环九成出在切线方向，先打印 L、R 坐标，再打印方向判据结果，五个排查能命中三个。
4.5 比增量法还慢：把分治写成了伪分治
现象：理论上是分治，实际测出来比 Bowyer-Watson 慢一倍，百万点跑了四十秒。
原因：切片用复制、每层都拷贝数组；合并时又全图扫描寻找候选点；LOP 也是全局搜索。本质上复杂度已经回到 O(n²)，只是披着递归的外壳。
解决：用偏移量加长度传子区间；候选点只从前一步邻接三角形里找，别扫全子集；LOP 每翻一条边都要快速找“对面”，翻得慢就回头查邻接字段是否维护错位。分治法的面子是递归，里子是局部性，局部性丢了，不如改用增量法。
5. 验证阶段：用三张表检验“快”和“对”，再谈落地
5.1 对照验证：先证明没生成错
跑通第一版后别急着测时间。我习惯与现成三角化实现做对照：三角形数量、凸包顶点顺序、随机采样点的邻接关系。两份输出可能不完全一致，但三角形总数和凸包必须一致。若数量差一两个，多半是退化点处理差异；若数量级都对不上，说明结构有根本问题。对照这一步看起来笨，却最省时间，因为后面所有速度测试都建立在“正确”的前提上。
5.2 规模曲线：从 1 万到 100 万点的耗时趋势
测速只看一组数据没有意义。我按 1 万、5 万、20 万、100 万四个规模测同一份随机数据，看时间曲线是否近似 n log n；若 100 万点出现悬崖式拉长，大概率是索引或数据结构在某个规模上退化。
| 数据点数 | 分治实现耗时（参考） | 健康度判断 |
|---|---|---|
| 1 万 | 约几十毫秒 | 正常 |
| 5 万 | 约几百毫秒 | 正常 |
| 20 万 | 约 1~2 秒 | 留意是否陡增 |
| 100 万 | 约 5~10 秒 | 应接近 n log n 趋势 |
这个表的绝对数值在每台机器上都不一样，别把它当标准；重点看趋势：从 5 万到 100 万，耗时不应出现几十倍的跳变。
5.3 不变量：三角形数量守恒与空圆抽查
我每次调参后都会跑两条不变量。第一，核对欧拉关系：去重后点数 n、凸包顶点数 h，三角形数 t 必须满足 t = 2n - 2 - h，差一个数都说明邻接没缝上。第二，随机抽十万条边，对每条边取对侧三角形顶点，重跑空外接圆判据，违规比例应接近零。这两条能兜住绝大多数“看着对、实际错”的结果。
5.4 落到生产前的三个小改造和习惯
验证之后真要做生产版本，我还会做三件事：把坐标减掉包围盒左下角转成相对值，让数值量级集中在 1e-5 到 1e6 之间；把递归里的数组切片改成(start, end)区间；把三角形邻居的六七个引用换成三个整数索引。这三件事不改算法逻辑，但能让 C++ 或 Rust 版本里的缓存命中和向量化顺利很多。
到这一步，才能真正放心去优化“最快”：先有正确基线，再有规模曲线，最后做硬件级优化。我自己的习惯是把对照脚本、规模曲线和不变量检查写成同一个测试程序，跑一次出一张报告，一切调参都用同一套报告比对。这个习惯让我少走了很多弯路，也希望帮到你。
本文还有配套的精品资源，点击获取
