简介基于分治法实现的三角剖分算法工程采用C语言编写面向计算机图形学、计算几何与算法设计方向的开发者或学习者旨在清晰演示如何将Delaunay三角剖分递归拆解为子问题再合并成完整剖分结果。压缩包共91个文件以cpp源文件、h头文件和Visual Studio工程文件sln/vcxproj为主体并带有编译调试所需的obj、pdb、ipch等中间产物以及图标、位图等界面资源整体大小约29MB目录结构完整便于直接打开工程查看和运行。该项目已有591人学习/下载。工程内置dtriangulation解决方案源码与配置齐全可结合数据结构追踪种子点选择、递归划分、边界处理并维持Delaunay性质借助调试文件还能观察三角网动态生成过程并了解二叉堆、优先队列在性能优化中的应用。工程保留Visual Studio升级记录便于适配不同IDE版本无论课程设计、算法研究或项目改造这份实现均可作参考适合有一定C基础的读者掌握分治策略。1. 三角剖分为什么分治法是最难写对的剖分算法同一个点集能画出的三角剖分有无数种但只有满足空圆准则的那一种能让所有三角形的最小角取到最大值——这就是带 Delaunay 性质的最优剖分。三角剖分算法里有逐点插入、扫描线、分治三条主流路线分治法在理论上拿到了最优的 O(n log n)在工程实现里却公认最难写对分的过程无非是递归切点集合的过程却要在左右两半之间做跨基线的逐边生长、空圆判定、边翻转每一步都踩在浮点精度与退化情况的边界上。搞懂分治法等于同时搞懂空圆准则、凸包合并、局部优化三块底层机制。这套资源的核心不是在某个魔法技巧上快而是把整体剖分拆成可递归求解的局部问题。2. 分治框架从点集排序到递归划分的完整流程2.1 排序让「分」在几何上成立分治三角剖分的第一步不是剖分而是排序。常见的实现思路是先把所有点按 x 坐标排序x 相等时再按 y 坐标排序然后取中位点把区间切成左半和右半。这一步的意义比看上去更深它保证递归下去的每个子区间在几何上也是左右分离的连续点块。左右两侧的凸包不会互相穿插后续「找公共切线」的前提才成立。struct Point { double x, y; int id; }; bool cmp(Point a, Point b) { if (a.x ! b.x) return a.x b.x; return a.y b.y; // x 相同时用 y 决出稳定序 } Mesh solve(Point* pts, int l, int r) { int n r - l 1; if (n 3) return buildBase(pts l, n); // 递归出口 int mid (l r) / 2; Mesh L solve(pts, l, mid - 1); // 左半 Mesh R solve(pts, mid, r); // 右半 return merge(L, R); // 合并是关键 }排序之后调用solve(pts, 0, n-1)即可。buildBase处理不超过三个点的子集而merge承担左右两个子剖分的缝合。注意这里故意用「连续子区间」而非「几何上按中位切」递归的子问题之间天然没有交集也天然被一条竖直线分开。这是分治法能递归下去的结构保证很多实现败在排序不稳定上导致子区间在几何上互相嵌套公共切线逻辑全乱。2.2 递归基单点、双点、三点的出口递归基的写法看起来简单却是后面所有合并操作的信任基础。一个点返回空结构两个点建立一条双向边三个点如果非共线直接按逆时针方向建一个三角形。关键是三个点时就要给面定向——三角形的顶点序必须在局部是逆时针的因为后续所有空圆判定、翻转判定都依赖这个方向约定。Mesh buildBase(Point* p, int n) { if (n 1) return Mesh(1, 0, 0); if (n 2) return Mesh(2, 1, 1); // 顶点、单边、无边面 // n 3保证逆时针后再建面 if (orient2d(p[0], p[1], p[2]) 0) swap(p[1], p[2]); return Mesh(3, 3, 1); // 三条半边围成一个面 }这里Mesh(顶点数, 半边数, 面数)的写法是按半边结构初始化的。双点时只有一条双向边半边数为 1属于剖分中的退化形态三点共线时不能建面需要先做共线处理否则面积为零的三角形会在后续合并中被带进来。这部分处理会在第 4 章的退化情形里展开。2.3 合并主循环从下切线到上切线的生长合并是分治法的灵魂整体形态是先在左右两个子凸包之间找出下公共切线和上公共切线下切线作为初始基线然后让基线一路向上升直到遇见上切线。每次上升会覆盖一个新三角形这个三角形的一边是当前基线第三个顶点来自左凸包或右凸包的边界候选点。merge(left, right) 的主循环 下切线 找下公共切线(left, right) 上切线 找上公共切线(left, right) 基线 下切线 while 基线 ! 上切线: 左候选 从基线左端点沿左凸包边界取的候选顶点 右候选 从基线右端点沿右凸包边界取的候选顶点 用空圆准则比较左候选与右候选选定第三个顶点 chosen 用 (基线左端, 基线右端, chosen) 建三角形 对两条新边分别做 LOP 翻转检查 基线 推进到以 chosen 为端点的下一条边下切线和上切线把左右凸包连接成一个大凸包基线从下往上像拉链一样扫过整个缝隙。这个主循环体现了一个深刻的归纳性质左右子剖分的内部三角形都已经是合法的合并时永远不需要动它们只需要处理「跨越左右边界」的那些新三角形。所有合法性和性能问题都集中在这条拉链的推进逻辑上。3. 空圆准则与 LOP剖分合法性的底层判定3.1 incircle 测试符号背后的几何意义空圆准则in-circle criterion说的是任意一个三角形的外接圆内不允许出现其他点。这是 Delaunay 三角剖分的判定核心。工程实现里判断点 d 是否在三角形 abc 的外接圆内不会真的去算圆心和半径——那要先做浮点除法再开平方既慢又容易在临界情况下失去精度。常见的做法是构造一个行列式符号判断// 约定 a、b、c 按逆时针方向给出 double orient2d(Point a, Point b, Point c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } // d 是否在 abc 的外接圆内a、b、c 逆时针 bool incircle(Point a, Point b, Point c, Point d) { double adx a.x - d.x, ady a.y - d.y; double bdx b.x - d.x, bdy b.y - d.y; double cdx c.x - d.x, cdy c.y - d.y; double det (adx * adx ady * ady) * (bdx * cdy - cdx * bdy) - (bdx * bdx bdy * bdy) * (adx * cdy - cdx * ady) (cdx * cdx cdy * cdy) * (adx * bdy - bdx * ady); return det 0; }这段代码没有开平方没有除法的符号判断。它把 d 平移到原点用三个点相对于 d 的坐标构造一个带平方项的 3x3 行列式det 的符号就对应 d 在圆内、圆外还是圆上。首次接触时很容易觉得这套东西是玄学其实它的几何意义非常直接行列式等价于比较「三角形三条边的斜率差」与「圆半径的累积」符号由 d 相对圆周的位置唯一决定。相比先算圆心半径再比距离它省掉了一整类灾难性的浮点误差来源。3.2 LOP 翻转合法性的自我修复空圆准则决定了一个三角形合不合法而局部优化过程LOP决定不合法的边怎么变成合法。核心操作是 Lawson 翻转如果共享同一条边的两个三角形中某个顶点落进了另一个三角形的外接圆内就把共用边翻转成另外一个对角线用「一次翻转」同时替换两个三角形。// 检查公共边 e 是否非法 bool isIllegal(Edge e, Mesh m) { Vertex a 面1中不在 e 上的顶点; Vertex b 面2中不在 e 上的顶点; // a、b 必须在 e 的异侧否则不是四边形 if (同一侧) return false; // e 的两个端点加 a 构成逆时针后判断 b return incircle(e.p1, e.p2, a, b); } void flip(Edge e, Mesh m) { // 拿到 e 的两条半边 h 和 h.twin // 把 h 的起点改为 b、终点改为 a 所在面结构 // 同步更新 next/prev/twin重排四个半边的循环 // 更新两个三角形面的归属 }翻转的本质不是删边加边而是把两个三角形重新接线。它保证修复后四个顶点构成的四边形再次满足空圆准则并且不会破坏凸包边界。这个操作只影响局部两个面与全局状态无关所以每次合并生成新三角形后都能立刻调用它且理论上翻转总量是线性的——这是分治法能维持 O(n log n) 的底气所在。3.3 半边结构用边而不是顶点来组织剖分分治法里最容易出现的数据结构误区是用「顶点 邻接表」组织剖分。邻接表适合遍历不适合合并且频繁翻转边的场景。标准的工程实现用半边结构DCEL把每条无向边拆成两条方向相反的有向半边struct HalfEdge { int origin; // 起点顶点下标 int twin; // 对偶半边同一条边的反向 int next; // 所属面内按逆时针的下一条半边 int prev; // 所属面内按逆时针的上一条半边 int face; // 半边所在的三角形面 }; struct Mesh { vectorVertex vertices; vectorHalfEdge halfedges; vectorint faces; // 每个面起始半边 };选择半边结构不是风格问题是算力问题。翻转一条边时需要同时定位两个邻接面、四条半边并且把它们的 next/prev/twin 关系重组。半边结构里这些操作全部是 O(1) 的指针重定向邻接表则需要扫一遍邻居列表合并时基线每推进一步都要翻边累积开销不可接受。把「边」而不是「顶点」作为组织剖分的基本单位是分治三角剖分能高效落地的前提。4. 跨子集连接的基线与退化情形4.1 下切线的搜索从哪条边开始长三角形合并的第一步是找左右子凸包之间的下公共切线。所谓下切线是一条同时位于两个凸包「下方」的公共边左侧凸包的所有点都在它的上方或右侧右侧凸包的所有点也如此。经典思路是逐步逼近从最右点与最左点的连线开始检查左右两侧是否还有更「下」的点持续修正两边的端点直到稳定。找下切线(left, right) i left 凸包最右顶点 j right 凸包最左顶点 while 还没稳定: while orient2d(prev(i), i, j) 0: // i 还能往下走 i prev(i) while orient2d(i, j, next(j)) 0: // j 还能往下走 j next(j) return Edge(i, j)这里的prev(i)表示在凸包上逆时针顺序的上一个顶点next(j)表示右凸包上顺时针顺序的下一个顶点。两次内循环分别修正左端和右端直到两条切线条件同时满足。上下切线的区别只是一个方向判断的符号上切线把 0换成 0即可。很多人第一次写分治法就把这两个符号弄反结果基线跑反方向合并出来的剖分整个不是凸包。4.2 候选点竞争与可见性剪枝基线确定后第三步是选第三个顶点。基线两端各有一个候选左候选是基线左端点沿左凸包边界推进一个的顶点右候选是右端点沿右凸包边界推进一个的顶点。选谁的标准是空圆准则——不能选让另一个候选点落进外接圆的方案选定第三个顶点 chosen 左候选 lc 左凸包上基线左端沿逆时针的下一个顶点 右候选 rc 右凸包上基线右端沿顺时针的下一个顶点 if incircle(基线的两个端点, lc, rc): // rc 在 lc 的外接圆内 chosen rc // 那选 lc 会非法改选 rc else chosen lc这里有个容易被忽略的细节如果候选点与基线不构成「外侧可见」的三角形它根本不该参与竞争。判定方法是检查候选点是否落在基线端点确定的另一侧或者是否会被中间凸包顶点挡住。标准做法是在凸包上推进时先做可见性剪枝——越过所有与基线不构成外三角形的边界顶点再进入 incircle 竞争。漏掉剪枝合并出的剖分里会出现三角形覆盖内部顶点的情况画出来就像边界向内凹陷后续 LOP 也救不回来。基线推进后新三角形的另外两条边中只有通往上方的那条会成为新基线。基线的一端换成 chosen另一端不动于是整条基线像走之字形楼梯一样逐步爬升直到碰到上切线。这个「之字形推进」是理解合并过程的关键画面它在左右凸包之间交替取点每次都把可以触达的边界顶点用合法三角形填满。4.3 退化情形共线、重复点与四点共圆退化是分治三角剖分里最脏的一类问题也是最容易被资源里的实现掩盖掉的部分。我一般把退化分成三类处理重复点、共线点、四点共圆。退化情形现象处理策略重复点排序后相邻坐标完全相等建边时出现长度为 0 的边对输入先排序再去重去重后才能保证排序稳定共线点orient2d 结果接近 0递归基里建出面积为零的三角形三点共线时不建面把共线点挂到最近的凸包边上四点共圆incircle 结果在 0 附近震荡两个三角形反复翻转用稳定序打破对称四点近似共圆时规定固定方向不翻转四点共圆是分治法最著名的坑。左右子集合并时如果接触边界上恰好有四个点共圆incircle 只要符号判定就永远在 0 附近徘徊LOP 翻转会左右横跳程序直接陷入死循环。常见的工程处理是设置一个极小容差判定落在容差带内时按字典序固定翻转方向保证确定性。另一个思路是在输入阶段做微小扰动把共圆点轻微推开代价是输出结果带扰动痕迹。这两种取舍在源码里通常只隔一个eps参数但从原理上它们是两种不同的哲学一个保确定性一个保纯粹性。4.4 合并后的结构校验三角形数量是硬指标合并做完后剖分是否完整有一个非常可靠的硬指标对无退化且点都在凸包上的剖分面数和边数必须满足欧拉公式给出的闭式关系。设 n 为总点数h 为凸包顶点数则三角形面数为 2n - 2 - h边数为 3n - 3 - h。这不是近似是拓扑结论。我一般会在实现里专门写一个validate()遍历半边结构统计点数、半边形数、面数再计算出实际凸包顶点数做校验。只要数值对不上说明合并阶段要么漏了三角形要么半边没配对要么出现了零面积面。这个校验在调试分治法时比任何可视化工具都好用——它能在一秒内定位到自己写的拉链逻辑错在哪一环。5. 分治法实现避坑五个最容易翻车的细节5.1 递归栈先崩划分不平和翻转死循环都可能是元凶现象点集规模到几十万时程序直接爆栈退出看起来像递归深度失控。 原因分治递归深度理论上只有 O(log n)但如果你用sort后取中位的方式切分而输入里存在大量 x 坐标相等的点切分会出现「中点恰好落在重复点簇中间」的情况左右规模不再均衡深度退化到 O(n)。另一种可能是翻转循环里出现无限震荡递归栈被持续压入新帧。 解决取中位用线性选择保证严格二分翻转循环加迭代上限每次翻转计数超过阈值就输出退化警告并退出。栈深度不是玄学是可以提前估算的上限。5.2 输出里出现零面积三角形现象可视化结果里有一些细长条或完全重叠的三角形面积接近 0。 原因最典型的是递归基处三点共线时直接建了面。分治时左侧点集右边界和右侧点集左边界如果共线合并阶段会把共线的边界顶点当成普通候选点生成退化面。 解决三点共线时只建边不建面合并阶段在候选点竞争中先跳过共线顶点把共线点挂到最近的凸包边上。处理顺序必须在递归基和合并两处同时做只做一处都会被另一处漏进来。5.3 翻转死循环四点共圆的浮点震荡现象程序卡住不动或同一组三角形来回翻转剖分结果不稳定。 原因浮点比较在边界附近反复震荡。两侧三角形的外接圆判定正好落在 incircle 符号翻转的临界点上det一会儿正一会儿负翻转后又是同一个临界状态。 解决给 incircle 加一个容差带|det| eps时走稳定序分支。稳定序的要点是「此时禁止翻转」而不是「此时强制翻转一次」。强制翻转会让问题换一条边重新出现死循环换一个位置继续。5.4 合并结果不是合法凸包现象剖分外围有凹陷原本在凸包边界上的顶点被包进了内部。 原因公共切线搜索的方向符号反了。下切线写成上切线的方式后基线从错误的边开始生长前期连出的三角形直接插到边界外侧。另一类原因是可见性剪枝缺失候选点被内部顶点遮挡但照选不误。 解决用第 4 节的小凸包样例单独验证切线搜索不依赖完整剖分去测。只取四个点、六个点做手算对照确认下切线和上切线都正确后再进入主循环调试。5.5 三角形数量对不上现象100 个点剖分完面数不是理论值。 原因半边结构里twin配对出现漏连或重复连。合并时新增三角形的半边只连了自己的next/prev没连对偶对象的twin于是相邻关系断裂LOP 无法正确访问邻接三角形。 解决把validate()放在每个合并步骤返回前执行。统计实际面数和边数与欧拉公式核对。这是全篇最值得提前写进代码的检查——每跑一遍合并就校验一次能精确知道哪一步丢的三角形数。6. 从分治到增量设计取舍与工程落地分治法把复杂度压到 O(n log n)但它的代价不只是代码量。合并时需要同时驻留左右两个子剖分的半边结构峰值内存比逐点插入高出一块每次逼近切线和推进基线都要做方向判断常数因子也不小。工程上真正要回答的问题是什么时候值得用分治什么时候该抄近路。实现路线最坏复杂度平均复杂度峰值内存实现难度典型适用分治法O(n log n)O(n log n)较高递归驻留高百万级点、确定性要求逐点插入O(n²)O(n log n)随机化后低单点插入低十万级点、快速原型扫描线O(n log n)O(n log n)中很高数据流式、边界结构清晰逐点插入的思路是把点一个一个塞进现有剖分先找包含点的三角形再剖成三个新三角形最后用 LOP 回溯修复。它实现短、调试容易但最坏情况是全序退化随机打乱能让平均复杂度接近 O(n log n)却带来了输出的随机性。分治法相反输出完全确定、可复现更重要的优势是它天然不依赖随机化就能稳定走满 O(n log n)。我讲这段取舍是想说明一件事这套资源里「为什么用分治而非逐点插入」的答案不在速度而在确定性和规模。如果只是十万量级的点逐点插入加随机打乱完全够用一旦上到百万量级或者你的下游管线要求同输入必得同剖分分治法的确定性就是不可替代的硬需求。你拿到这套实现真正值得复用的是它的核心机制——半边结构、稳定 incircle、切线搜索与基线生长这四件套而不是一味追求手写出一个超越成熟库的工程。我自己实现分治法时踩的最狠的一次就是漏了共线点处理百万点集跑完可视化全是一堆重叠薄片当时第一反应是「数据结构写错了」查了三天才发现是递归基处少了一个方向判断。从那以后我强制自己把validate()写进合并入口任何一次改动都先跑拓扑校验再看图。希望你先把这条纪律放进自己的实现里希望帮到你。本文还有配套的精品资源点击获取