简介这份资源面向计算机图形学、GIS 与测绘方向的开发者及学生提供一套基于 VC6.0 实现的快速 TIN 三角网生成算法工程可用于地形建模、点云网格化与 Delaunay 三角剖分等场景的学习与二次开发。压缩包共 88 个文件约 769KB以 13 个 cpp 与 13 个 h 源文件为核心涵盖顶点、边、三角形、三角网及节点树等类实现另含 obj 编译产物、exe 可执行程序、rc 资源脚本与 dsp/dsw 工程文件可直接用 VC6.0 打开编译运行。资源已有 1320 人学习下载工程结构完整、模块划分清晰读者可从中理解三角网构建的数据组织方式与核心算法流程并在此基础上进行调试、改造或移植适合作为算法学习与课程设计的参考实现。1. 一个把“最快”写进标题的 TIN 生成器到底快在哪第一次看到“最快的 TIN 三角网生成算法”这个标题我的反应是怀疑。三角网构建这块增量插入、分治、扫描线几类思路早就被翻来覆去研究过敢在标题里直接挂“最快”两个字要么是标题党要么是真在某个环节上做了取舍。把源码包拉下来翻了一遍结论偏向后者它没有追求通用场景下的全面最优而是把 VC6.0 这个老编译环境下的内存布局和浮点比较开销压到了很低用一套紧凑的点结构加边翻转策略把 Delaunay 三角网的构建过程跑得很干脆。这份资源适合两类人一类是手里有离散点云、高程点、钻孔点需要快速铺出一张不规则三角网做地形建模或等值线起点的开发者另一类是还在维护 VC6.0 老工程、需要往里面塞一个不依赖第三方库的三角网模块的人。它不依赖 CGAL、不依赖 Boost纯 C 实现编译门槛低到一台装了 VC6.0 的机器就能开工。下面按“能干什么 → 怎么跑 → 核心怎么实现 → 怎么改”的顺序拆。2. 项目定位与技术选型为什么是纯 C 加 VC6.02.1 这个 TIN 模块解决的是什么问题TINTriangulated Irregular Network不规则三角网的本质是把一堆散乱的点连成互不重叠的三角形并且尽量让三角形形状均匀、避免狭长三角形。工程上最常用的约束是 Delaunay 准则任意三角形的外接圆内不含其他点。满足这个准则的三角网在插值、坡度计算、体积估算时数值表现更稳。这个项目做的就是“给一批二维点输出一张满足 Delaunay 性质的三角形列表”。输入是点坐标数组输出是三角形索引三元组。它不负责点云去重、不负责边界裁剪、不负责高程插值这些都在调用方做。定位很清晰一个可嵌入的三角剖分内核。2.2 技术栈与目录结构从源码包的构成看这是一个典型的 VC6.0 时代的 C 工程没有 CMake没有 Makefile靠 .dsp/.dsw 工程文件组织。核心文件大致是这么几类文件/目录作用主工程文件.dsp/.dswVC6.0 工程配置指定编译选项和文件列表点与边结构定义头文件定义顶点、边、三角形的数据结构三角网构建实现文件增量插入、边翻转、外接圆判定等核心逻辑测试/演示入口构造样例点集调用构建接口输出三角形数据文件可选示例点坐标供演示程序读取这种结构放在今天看很朴素但好处是零依赖、编译快、移植到别的 C 工程时只需要拷几个 .h/.cpp。我一般会把核心实现文件和头文件单独拎出来塞进自己的工程演示入口只作参考。2.3 为什么选 VC6.0 而不是现代工具链这不是技术先进性的选择是历史包袱的选择。VC6.0 对 C 标准的支持停留在很早期的阶段模板、STL 都有坑所以这类工程通常刻意避开 STL 容器用手写数组和指针管理内存。代价是要自己管扩容和释放收益是编译产物小、运行时不引入额外抽象层开销。如果你的工程已经迁到 VS2019 或 GCC源码基本能直接编但要注意 VC6.0 下的一些写法比如 for 循环变量作用域、旧式类型转换在新编译器下会报警告改起来不费事。提示VC6.0 工程文件不能直接被新版 Visual Studio 打开需要新建空工程再把源文件加进去或者用“升级向导”转换。转换后重点检查for (int i...)这类变量作用域差异。3. 跑起来从编译到看到第一张三角网3.1 环境准备与工程打开最省事的路径是找一台还能跑 VC6.0 的环境直接双击 .dsw 打开。如果手头只有新版 Visual Studio就新建一个 Win32 Console 空工程把核心 .cpp 和 .h 全部加入再把演示入口的 main 函数保留。编译选项上VC6.0 默认的字符集和运行时库一般不用动但如果遇到fopen相关警告把运行库统一成多线程静态库即可。命令行编译的话用 cl 直接编cl /EHsc /O2 tin_build.cpp demo_main.cpp /Fe:tin_demo.exe/O2是必须加的这类几何算法在不开优化时慢得离谱开了之后差距能到数倍。/EHsc是标准异常处理开关老代码里如果没写异常加不加都能过加上更稳。3.2 构造输入点集并调用构建接口演示入口通常长这样准备一个点数组调用构建函数拿到三角形索引后打印或写文件。下面是我按项目接口风格还原的一段调用代码变量名按实际源码调整#include tin_build.h int main() { // 构造一批散乱点实际项目里从文件或点云读入 const int N 6; double xs[N] {0.0, 1.0, 2.0, 0.5, 1.5, 1.0}; double ys[N] {0.0, 0.0, 0.0, 1.0, 1.0, 2.0}; TINBuilder builder; // 逐点插入内部维护三角形链表 for (int i 0; i N; i) { builder.AddPoint(xs[i], ys[i]); } // 取出三角形索引每三个一组 const int* tris builder.GetTriangles(); int triCount builder.GetTriangleCount(); for (int t 0; t triCount; t) { printf(%d %d %d\n, tris[t * 3 0], tris[t * 3 1], tris[t * 3 2]); } return 0; }这段代码的关键在AddPoint的调用顺序增量式构建对插入顺序敏感点集如果已经按空间排序插入效率会明显不同。GetTriangles返回的是扁平化的索引数组每三个 int 构成一个三角形索引对应AddPoint的调用次序。参数上没有花哨的东西就是 x、y 两个 double高程 z 不参与三角剖分只在后续插值时用。3.3 输出结果怎么验证跑通之后第一件事是验证三角形数量。对 N 个点、H 个凸包顶点Delaunay 三角网的三角形数满足T 2N - 2 - H。拿上面 6 个点举例如果凸包是 4 个顶点三角形数应该是12 - 2 - 4 6。数量对不上说明插入或翻转逻辑有问题。第二件事是检查有没有重复三角形和退化三角形三点共线。退化三角形面积接近零在后续插值时会产生除零。我一般会在输出后加一段面积过滤把面积小于阈值的三角形标出来作为调试信号。注意演示点集如果存在重复点或严格共线点增量插入可能进入异常分支。正式使用前先做一遍去重和共线检测比事后排查省事得多。4. 核心模块拆解增量插入与边翻转的完整链路4.1 数据结构点、边、三角形怎么组织这类追求速度的实现通常不会用std::vector存三角形而是用固定大小的结构体数组加空闲链表。顶点结构只存坐标和一条关联边半边结构或直接存索引三角形结构存三个顶点索引和三个邻接三角形索引。半边结构在遍历邻接关系时最快但内存占用高索引式结构省内存代价是查邻接要绕一下。按项目“最快”的取向我判断它用的是索引式三角形数组加邻接缓存。核心结构大致如下struct TINVertex { double x, y; // 平面坐标z 不参与剖分 int index; // 原始点序号用于输出映射 }; struct TINTriangle { int v[3]; // 三个顶点在顶点数组中的下标 int n[3]; // 三条边对应的邻接三角形下标-1 表示边界 bool alive; // 删除标记配合空闲链表复用 };alive标记加空闲链表是这类实现的常见做法边翻转和插入会产生大量临时三角形频繁 new/delete 会把性能拖垮改成预分配一大块数组、用标记位回收插入一万个点也不会有明显的内存抖动。n[3]缓存邻接关系让“找共享边的相邻三角形”从 O(T) 降到 O(1)这是边翻转能跑快的前提。4.2 增量插入定位包含点的三角形增量插入的第一步是找到新点落在哪个三角形内部。最朴素的做法是遍历所有三角形做点在三角形内测试复杂度 O(T)点一多就废。快一点的做法是维护一个三角形查找结构或者利用上一次插入的位置做“行走”walk从邻近三角形出发沿边跳转。行走法的逻辑是从某个三角形出发判断新点在它三条边的哪一侧如果都在内侧就命中如果在某条边外侧就跳到那条边的邻接三角形继续判断。代码骨架// 从 start 三角形出发行走定位包含点 p 的三角形 int LocateTriangle(int start, double px, double py) { int cur start; while (true) { TINTriangle t tris[cur]; int outside -1; for (int e 0; e 3; e) { // 有向面积判断点在哪一侧逆时针为正 if (Orient(t.v[e], t.v[(e 1) % 3], px, py) 0) { outside e; break; } } if (outside -1) return cur; // 三点内侧命中 cur t.n[outside]; // 跳到邻接三角形 if (cur -1) return -1; // 走到边界外点不在网内 } }Orient是二维有向面积用叉积算符号决定点在边的哪一侧。这里有个血泪经验浮点误差会让点恰好落在边上时符号抖动行走可能来回跳。常见做法是给 Orient 加一个极小容差绝对值小于容差时按“在边上”处理直接返回当前三角形后续插入时把点当作落在边上做特殊分裂。4.3 边翻转恢复 Delaunay 性质新点插入后把所在三角形一分为三然后检查新生成的三条边是否满足 Delaunay 准则。不满足就翻转翻转后可能影响相邻三角形用栈或队列做局部传播。判定准则是“对面顶点是否落在当前三角形的外接圆内”用行列式算// 判断点 d 是否在三角形 abc 的外接圆内 bool InCircumcircle(int a, int b, int c, int d) { double ax verts[a].x - verts[d].x; double ay verts[a].y - verts[d].y; double bx verts[b].x - verts[d].x; double by verts[b].y - verts[d].y; double cx verts[c].x - verts[d].x; double cy verts[c].y - verts[d].y; double det (ax * ax ay * ay) * (bx * cy - by * cx) - (bx * bx by * by) * (ax * cy - ay * cx) (cx * cx cy * cy) * (ax * by - ay * bx); return det 0; // 逆时针三角形下正值为圆内 }这个行列式是 3x3 展开把 d 平移到原点后算。det 0的符号约定依赖三角形顶点是逆时针排列如果实现里三角形方向不统一判定会整体反掉这是最容易翻车的地方。翻转本身只改两个三角形的顶点和邻接数组不新建三角形所以内存开销很小。传播时用栈存“待检查边”每次翻转后把受影响的两条边压栈直到栈空。局部性保证了这个过程平均只碰常数个三角形整体复杂度接近 O(N log N)。4.4 边界处理与凸包维护增量插入有个绕不开的问题新点如果落在当前凸包外行走会走到边界返回 -1。这时需要扩展凸包把新点和可见的边界边连成新三角形。实现上通常维护一个凸包顶点环插入外部点时找到两条切线把中间可见的边替换掉。这块是很多开源实现偷懒的地方直接要求输入点集先算好凸包、按凸包顺序插入。这个项目如果追求“最快”很可能也做了类似假设调用方保证点集在凸包内或者先做一次凸包预排序。使用时要留意接口注释如果没写清楚自己补一个凸包预处理更保险。5. 避坑与排查五个真实会卡住你的问题5.1 编译过了但运行崩溃在插入阶段现象点集稍大就在AddPoint里访问越界。原因多半是三角形数组预分配容量不够空闲链表用尽后没有扩容逻辑或者扩容后邻接索引没同步更新。解决在插入前按2N估算三角形上限预分配扩容时整体重建索引映射别只 realloc 数组。5.2 三角形数量对但形状全是狭长三角形现象输出能看但三角形质量极差。原因通常是边翻转没生效或者InCircumcircle的符号约定和三角形顶点方向不一致导致该翻的没翻。解决先固定所有三角形为逆时针再统一判定符号加一个断言检查每个三角形有向面积为正。5.3 点恰好落在已有边上导致死循环现象程序卡在LocateTriangle的 while 里。原因是有向面积在边上时符号抖动行走在两个三角形间来回跳。解决给 Orient 加容差落在边上时直接返回当前三角形插入逻辑走“边分裂”分支而不是“面分裂”。5.4 换到新版编译器后结果和 VC6.0 不一致现象同一批点老环境和新环境输出的三角形不同。原因是浮点运算顺序和 x87 扩展精度差异VC6.0 默认用 x87 80 位中间结果新版默认 SSE 64 位。解决统一编译选项新版加/fp:precise或者接受差异但保证两者都满足 Delaunay 准则用外接圆测试做验收而不是逐三角形比对。5.5 大规模点集内存暴涨现象十万点级别内存占用远超预期。原因是每个三角形存了完整邻接数组加标记位结构体偏大加上空闲链表只回收不缩容。解决把alive改成用v[0] -1表示省一个 bool 的对齐填充或者分块处理按空间网格切分点集分别建网再缝合边界。6. 二次开发把三角网内核接进自己的管线拿到这份源码多数人不是要跑演示是要把它嵌进自己的地形或点云管线。改造的第一步是剥离演示入口只保留构建类和数据结构把printf输出换成回调或直接返回索引数组。第二步是补一个点集预处理去重、剔除共线点、按空间排序希尔伯特曲线或网格排序都行排序后增量插入的行走距离会大幅缩短这是不改变算法本身就能拿到的提速。第三步是接口适配。原始接口大概率是AddPoint逐点插入如果你的数据是一次性给一整批可以加一个批量入口内部先排序再逐点插入对外仍然返回扁平索引数组。下面是一个适配层的写法// 批量构建先按网格排序降低行走距离再逐点插入 bool BuildTIN(const std::vectordouble xs, const std::vectordouble ys, std::vectorint outTris) { int n (int)xs.size(); std::vectorint order(n); for (int i 0; i n; i) order[i] i; // 按 x 分桶再按 y 排序近似空间局部性 std::sort(order.begin(), order.end(), [](int a, int b) { int ba (int)(xs[a] * 16), bb (int)(xs[b] * 16); if (ba ! bb) return ba bb; return ys[a] ys[b]; }); TINBuilder builder; std::vectorint remap(n); for (int k 0; k n; k) { remap[k] builder.AddPoint(xs[order[k]], ys[order[k]]); } const int* tris builder.GetTriangles(); int cnt builder.GetTriangleCount(); outTris.resize(cnt * 3); for (int i 0; i cnt * 3; i) { // 把内部索引映射回原始点序号 outTris[i] order[tris[i]]; } return true; }这里的关键是remap和order的双向映射内部按排序后的顺序插入输出时再映射回调用方的原始序号否则拿到的三角形索引对不上你的点数组。排序桶宽16是经验值点密度高时调大密度低时调小本质是控制每个桶里的点数在一个常数附近。验证改造是否成功我习惯用三个指标三角形总数是否符合欧拉公式、所有三角形有向面积为正、随机抽若干三角形做外接圆测试确认无点落入。这三个检查写成单元测试每次改完跑一遍比肉眼看图靠谱。还有一个容易被忽略的点这份实现如果内部用了全局或静态缓冲区多线程调用会互相踩。要并行建网得把构建类改成无状态或每线程一个实例别图省事共享一个 builder。我早年在一个批量地形生成任务里就栽在这上面单线程跑得好好的一开多线程结果随机错乱查了两天才定位到静态数组。从那以后我每次接这类几何内核第一件事就是 grep 一遍全局变量和 static 局部变量确认没有隐藏的共享状态再谈并行。希望帮到你。本文还有配套的精品资源点击获取
简介这份资源面向计算机图形学、GIS 与测绘方向的开发者及学生提供一套基于 VC6.0 实现的快速 TIN 三角网生成算法工程可用于地形建模、点云网格化与 Delaunay 三角剖分等场景的学习与二次开发。压缩包共 88 个文件约 769KB以 13 个 cpp 与 13 个 h 源文件为核心涵盖顶点、边、三角形、三角网及节点树等类实现另含 obj 编译产物、exe 可执行程序、rc 资源脚本与 dsp/dsw 工程文件可直接用 VC6.0 打开编译运行。资源已有 1320 人学习下载工程结构完整、模块划分清晰读者可从中理解三角网构建的数据组织方式与核心算法流程并在此基础上进行调试、改造或移植适合作为算法学习与课程设计的参考实现。1. 一个把“最快”写进标题的 TIN 生成器到底快在哪第一次看到“最快的 TIN 三角网生成算法”这个标题我的反应是怀疑。三角网构建这块增量插入、分治、扫描线几类思路早就被翻来覆去研究过敢在标题里直接挂“最快”两个字要么是标题党要么是真在某个环节上做了取舍。把源码包拉下来翻了一遍结论偏向后者它没有追求通用场景下的全面最优而是把 VC6.0 这个老编译环境下的内存布局和浮点比较开销压到了很低用一套紧凑的点结构加边翻转策略把 Delaunay 三角网的构建过程跑得很干脆。这份资源适合两类人一类是手里有离散点云、高程点、钻孔点需要快速铺出一张不规则三角网做地形建模或等值线起点的开发者另一类是还在维护 VC6.0 老工程、需要往里面塞一个不依赖第三方库的三角网模块的人。它不依赖 CGAL、不依赖 Boost纯 C 实现编译门槛低到一台装了 VC6.0 的机器就能开工。下面按“能干什么 → 怎么跑 → 核心怎么实现 → 怎么改”的顺序拆。2. 项目定位与技术选型为什么是纯 C 加 VC6.02.1 这个 TIN 模块解决的是什么问题TINTriangulated Irregular Network不规则三角网的本质是把一堆散乱的点连成互不重叠的三角形并且尽量让三角形形状均匀、避免狭长三角形。工程上最常用的约束是 Delaunay 准则任意三角形的外接圆内不含其他点。满足这个准则的三角网在插值、坡度计算、体积估算时数值表现更稳。这个项目做的就是“给一批二维点输出一张满足 Delaunay 性质的三角形列表”。输入是点坐标数组输出是三角形索引三元组。它不负责点云去重、不负责边界裁剪、不负责高程插值这些都在调用方做。定位很清晰一个可嵌入的三角剖分内核。2.2 技术栈与目录结构从源码包的构成看这是一个典型的 VC6.0 时代的 C 工程没有 CMake没有 Makefile靠 .dsp/.dsw 工程文件组织。核心文件大致是这么几类文件/目录作用主工程文件.dsp/.dswVC6.0 工程配置指定编译选项和文件列表点与边结构定义头文件定义顶点、边、三角形的数据结构三角网构建实现文件增量插入、边翻转、外接圆判定等核心逻辑测试/演示入口构造样例点集调用构建接口输出三角形数据文件可选示例点坐标供演示程序读取这种结构放在今天看很朴素但好处是零依赖、编译快、移植到别的 C 工程时只需要拷几个 .h/.cpp。我一般会把核心实现文件和头文件单独拎出来塞进自己的工程演示入口只作参考。2.3 为什么选 VC6.0 而不是现代工具链这不是技术先进性的选择是历史包袱的选择。VC6.0 对 C 标准的支持停留在很早期的阶段模板、STL 都有坑所以这类工程通常刻意避开 STL 容器用手写数组和指针管理内存。代价是要自己管扩容和释放收益是编译产物小、运行时不引入额外抽象层开销。如果你的工程已经迁到 VS2019 或 GCC源码基本能直接编但要注意 VC6.0 下的一些写法比如 for 循环变量作用域、旧式类型转换在新编译器下会报警告改起来不费事。提示VC6.0 工程文件不能直接被新版 Visual Studio 打开需要新建空工程再把源文件加进去或者用“升级向导”转换。转换后重点检查for (int i...)这类变量作用域差异。3. 跑起来从编译到看到第一张三角网3.1 环境准备与工程打开最省事的路径是找一台还能跑 VC6.0 的环境直接双击 .dsw 打开。如果手头只有新版 Visual Studio就新建一个 Win32 Console 空工程把核心 .cpp 和 .h 全部加入再把演示入口的 main 函数保留。编译选项上VC6.0 默认的字符集和运行时库一般不用动但如果遇到fopen相关警告把运行库统一成多线程静态库即可。命令行编译的话用 cl 直接编cl /EHsc /O2 tin_build.cpp demo_main.cpp /Fe:tin_demo.exe/O2是必须加的这类几何算法在不开优化时慢得离谱开了之后差距能到数倍。/EHsc是标准异常处理开关老代码里如果没写异常加不加都能过加上更稳。3.2 构造输入点集并调用构建接口演示入口通常长这样准备一个点数组调用构建函数拿到三角形索引后打印或写文件。下面是我按项目接口风格还原的一段调用代码变量名按实际源码调整#include tin_build.h int main() { // 构造一批散乱点实际项目里从文件或点云读入 const int N 6; double xs[N] {0.0, 1.0, 2.0, 0.5, 1.5, 1.0}; double ys[N] {0.0, 0.0, 0.0, 1.0, 1.0, 2.0}; TINBuilder builder; // 逐点插入内部维护三角形链表 for (int i 0; i N; i) { builder.AddPoint(xs[i], ys[i]); } // 取出三角形索引每三个一组 const int* tris builder.GetTriangles(); int triCount builder.GetTriangleCount(); for (int t 0; t triCount; t) { printf(%d %d %d\n, tris[t * 3 0], tris[t * 3 1], tris[t * 3 2]); } return 0; }这段代码的关键在AddPoint的调用顺序增量式构建对插入顺序敏感点集如果已经按空间排序插入效率会明显不同。GetTriangles返回的是扁平化的索引数组每三个 int 构成一个三角形索引对应AddPoint的调用次序。参数上没有花哨的东西就是 x、y 两个 double高程 z 不参与三角剖分只在后续插值时用。3.3 输出结果怎么验证跑通之后第一件事是验证三角形数量。对 N 个点、H 个凸包顶点Delaunay 三角网的三角形数满足T 2N - 2 - H。拿上面 6 个点举例如果凸包是 4 个顶点三角形数应该是12 - 2 - 4 6。数量对不上说明插入或翻转逻辑有问题。第二件事是检查有没有重复三角形和退化三角形三点共线。退化三角形面积接近零在后续插值时会产生除零。我一般会在输出后加一段面积过滤把面积小于阈值的三角形标出来作为调试信号。注意演示点集如果存在重复点或严格共线点增量插入可能进入异常分支。正式使用前先做一遍去重和共线检测比事后排查省事得多。4. 核心模块拆解增量插入与边翻转的完整链路4.1 数据结构点、边、三角形怎么组织这类追求速度的实现通常不会用std::vector存三角形而是用固定大小的结构体数组加空闲链表。顶点结构只存坐标和一条关联边半边结构或直接存索引三角形结构存三个顶点索引和三个邻接三角形索引。半边结构在遍历邻接关系时最快但内存占用高索引式结构省内存代价是查邻接要绕一下。按项目“最快”的取向我判断它用的是索引式三角形数组加邻接缓存。核心结构大致如下struct TINVertex { double x, y; // 平面坐标z 不参与剖分 int index; // 原始点序号用于输出映射 }; struct TINTriangle { int v[3]; // 三个顶点在顶点数组中的下标 int n[3]; // 三条边对应的邻接三角形下标-1 表示边界 bool alive; // 删除标记配合空闲链表复用 };alive标记加空闲链表是这类实现的常见做法边翻转和插入会产生大量临时三角形频繁 new/delete 会把性能拖垮改成预分配一大块数组、用标记位回收插入一万个点也不会有明显的内存抖动。n[3]缓存邻接关系让“找共享边的相邻三角形”从 O(T) 降到 O(1)这是边翻转能跑快的前提。4.2 增量插入定位包含点的三角形增量插入的第一步是找到新点落在哪个三角形内部。最朴素的做法是遍历所有三角形做点在三角形内测试复杂度 O(T)点一多就废。快一点的做法是维护一个三角形查找结构或者利用上一次插入的位置做“行走”walk从邻近三角形出发沿边跳转。行走法的逻辑是从某个三角形出发判断新点在它三条边的哪一侧如果都在内侧就命中如果在某条边外侧就跳到那条边的邻接三角形继续判断。代码骨架// 从 start 三角形出发行走定位包含点 p 的三角形 int LocateTriangle(int start, double px, double py) { int cur start; while (true) { TINTriangle t tris[cur]; int outside -1; for (int e 0; e 3; e) { // 有向面积判断点在哪一侧逆时针为正 if (Orient(t.v[e], t.v[(e 1) % 3], px, py) 0) { outside e; break; } } if (outside -1) return cur; // 三点内侧命中 cur t.n[outside]; // 跳到邻接三角形 if (cur -1) return -1; // 走到边界外点不在网内 } }Orient是二维有向面积用叉积算符号决定点在边的哪一侧。这里有个血泪经验浮点误差会让点恰好落在边上时符号抖动行走可能来回跳。常见做法是给 Orient 加一个极小容差绝对值小于容差时按“在边上”处理直接返回当前三角形后续插入时把点当作落在边上做特殊分裂。4.3 边翻转恢复 Delaunay 性质新点插入后把所在三角形一分为三然后检查新生成的三条边是否满足 Delaunay 准则。不满足就翻转翻转后可能影响相邻三角形用栈或队列做局部传播。判定准则是“对面顶点是否落在当前三角形的外接圆内”用行列式算// 判断点 d 是否在三角形 abc 的外接圆内 bool InCircumcircle(int a, int b, int c, int d) { double ax verts[a].x - verts[d].x; double ay verts[a].y - verts[d].y; double bx verts[b].x - verts[d].x; double by verts[b].y - verts[d].y; double cx verts[c].x - verts[d].x; double cy verts[c].y - verts[d].y; double det (ax * ax ay * ay) * (bx * cy - by * cx) - (bx * bx by * by) * (ax * cy - ay * cx) (cx * cx cy * cy) * (ax * by - ay * bx); return det 0; // 逆时针三角形下正值为圆内 }这个行列式是 3x3 展开把 d 平移到原点后算。det 0的符号约定依赖三角形顶点是逆时针排列如果实现里三角形方向不统一判定会整体反掉这是最容易翻车的地方。翻转本身只改两个三角形的顶点和邻接数组不新建三角形所以内存开销很小。传播时用栈存“待检查边”每次翻转后把受影响的两条边压栈直到栈空。局部性保证了这个过程平均只碰常数个三角形整体复杂度接近 O(N log N)。4.4 边界处理与凸包维护增量插入有个绕不开的问题新点如果落在当前凸包外行走会走到边界返回 -1。这时需要扩展凸包把新点和可见的边界边连成新三角形。实现上通常维护一个凸包顶点环插入外部点时找到两条切线把中间可见的边替换掉。这块是很多开源实现偷懒的地方直接要求输入点集先算好凸包、按凸包顺序插入。这个项目如果追求“最快”很可能也做了类似假设调用方保证点集在凸包内或者先做一次凸包预排序。使用时要留意接口注释如果没写清楚自己补一个凸包预处理更保险。5. 避坑与排查五个真实会卡住你的问题5.1 编译过了但运行崩溃在插入阶段现象点集稍大就在AddPoint里访问越界。原因多半是三角形数组预分配容量不够空闲链表用尽后没有扩容逻辑或者扩容后邻接索引没同步更新。解决在插入前按2N估算三角形上限预分配扩容时整体重建索引映射别只 realloc 数组。5.2 三角形数量对但形状全是狭长三角形现象输出能看但三角形质量极差。原因通常是边翻转没生效或者InCircumcircle的符号约定和三角形顶点方向不一致导致该翻的没翻。解决先固定所有三角形为逆时针再统一判定符号加一个断言检查每个三角形有向面积为正。5.3 点恰好落在已有边上导致死循环现象程序卡在LocateTriangle的 while 里。原因是有向面积在边上时符号抖动行走在两个三角形间来回跳。解决给 Orient 加容差落在边上时直接返回当前三角形插入逻辑走“边分裂”分支而不是“面分裂”。5.4 换到新版编译器后结果和 VC6.0 不一致现象同一批点老环境和新环境输出的三角形不同。原因是浮点运算顺序和 x87 扩展精度差异VC6.0 默认用 x87 80 位中间结果新版默认 SSE 64 位。解决统一编译选项新版加/fp:precise或者接受差异但保证两者都满足 Delaunay 准则用外接圆测试做验收而不是逐三角形比对。5.5 大规模点集内存暴涨现象十万点级别内存占用远超预期。原因是每个三角形存了完整邻接数组加标记位结构体偏大加上空闲链表只回收不缩容。解决把alive改成用v[0] -1表示省一个 bool 的对齐填充或者分块处理按空间网格切分点集分别建网再缝合边界。6. 二次开发把三角网内核接进自己的管线拿到这份源码多数人不是要跑演示是要把它嵌进自己的地形或点云管线。改造的第一步是剥离演示入口只保留构建类和数据结构把printf输出换成回调或直接返回索引数组。第二步是补一个点集预处理去重、剔除共线点、按空间排序希尔伯特曲线或网格排序都行排序后增量插入的行走距离会大幅缩短这是不改变算法本身就能拿到的提速。第三步是接口适配。原始接口大概率是AddPoint逐点插入如果你的数据是一次性给一整批可以加一个批量入口内部先排序再逐点插入对外仍然返回扁平索引数组。下面是一个适配层的写法// 批量构建先按网格排序降低行走距离再逐点插入 bool BuildTIN(const std::vectordouble xs, const std::vectordouble ys, std::vectorint outTris) { int n (int)xs.size(); std::vectorint order(n); for (int i 0; i n; i) order[i] i; // 按 x 分桶再按 y 排序近似空间局部性 std::sort(order.begin(), order.end(), [](int a, int b) { int ba (int)(xs[a] * 16), bb (int)(xs[b] * 16); if (ba ! bb) return ba bb; return ys[a] ys[b]; }); TINBuilder builder; std::vectorint remap(n); for (int k 0; k n; k) { remap[k] builder.AddPoint(xs[order[k]], ys[order[k]]); } const int* tris builder.GetTriangles(); int cnt builder.GetTriangleCount(); outTris.resize(cnt * 3); for (int i 0; i cnt * 3; i) { // 把内部索引映射回原始点序号 outTris[i] order[tris[i]]; } return true; }这里的关键是remap和order的双向映射内部按排序后的顺序插入输出时再映射回调用方的原始序号否则拿到的三角形索引对不上你的点数组。排序桶宽16是经验值点密度高时调大密度低时调小本质是控制每个桶里的点数在一个常数附近。验证改造是否成功我习惯用三个指标三角形总数是否符合欧拉公式、所有三角形有向面积为正、随机抽若干三角形做外接圆测试确认无点落入。这三个检查写成单元测试每次改完跑一遍比肉眼看图靠谱。还有一个容易被忽略的点这份实现如果内部用了全局或静态缓冲区多线程调用会互相踩。要并行建网得把构建类改成无状态或每线程一个实例别图省事共享一个 builder。我早年在一个批量地形生成任务里就栽在这上面单线程跑得好好的一开多线程结果随机错乱查了两天才定位到静态数组。从那以后我每次接这类几何内核第一件事就是 grep 一遍全局变量和 static 局部变量确认没有隐藏的共享状态再谈并行。希望帮到你。本文还有配套的精品资源点击获取
