1. 项目概述从零到一在VC中实现Delaunay三角剖分如果你正在处理地理信息系统、计算机图形学或者任何需要处理离散点集生成网格的场景那么“Delaunay三角网”这个词你一定不陌生。它不仅仅是一种三角剖分方法更是保证网格质量、避免出现“瘦长”三角形的黄金准则。很多朋友可能在论文或者开源库里见过它的应用但真要自己动手尤其是在经典的VC开发环境下从零开始实现一套健壮、高效的Delaunay三角网构建代码往往会遇到一堆“坑”数据结构怎么设计核心的“空外接圆准则”如何高效判定边界处理和退化情况比如四点共圆怎么处理我最近就因为一个老项目的维护需求重新梳理并实现了一套VC下的Delaunay三角网构建代码。这个过程让我深刻体会到看懂算法原理和写出能稳定运行的工业级代码中间隔着一道鸿沟。网上能找到的很多示例代码要么过于学术化只展示核心循环忽略了内存管理和异常处理要么耦合了特定的图形库难以剥离出来用在你的控制台或计算服务中。所以我想通过这篇内容把我这次实现的完整源代码拆开揉碎了讲清楚不仅告诉你每一行代码在做什么更重要的是分享我在设计数据结构、优化算法效率以及调试各种边界案例时踩过的坑和总结的经验。无论你是学生想完成课程设计还是工程师需要在现有MFC或Win32项目中集成网格化功能这篇文章都能给你提供一个可直接参考、复现的蓝本。2. 核心算法与数据结构设计思路在动手写代码之前我们必须把Delaunay三角剖分的核心思想和要用的数据结构想明白。直接用数组和链表硬怼不是不行但代码会很快变得难以维护和调试。我的设计原则是清晰第一效率兼顾。2.1 理解Delaunay三角剖分的“空圆”准则Delaunay三角剖分的定义很简单对于一个平面上的点集其Delaunay三角网中任意一个三角形的外接圆内部不包含点集中的任何其他点。这个“空外接圆准则”是算法的灵魂。它带来的直接好处就是最大化最小角避免了狭长三角形的出现这对于后续的有限元分析或插值计算至关重要。在实现上我们通常采用增量插入法。算法的基本骨架如下构建一个包含所有点的“超级三角形”。将点集中的点逐个插入。每插入一个新点找到其所在的三角形称为“影响三角形”将该三角形删除并与新点连接形成新的三角形。对新形成的三角形集合进行“局部优化”LOP, Local Optimization Procedure即检查相邻三角形是否满足空圆准则如果不满足则进行“边翻转”操作。重复步骤2-4直到所有点插入完毕。移除所有与“超级三角形”顶点相关的三角形。这里的关键在于第3步的“定位”和第4步的“局部优化”如何高效实现。一个朴素的实现遍历所有现有三角形来定位会导致O(n²)的复杂度对于上万级的点集就力不从心了。2.2 数据结构的设计点、边、三角形的“铁三角”为了高效实现上述算法我设计了三个核心类Point、Edge、Triangle。它们之间通过指针相互关联形成一个网状结构。Point类除了存储点的x, y坐标我还增加了一个id成员用于唯一标识这在调试和输出时非常有用。同时它不直接持有三角形或边的引用以保持简洁。Edge类这是实现“边翻转”和查询的关键。一条边由两个Point*指针定义。更重要的是在Delaunay三角网中一条内边通常被两个三角形共享。因此Edge类里我设计了triangles列表或固定大小的数组用于存储共享这条边的三角形。这极大地优化了邻接关系的查找速度。此外我还重载了运算符实现基于点指针而非坐标的相等判断确保逻辑正确。class DelaunayEdge { public: DelaunayPoint* p1; DelaunayPoint* p2; std::vectorDelaunayTriangle* adjacentTriangles; // 通常大小为0, 1或2 DelaunayEdge(DelaunayPoint* a, DelaunayPoint* b) : p1(a), p2(b) {} bool operator(const DelaunayEdge other) const { return (p1 other.p1 p2 other.p2) || (p1 other.p2 p2 other.p1); } };Triangle类这是核心。一个三角形由三个Point*指针构成。我存储了三条边的指针Edge*这比每次计算要快也方便了邻接查询。最关键的是它提供了CircumCircleContains(const Point* p)方法用于判断点p是否位于该三角形的外接圆内。这个方法的实现需要一点平面几何知识通过计算三角形的外心坐标和半径再判断点p到外心的距离与半径的关系。这里要注意数值稳定性问题对于接近共线或坐标值极大的点需要使用稳健的计算方法比如判断行列式的符号而不是直接比较距离平方。class DelaunayTriangle { public: DelaunayPoint* vertices[3]; DelaunayEdge* edges[3]; bool isBad false; // 标记为“坏”三角形用于在算法过程中逻辑删除 // 计算并判断点p是否在外接圆内 bool CircumCircleContains(const DelaunayPoint* p) const { // 详细计算逻辑见后续实现章节 // 核心计算三角形顶点和点p构成的4x4行列式齐次坐标的符号 // 或者直接计算外心坐标和半径再比较距离平方 } };此外整个三角网的管理我使用了一个DelaunayTriangulation类它持有所有的点、边、三角形对象并提供了InsertPoint()、Triangulate()等公开接口。内部维护一个“活动三角形列表”和一个“活动边列表”用于在增量插入过程中跟踪状态变化。注意在内存管理上我选择使用std::vector存储对象并用原始指针表示关系。也可以使用智能指针如std::shared_ptr但需要小心处理循环引用问题。对于教学和清晰度原始指针配合明确的归属关系DelaunayTriangulation类负责所有对象的生命周期更容易理解。3. 核心代码模块详解与实现有了清晰的数据结构我们就可以开始填充血肉实现各个核心模块了。我将按照算法执行的顺序逐一拆解关键函数。3.1 初始化构建“超级三角形”第一步是构建一个足够大的三角形包含所有的输入点。这个三角形的顶点坐标需要精心计算确保它足够大使得所有输入点都位于其内部并且其外接圆不会包含任何输入点除了它自己的顶点。一个常见的做法是计算点集的包围盒然后向外扩展一定的比例比如50%用扩展后的矩形对角线来构造一个大的等腰直角三角形。void DelaunayTriangulation::InitializeSuperTriangle(const std::vectorPoint inputPoints) { // 1. 计算点集的包围盒 double minX INFINITY, maxX -INFINITY, minY INFINITY, maxY -INFINITY; for (const auto p : inputPoints) { minX std::min(minX, p.x); maxX std::max(maxX, p.x); minY std::min(minY, p.y); maxY std::max(maxY, p.y); } // 2. 扩展包围盒确保超级三角形足够大 double dx maxX - minX; double dy maxY - minY; double deltaMax std::max(dx, dy) * 2.0; // 扩展2倍这是一个经验值确保足够大 double midX (minX maxX) / 2.0; double midY (minY maxY) / 2.0; // 3. 定义超级三角形的三个顶点 superTriangleVertices[0] new Point(midX - 20 * deltaMax, midY - deltaMax); // 左下远点 superTriangleVertices[1] new Point(midX 20 * deltaMax, midY - deltaMax); // 右下远点 superTriangleVertices[2] new Point(midX, midY 20 * deltaMax); // 正上远点 // 4. 创建超级三角形对象并加入三角形列表 Triangle* superTri new Triangle(superTriangleVertices[0], superTriangleVertices[1], superTriangleVertices[2]); triangles.push_back(superTri); }实操心得deltaMax的扩展倍数需要足够大。我最初只扩展了1.5倍在处理一些边界分布的点集时出现了新插入的点恰好落在超级三角形外接圆上的情况导致算法失败。将其扩大到10-20倍后非常稳定。虽然这会产生一些数值计算上的挑战大数字但优先保证算法的鲁棒性。3.2 点的定位与“影响多边形”查找当插入一个新点时我们需要快速找到包含这个点的三角形如果点在边上则属于两个三角形。这就是“点定位”问题。一个高效的方法是“行走算法”Walk Algorithm从任意一个三角形比如上一个插入的三角形开始判断点位于当前三角形的哪个区域利用重心坐标或边方向的符号然后朝点的方向移动到相邻的三角形直到定位成功。在我的实现中为了代码清晰我暂时使用了简单但较慢的遍历法适用于点数不多或演示目的。在实际高性能需求中务必替换为“行走算法”或结合网格索引。std::vectorTriangle* DelaunayTriangulation::FindTrianglesContainingPoint(Point* p) { std::vectorTriangle* result; for (Triangle* tri : triangles) { if (tri-isBad) continue; // 跳过已标记为“坏”的三角形 if (tri-ContainsPoint(p)) { // ContainsPoint 方法利用重心坐标判断点是否在三角形内或边上 result.push_back(tri); } } // 如果点在边上result可能包含1个或2个三角形 return result; }找到“影响三角形”后这些三角形构成的区域一个多边形内部包含新点且它们的外接圆都不再满足空圆准则。我们需要删除所有这些三角形形成一个“空洞”然后将新点与这个“空洞”的边界上的每个点连接形成新的三角形。3.3 核心中的核心局部优化与边翻转LOP这是Delaunay算法的精髓。在插入新点形成一批新三角形后这些新三角形与周围旧的三角形之间可能不满足空圆准则。局部优化过程LOP就是通过不断地检查并翻转不满足条件的公共边使三角网重新满足Delaunay性质。我们需要一个队列来存储需要检查的边。算法如下将新生成的所有三角形的边加入检查队列。当队列不为空时取出一条边。找到共享这条边的两个三角形如果存在。如果这条边是边界边只被一个三角形共享则跳过。检查这条边对应的两个三角形形成的四边形是否满足空圆准则。具体来说检查其中一个三角形的非共享顶点是否在另一个三角形的外接圆内。如果不满足则进行“边翻转”删除这条公共边连接四边形的另一条对角线从而用两个新的三角形替换原来的两个三角形。将新生成的两个三角形的、不属于原来四边形的边加入检查队列。重复步骤2-6。void DelaunayTriangulation::LegalizeEdge(Point* p, Edge* e, std::queueEdge* edgeQueue) { if (e-adjacentTriangles.size() ! 2) return; // 边界边不处理 Triangle* tri1 e-adjacentTriangles[0]; Triangle* tri2 e-adjacentTriangles[1]; // 找到两个三角形中不属于边e的那个顶点 Point* op1 tri1-GetOppositeVertex(e); Point* op2 tri2-GetOppositeVertex(e); // 关键判断如果点op2位于三角形tri1的外接圆内则边e非法需要翻转 if (tri1-CircumCircleContains(op2)) { // 标记旧三角形为“坏” tri1-isBad true; tri2-isBad true; // 创建新的对角线即翻转边 Edge* newEdge new Edge(p, op2); // 注意这里p是新插入的点在这个上下文中是op1 // 实际上在插入点的上下文中p是已知的。更通用的写法是找到四边形不共边的两个顶点进行连接。 // 这里为了清晰简化为如果边e由点a,b构成两个对顶点是c和d则翻转后新边连接c和d。 Point* a e-p1; Point* b e-p2; // 假设我们已经正确获取了对顶点c(op1)和d(op2) Point* c op1; Point* d op2; // 删除旧边e创建新边newEdge (连接c和d) Edge* flippedEdge GetOrCreateEdge(c, d); // 用两个新三角形替换旧三角形 (a, c, d) 和 (b, c, d) Triangle* newTri1 new Triangle(a, c, d); Triangle* newTri2 new Triangle(b, c, d); // ... 建立新三角形与边的关联关系 ... // 将新三角形加入到活动列表 triangles.push_back(newTri1); triangles.push_back(newTri2); // 将新生成的、可能与新点相关的边除了翻转边加入检查队列 // 例如边(a,c), (a,d), (b,c), (b,d) 需要检查其新的邻接关系是否合法 AddEdgesToQueueIfNotProcessed(newTri1-edges, edgeQueue, flippedEdge); AddEdgesToQueueIfNotProcessed(newTri2-edges, edgeQueue, flippedEdge); } }注意事项CircumCircleContains函数的数值稳定性至关重要。直接计算距离比较浮点数可能会因为精度问题导致误判。我推荐使用精确的定向测试Orientation Test结合行列式计算。具体来说对于点A, B, C, D判断D是否在A, B, C的外接圆内可以通过计算下面4x4行列式的符号来判断 |Ax, Ay, Ax²Ay², 1| |Bx, By, Bx²By², 1| |Cx, Cy, Cx²Cy², 1| |Dx, Dy, Dx²Dy², 1| 如果行列式大于0则D在圆外小于0则在圆内等于0则在圆上。这种方法比先算圆心半径再算距离更稳健但要注意坐标值过大可能溢出可以使用相对坐标。3.4 后期清理移除超级三角形相关元素所有点插入完成后我们的三角形列表中还包含那些与超级三角形顶点相连的三角形。这些三角形不属于原始点集的Delaunay三角网必须移除。void DelaunayTriangulation::RemoveSuperTriangle() { auto it triangles.begin(); while (it ! triangles.end()) { Triangle* tri *it; // 如果三角形包含任何一个超级三角形的顶点则移除 if (tri-ContainsVertex(superTriangleVertices[0]) || tri-ContainsVertex(superTriangleVertices[1]) || tri-ContainsVertex(superTriangleVertices[2])) { // 标记关联的边如果边不再被任何三角形使用则删除边 for (int i 0; i 3; i) { DisassociateEdgeFromTriangle(tri-edges[i], tri); } delete tri; it triangles.erase(it); } else { it; } } // 最后删除超级三角形的顶点对象 for (int i 0; i 3; i) { delete superTriangleVertices[i]; } }4. 完整工作流程与主函数串联现在我们把所有模块串联起来形成完整的Triangulate主流程。这个函数是面向用户的入口。bool DelaunayTriangulation::Triangulate(const std::vectorPoint inputPoints) { // 0. 清空之前的数据 Clear(); if (inputPoints.size() 3) { // 点数不足无法三角化 return false; } // 1. 初始化超级三角形 InitializeSuperTriangle(inputPoints); // 2. 逐个插入点 for (const auto point : inputPoints) { Point* newPoint new Point(point.x, point.y); m_points.push_back(newPoint); // 2.1 定位包含新点的三角形影响多边形 std::vectorTriangle* affectedTris FindTrianglesContainingPoint(newPoint); if (affectedTris.empty()) { // 理论上不应该发生如果发生说明超级三角形不够大或点定位算法有误 delete newPoint; return false; } // 2.2 收集“空洞”的边界边 std::vectorEdge* polygonHoleEdges; std::unordered_setEdge* edgesToRemove; // 遍历所有影响三角形它们的边如果被两个影响三角形共享则是内部边需要删除 // 如果只被一个影响三角形共享则是“空洞”的边界边。 // ... 具体收集逻辑 ... // 2.3 删除所有影响三角形标记为bad或从列表移除 for (Triangle* tri : affectedTris) { tri-isBad true; // 同时解除边与这些三角形的关联 } // 2.4 用新点连接“空洞”边界上的每个点创建新三角形 std::vectorEdge* newEdges; for (Edge* boundaryEdge : polygonHoleEdges) { Triangle* newTri new Triangle(newPoint, boundaryEdge-p1, boundaryEdge-p2); // 建立新三角形与边的关联复用边界边创建两条新边 // ... triangles.push_back(newTri); // 将新生成的两条边newPoint-p1, newPoint-p2加入待检查队列 newEdges.push_back(/* edge newPoint-p1 */); newEdges.push_back(/* edge newPoint-p2 */); } // 2.5 局部优化LOP std::queueEdge* edgeQueue; for (Edge* e : newEdges) { edgeQueue.push(e); } while (!edgeQueue.empty()) { Edge* e edgeQueue.front(); edgeQueue.pop(); LegalizeEdge(newPoint, e, edgeQueue); // 注意这里需要适配LegalizeEdge的逻辑 } // 2.6 清理标记为bad的三角形 RemoveBadTriangles(); } // 3. 移除与超级三角形相关的所有三角形和边 RemoveSuperTriangle(); // 4. 最终验证与整理可选 // 可以检查所有剩余三角形是否满足Delaunay性质或者计算一些统计信息 return true; }5. 性能优化与高级话题探讨基础的增量插入算法在点数上千时可能就会遇到性能瓶颈。定位点的遍历查找是O(n)复杂度整体算法趋近O(n²)。对于大规模点集我们必须进行优化。5.1 点定位优化行走算法与空间索引行走算法Walk这是一种期望复杂度为O(√n)的算法。它利用三角网的空间连续性从上一个插入点所在的三角形或一个随机三角形开始根据点与当前三角形各边的位置关系“走”向目标点。实现时需要注意处理点恰好落在边上的情况这时可以随机选择一条方向继续走。行走算法在点集分布均匀时效率很高但在极端狭长三角形下可能退化。空间网格索引Spatial Grid将整个区域划分为均匀的网格。插入新点时首先根据点的坐标快速定位到某个网格单元格。维护一个“每个网格单元格中可能包含的三角形”的列表一个三角形可能覆盖多个单元格。定位时只需检查该单元格及其相邻单元格中的三角形大大缩小了搜索范围。这种方法实现相对简单对分布不均匀的点集也有效但需要额外内存存储网格索引。在我的优化版本中我结合了两者首先使用一个粗糙的网格比如100x100快速找到一个候选三角形然后从这个三角形开始执行行走算法。实测对于10万个随机点构建时间可以从分钟级降到秒级。5.2 处理退化情况四点共圆与重复点四点共圆当四个或更多点共圆时Delaunay三角剖分不唯一。我们的算法在判断CircumCircleContains时如果遇到点恰好在外接圆上行列式等于0就会产生歧义。处理方法是制定一个“决胜规则”Tie-breaking Rule。例如可以定义当点在外接圆上时视为“在圆内”强制进行边翻转。或者更稳健的方法是引入微小的随机扰动到点的坐标抖动打破这种几何对称性。在输出结果中这可能会导致两种不同的合法三角网之一。重复点输入点集中可能存在坐标完全相同的点。这会导致算法失败例如试图创建一个面积为0的三角形。必须在预处理阶段剔除重复点。可以使用std::sort和std::unique结合一个自定义的比较函数比较x和y坐标考虑浮点误差来实现。struct PointComparator { bool operator()(const Point a, const Point b) const { const double eps 1e-10; if (fabs(a.x - b.x) eps) return a.x b.x; if (fabs(a.y - b.y) eps) return a.y b.y; return false; // 相等时返回false } }; void RemoveDuplicates(std::vectorPoint points) { std::sort(points.begin(), points.end(), PointComparator()); auto last std::unique(points.begin(), points.end(), [](const Point a, const Point b) { return fabs(a.x - b.x) 1e-10 fabs(a.y - b.y) 1e-10; }); points.erase(last, points.end()); }5.3 内存管理与对象池在增量构建过程中会频繁地创建和删除三角形和边对象。直接使用new和delete可能导致内存碎片和性能开销。一个高级优化是使用对象池Object Pool。我们可以预先分配一大块内存来存储Triangle和Edge对象。当需要一个新对象时从池中取出一个空闲的当对象不再需要时不是直接delete而是将其状态重置并放回池中标记为空闲。这几乎消除了动态内存分配的开销对于需要处理百万级三角形的应用至关重要。实现对象池需要小心处理对象的构造和析构确保重置状态时不会遗留错误指针。6. 调试技巧与常见问题排查实现Delaunay算法就像调试一个动态生长的几何结构光看日志很难发现问题。我总结了几种非常有效的调试方法。6.1 可视化调试每一步都画出来这是最直观的方法。利用VC的MFC或者简单的GDI在算法执行的关键步骤如每次插入点后、每次边翻转后暂停将当前的三角网绘制出来。用不同的颜色区分新生成的三角形、待检查的边、非法的边等。你可以创建一个调试视图在OnPaint函数中遍历所有的Triangle和Edge进行绘制。在怀疑有问题的代码处设置断点然后单步执行观察图形的变化是否符合预期。例如当你发现一个点插入后产生的“空洞”边界不是一个简单的多边形那就说明“影响三角形”查找逻辑有误。6.2 断言与完整性检查在数据结构中嵌入完整性检查函数并在关键操作后调用它们。例如void DelaunayTriangulation::SanityCheck() const { // 检查1: 所有非bad三角形是否都引用了有效的点 for (const Triangle* tri : triangles) { if (tri-isBad) continue; assert(tri-vertices[0] ! nullptr tri-vertices[1] ! nullptr tri-vertices[2] ! nullptr); // 检查点指针是否在总点集列表中可选 } // 检查2: 边的邻接三角形关系是否正确 for (const Edge* e : edges) { // 一条边最多被两个三角形共享 assert(e-adjacentTriangles.size() 2); for (const Triangle* tri : e-adjacentTriangles) { // 检查三角形是否确实包含这条边 assert(std::find(tri-edges.begin(), tri-edges.end(), e) ! tri-edges.end()); } } // 检查3: Delaunay性质计算量大可在最终完成后或怀疑时检查 // for (每个三角形T1) { // for (每个与其共享边的三角形T2) { // assert(T1和T2满足空圆准则); // } // } }在Debug模式下开启这些断言一旦违反就会立刻中断帮你快速定位到数据状态不一致的地方。6.3 常见问题速查表下表列出了我调试过程中遇到的一些典型问题及排查思路问题现象可能原因排查步骤程序崩溃访问非法内存1. 指针未初始化或已删除后被访问。2. 在vector迭代过程中增删元素导致迭代器失效。1. 检查所有new和delete是否配对。2. 使用Remove-Erase惯用法或手动管理迭代器。3. 使用调试器的内存检查工具如Visual Studio的“应用程序验证器”。生成的三角网有“洞”或缺失区域1. “影响多边形”边界收集错误导致新三角形未能完全覆盖空洞。2. 点在三角形边上的处理逻辑不完整导致该边被错误地归为内部边删除。1. 可视化插入单个点前后的状态重点观察“影响三角形”和收集到的“边界边”。2. 检查FindTrianglesContainingPoint函数对于点在边上的返回值应返回两个三角形。3. 检查边界边收集逻辑中判断“边被几个影响三角形共享”的计数是否正确。算法陷入无限循环或栈溢出1. 边翻转逻辑错误导致同一条边被反复加入检查队列。2. 四点共圆时决胜规则导致在两个状态间震荡。1. 在LegalizeEdge函数中对处理过的边做标记避免重复处理。2. 检查CircumCircleContains在点在圆上时的返回值确保规则一致始终返回true或false。3. 限制边翻转队列的最大循环次数超时后输出当前状态用于分析。最终三角网包含超级三角形的边RemoveSuperTriangle函数逻辑有误未能正确识别包含超级顶点的三角形。1. 确保超级三角形的顶点指针被正确存储和比较。2. 检查Triangle::ContainsVertex函数实现是否正确。3. 在移除前可视化整个三角网确认超级三角形的位置和其关联的三角形。对于大量点10000速度极慢1. 点定位使用线性扫描。2. 没有及时清理isBad的三角形导致遍历开销大。1. 实现行走算法或网格索引。2. 在每轮插入后将isBad的三角形从活动triangles列表移到一个废弃列表仅遍历活动列表。6.4 单元测试与边界测试构建一套测试用例至关重要包括简单用例3个点、4个点共圆、共线点。规则网格点如矩形网格其Delaunay三角网是确定的通常由对角线分割的两个三角形组成网格。随机点集用于测试算法的普遍性和稳定性。退化用例输入重复点、所有点共线、空输入。为你的DelaunayTriangulation类编写测试函数验证输出三角形的数量是否符合欧拉公式对于n个点Delaunay三角网最多有3n-6条边和2n-5个三角形并且所有边都满足空圆准则可以通过暴力检查验证。7. 工程集成与扩展应用一套可靠的Delaunay三角网生成代码其价值在于能够无缝集成到更大的项目中。这里谈谈在VC工程中使用的实践。7.1 封装为动态库DLL或静态库将核心算法类Point,Edge,Triangle,DelaunayTriangulation单独放在一个项目中编译成静态库.lib或动态库.dll。这样你的主程序可能是MFC图形程序、控制台工具或服务只需要链接这个库并调用简单的接口即可。接口设计示例// DelaunayAPI.h #ifdef DELAUNAY_EXPORTS #define DELAUNAY_API __declspec(dllexport) #else #define DELAUNAY_API __declspec(dllimport) #endif #include vector struct DelaunayPoint2D { double x, y; }; struct DelaunayTriangle2D { int p1, p2, p3; // 点的索引 }; class DELAUNAY_API DelaunayGenerator { public: DelaunayGenerator(); ~DelaunayGenerator(); // 主计算函数 bool Generate(const std::vectorDelaunayPoint2D points, std::vectorDelaunayTriangle2D outTriangles); // 可设置参数如超级三角形扩展系数 void SetSuperTriangleScale(double scale); };这样封装后调用方完全不需要关心内部复杂的指针和数据结构只需提供点集获取三角形索引列表非常清晰。7.2 与图形界面MFC结合如果你用MFC做界面可以在CView的OnDraw函数中调用三角网生成结果并进行绘制。将点集存储为CArray或std::vector在按钮点击事件中触发计算计算完成后调用Invalidate()重绘视图。绘制示例void CMyDelaunayView::OnDraw(CDC* pDC) { CView::OnDraw(pDC); if (m_triangles.empty()) return; CPen pen(PS_SOLID, 1, RGB(0, 0, 255)); // 蓝色笔绘制边 CPen* oldPen pDC-SelectObject(pen); for (const auto tri : m_triangles) { const auto p1 m_points[tri.p1]; const auto p2 m_points[tri.p2]; const auto p3 m_points[tri.p3]; pDC-MoveTo(p1.x, p1.y); pDC-LineTo(p2.x, p2.y); pDC-LineTo(p3.x, p3.y); pDC-LineTo(p1.x, p1.y); } pDC-SelectObject(oldPen); // 可以用红色点绘制顶点 CBrush brush(RGB(255, 0, 0)); CBrush* oldBrush pDC-SelectObject(brush); for (const auto p : m_points) { pDC-Ellipse(p.x - 2, p.y - 2, p.x 2, p.y 2); } pDC-SelectObject(oldBrush); }7.3 向三维与约束性Delaunay扩展基础的二维Delaunay三角网是很多高级应用的基石。三维Delaunay四面体剖分原理从“空外接圆”扩展到“空外接球”。数据结构从三角形、边变为四面体、三角面片。增量插入法和边翻转在3D中是面翻转或更复杂的操作依然适用但实现复杂度陡增。通常需要借助专业计算几何库如CGAL。约束Delaunay三角网CDT这是更常见的工程需求。你不仅有点还有必须出现在三角网中的线段如地形特征线、区域边界。算法需要在满足Delaunay性质的同时强制这些“约束边”存在。实现方法通常是在标准Delaunay三角网中插入约束边然后通过“边细分”和“局部优化”来恢复Delaunay性质同时保持约束边不被翻转。这是一个进阶话题有成熟的算法如“Ruppert算法”或“Chew算法”用于生成高质量约束三角网。在实现CDT时一个实用的技巧是先将约束边的端点作为普通点插入生成初始Delaunay三角网然后遍历每条约束边查找三角网中与其相交的三角形边进行“边交换”或插入“Steiner点”额外的点来逐步“铺设”这条约束边最后再进行一轮局部优化。这个过程需要仔细维护拓扑关系。