基于 PCL 库使用 Kruskal 最小生成树算法连接点云 PLY 文件内的所有点并进行可视化的 C++ 代码

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

#include <iostream>
#include <pcl/point_cloud.h>
#include <pcl/point_types.h>
#include <pcl/io/ply_io.h>
#include <pcl/visualization/cloud_viewer.h>
#include <pcl/segmentation/extract_clusters.h>
#include <pcl/features/normal_3d.h>
#include <pcl/features/moment_of_inertia_estimation.h>
#include <pcl/common/centroid.h>
#include <pcl/common/common.h>

// 定义一个结构体来表示边
struct Edge
{
    int src, dest;
    float weight;
};

// 定义一个结构体来表示并查集中的子集
struct Subset
{
    int parent;
    int rank;
};

// 查找元素 i 的集合（使用路径压缩技术）
int find(Subset subsets[], int i)
{
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);

    return subsets[i].parent;
}

// 合并两个集合 x 和 y（使用按秩合并）
void Union(Subset subsets[], int x, int y)
{
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else
    {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

// 用于按权重非递减顺序对边进行排序的比较函数
bool compareEdges(const Edge &a, const Edge &b)
{
    return a.weight < b.weight;
}

// 使用 Kruskal 算法构造 MST 的函数
void KruskalMST(pcl::PointCloud<pcl::PointXYZ>::Ptr cloud, pcl::PointCloud<pcl::PointXYZ>::Ptr output)
{
    int numVertices = cloud->size();
    int numEdges = numVertices * (numVertices - 1) / 2;

    // 创建一个向量来存储图中的所有边
    std::vector<Edge> edges(numEdges);

    int edgeIndex = 0;
    for (int i = 0; i < numVertices; i++)
    {
        for (int j = i + 1; j < numVertices; j++)
        {
            Edge e;
            e.src = i;
            e.dest = j;
            e.weight = pcl::euclideanDistance(cloud->points[i], cloud->points[j]);
            edges[edgeIndex++] = e;
        }
    }

    // 按权重非递减顺序对边进行排序
    std::sort(edges.begin(), edges.end(), compareEdges);

    // 分配内存以创建 V 个子集
    Subset *subsets = new Subset[numVertices * sizeof(Subset)];

    // 创建 V 个包含单个元素的子集
    for (int v = 0; v < numVertices; ++v)
    {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    // 初始化 MST 以存储最小生成树的边
    std::vector<Edge> mst(numVertices - 1);

    // 跟踪包含在 MST 中的边
    int mstIndex = 0;

    // 用于选择下一条边的索引变量
    int edgeCount = 0;

    // 循环，直到所有边都包含在 MST 中或形成了最大生成树
    while (mstIndex < numVertices - 1)
    {
        // 选择最小的边
        Edge nextEdge = edges[edgeCount++];

        int x = find(subsets, nextEdge.src);
        int y = find(subsets, nextEdge.dest);

        // 如果包含这条边不会导致循环，则将其包含在 MST 中
        if (x != y)
        {
            mst[mstIndex++] = nextEdge;
            Union(subsets, x, y);
        }
    }

    // 释放分配的内存
    delete[] subsets;

    // 创建输出点云
    output->resize(numVertices);
    for (int i = 0; i < numVertices; i++)
    {
        output->points[i] = cloud->points[i];
    }

    // 将 MST 的边添加到输出点云
    for (int i = 0; i < mstIndex; i++)
    {
        int src = mst[i].src;
        int dest = mst[i].dest;
        output->points[src].x = cloud->points[src].x;
        output->points[src].y = cloud->points[src].y;
        output->points[src].z = cloud->points[src].z;
        output->points[dest].x = cloud->points[dest].x;
        output->points[dest].y = cloud->points[dest].y;
        output->points[dest].z = cloud->points[dest].z;
    }
}

int main()
{
    // 从 PLY 文件加载输入点云
    pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);
    pcl::PointCloud<pcl::PointXYZ>::Ptr output(new pcl::PointCloud<pcl::PointXYZ>);
    pcl::PLYReader reader;
    reader.read('input.ply', *cloud);

    // 应用 Kruskal 算法来构造 MST
    KruskalMST(cloud, output);

    // 可视化原始点云和 MST
    pcl::visualization::CloudViewer viewer('Point Cloud Viewer');
    viewer.showCloud(cloud, 'Original Point Cloud');
    viewer.showCloud(output, 'Minimum Spanning Tree');

    while (!viewer.wasStopped())
    {
    }

    return 0;
}

请注意，此示例仅处理具有 PointXYZ 类型的点云 PLY 文件。如果您的 PLY 文件中包含其他类型的点云数据，请相应地修改代码。此外，您需要将 PLY 文件的名称更改为实际的文件名。