使用 Kruskal 算法生成点云最小生成树并可视化的 C++ 代码

以下是使用 Kruskal 算法生成最小生成树并可视化点云文件的 C++ 代码示例：

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <opencv2/opencv.hpp>

using namespace std;
using namespace cv;

// 定义边结构体
struct Edge {
    int src, dst;
    float weight;
};

// 定义并查集结构体
struct UnionFind {
    vector<int> parent;
    vector<int> rank;
    
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
};

// 计算两点之间的欧氏距离
float distance(const Point2f& p1, const Point2f& p2) {
    float dx = p1.x - p2.x;
    float dy = p1.y - p2.y;
    return sqrt(dx * dx + dy * dy);
}

// 使用 Kruskal 算法生成最小生成树
vector<Edge> kruskal(const vector<Point2f>& points) {
    int n = points.size();
    vector<Edge> edges;
    
    // 构建所有边的集合
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            edges.push_back({i, j, distance(points[i], points[j])});
        }
    }
    
    // 按边权重排序
    sort(edges.begin(), edges.end(), [](const Edge& e1, const Edge& e2) {
        return e1.weight < e2.weight;
    });
    
    // 使用并查集找出最小生成树的边集合
    vector<Edge> mst;
    UnionFind uf(n);
    for (const Edge& edge : edges) {
        int srcRoot = uf.find(edge.src);
        int dstRoot = uf.find(edge.dst);
        if (srcRoot != dstRoot) {
            uf.unite(srcRoot, dstRoot);
            mst.push_back(edge);
        }
    }
    
    return mst;
}

// 可视化最小生成树
void visualizeMST(const vector<Point2f>& points, const vector<Edge>& mst) {
    int width = 800;
    int height = 800;
    Mat canvas(height, width, CV_8UC3, Scalar(255, 255, 255));
    
    for (const Edge& edge : mst) {
        Point2f p1 = points[edge.src];
        Point2f p2 = points[edge.dst];
        line(canvas, p1, p2, Scalar(0, 0, 0), 1, LINE_AA);
    }
    
    for (const Point2f& point : points) {
        circle(canvas, point, 3, Scalar(255, 0, 0), FILLED);
    }
    
    namedWindow('Minimum Spanning Tree', WINDOW_NORMAL);
    imshow('Minimum Spanning Tree', canvas);
    waitKey(0);
}

int main() {
    // 读取点云文件
    ifstream file('point_cloud.txt');
    int n;
    file >> n;
    vector<Point2f> points(n);
    for (int i = 0; i < n; i++) {
        float x, y;
        file >> x >> y;
        points[i] = Point2f(x, y);
    }
    file.close();
    
    // 生成最小生成树
    vector<Edge> mst = kruskal(points);
    
    // 可视化最小生成树
    visualizeMST(points, mst);
    
    return 0;
}

请注意，上述代码中的point_cloud.txt文件应包含点云的数据，格式如下：

4
0.5 0.5
1.5 1.5
2.5 0.5
1.5 2.5

其中第一行为点的数量，后面的每一行为一个点的坐标（x和y）。代码使用 OpenCV 库进行可视化，需要确保已正确安装 OpenCV 并将其包含在编译器的库路径中。