Delaunay三角剖分详解（C++实现入门指南）

上图展示了一组点经过Delaunay三角剖分后形成的三角网格。注意每个三角形的外接圆内都没有其他输入点。

为什么使用Delaunay三角剖分？

• 生成的三角形尽可能“均匀”，避免出现狭长三角形；
• 在插值、地形建模、网格生成等任务中效果更优；
• 具有良好的数学性质，便于后续算法处理。

实现思路（简化版）

对于初学者，我们采用一种简单的“暴力法”：遍历所有可能的三点组合，检查是否满足Delaunay条件（即外接圆内无其他点）。虽然效率不高（时间复杂度为O(n⁴)），但逻辑清晰，适合学习理解。

步骤如下：

1. 读入所有点；
2. 枚举所有三个点的组合；
3. 对每组三点，计算其外接圆；
4. 检查该圆内是否包含其他输入点；
5. 若不包含，则这三点构成一个Delaunay三角形。

C++代码实现

下面是一个简化的C++实现，仅用于教学目的。实际项目中建议使用更高效的算法（如Bowyer-Watson或分治法）。

#include <iostream>#include <vector>#include <cmath>struct Point {    double x, y;    Point(double x = 0, double y = 0) : x(x), y(y) {}};// 判断点p是否在由a,b,c三点确定的外接圆内bool inCircle(const Point& a, const Point& b, const Point& c, const Point& p) {    // 使用行列式判断（InCircle Test）    double adx = a.x - p.x, ady = a.y - p.y;    double bdx = b.x - p.x, bdy = b.y - p.y;    double cdx = c.x - p.x, cdy = c.y - p.y;    double abdet = adx * ady - bdx * bdy;    double bcdet = bdx * bdy - cdx * cdy;    double cadet = cdx * cdy - adx * ady;    double alift = adx * adx + ady * ady;    double blift = bdx * bdx + bdy * bdy;    double clift = cdx * cdx + cdy * cdy;    double det = alift * bcdet + blift * cadet + clift * abdet;    return det > 0; // 若det > 0，则p在圆内}// 判断三点是否共线bool isCollinear(const Point& a, const Point& b, const Point& c) {    double area = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);    return std::abs(area) < 1e-9;}int main() {    std::vector<Point> points = {{0,0}, {1,0}, {0,1}, {1,1}, {0.5, 0.5}};    int n = points.size();    std::cout << "Delaunay Triangles:\n";    for (int i = 0; i < n; ++i) {        for (int j = i + 1; j < n; ++j) {            for (int k = j + 1; k < n; ++k) {                if (isCollinear(points[i], points[j], points[k])) continue;                bool valid = true;                for (int l = 0; l < n; ++l) {                    if (l == i || l == j || l == k) continue;                    if (inCircle(points[i], points[j], points[k], points[l])) {                        valid = false;                        break;                    }                }                if (valid) {                    std::cout << "Triangle: (" << i << "," << j << "," << k << ")\n";                }            }        }    }    return 0;}  

注意事项

上述代码中的inCircle函数使用了符号行列式方法判断点是否在圆内，这是计算几何中的标准技巧。但要注意浮点精度问题，在实际应用中需加入容差（epsilon）。

此外，该暴力算法仅适用于点数较少的情况（如 n < 50）。对于大规模数据，应使用更高效的计算几何算法，例如Bowyer-Watson增量插入法，其平均时间复杂度为O(n log n)。

进阶建议

掌握基础后，你可以尝试：

• 使用第三方库（如CGAL、Triangle）进行高效三角网格生成；
• 实现可视化界面，用OpenGL或SFML绘制结果；
• 研究约束Delaunay剖分（Constrained Delaunay Triangulation）。

总之，Delaunay三角剖分是连接离散点与连续曲面的重要桥梁，也是C++图形算法学习中的经典课题。希望本文能为你打开计算几何的大门！