c++编写delaunay

Delaunay三角剖分是一种将点集转换为无重叠三角形集合的方法，具有优秀的几何特性和广泛的应用。下面是一个简单的C++实现：

首先需要定义一个点类，包含点的x和y坐标：

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};

接下来，定义一个边类，包含起点和终点的编号：

struct Edge {
    int u, v;
    Edge(int u = 0, int v = 0) : u(u), v(v) {}
};

然后，定义一个三角形类，包含三个顶点的编号和外接圆的圆心和半径：

struct Triangle {
    int a, b, c;
    Point o;
    double r;
    Triangle(int a = 0, int b = 0, int c = 0) : a(a), b(b), c(c) {}
};

接着，定义一个函数用于计算三角形外接圆的圆心和半径：

void circumcircle(Point p1, Point p2, Point p3, Point& o, double& r) {
    double a1 = p2.x - p1.x, b1 = p2.y - p1.y, c1 = (a1 * a1 + b1 * b1) / 2;
    double a2 = p3.x - p1.x, b2 = p3.y - p1.y, c2 = (a2 * a2 + b2 * b2) / 2;
    double d = a1 * b2 - a2 * b1;
    o.x = p1.x + (c1 * b2 - c2 * b1) / d;
    o.y = p1.y + (a1 * c2 - a2 * c1) / d;
    r = sqrt((o.x - p1.x) * (o.x - p1.x) + (o.y - p1.y) * (o.y - p1.y));
}

然后，定义一个函数用于判断点是否在三角形外接圆内：

bool in_circle(Point p, Triangle t) {
    double dx = p.x - t.o.x, dy = p.y - t.o.y;
    double d2 = dx * dx + dy * dy;
    return d2 < t.r * t.r;
}

接着，定义一个函数用于计算Delaunay三角剖分的边：

void delaunay(int n, Point p[], vector<Edge>& edges) {
    vector<Triangle> tri;
    tri.push_back(Triangle(0, 1, 2));
    for (int i = 3; i < n; i++) {
        vector<Edge> e;
        for (int j = 0; j < tri.size(); j++) {
            if (in_circle(p[i], tri[j])) {
                e.push_back(Edge(tri[j].a, tri[j].b));
                e.push_back(Edge(tri[j].b, tri[j].c));
                e.push_back(Edge(tri[j].c, tri[j].a));
                tri[j] = tri.back();
                tri.pop_back();
                j--;
            }
        }
        for (int j = 0; j < e.size(); j++) {
            for (int k = j + 1; k < e.size(); k++) {
                if (e[j].u == e[k].v && e[j].v == e[k].u) {
                    e[j] = e.back();
                    e.pop_back();
                    e[k] = e.back();
                    e.pop_back();
                    j--;
                    break;
                }
            }
        }
        for (int j = 0; j < e.size(); j++) {
            tri.push_back(Triangle(e[j].u, e[j].v, i));
        }
    }
    for (int i = 0; i < tri.size(); i++) {
        edges.push_back(Edge(tri[i].a, tri[i].b));
        edges.push_back(Edge(tri[i].b, tri[i].c));
        edges.push_back(Edge(tri[i].c, tri[i].a));
    }
}

最后，就可以使用上述函数来计算Delaunay三角剖分了：

int main() {
    int n;
    cin >> n;
    Point p[n];
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y;
    }
    vector<Edge> edges;
    delaunay(n, p, edges);
    // 输出所有边
    for (int i = 0; i < edges.size(); i++) {
        cout << edges[i].u << " " << edges[i].v << endl;
    }
    return 0;
}