#include \n#include <pcl/point_types.h>\n#include <pcl/io/ply_io.h>\n#include <pcl/visualization/pcl_visualizer.h>\n#include <pcl/common/centroid.h>\n#include <pcl/features/normal_3d.h>\n#include <pcl/visualization/cloud_viewer.h>\n#include <pcl/segmentation/extract_clusters.h>\n\ntypedef pcl::PointXYZ PointT; \ntypedef pcl::PointCloud PointCloudT; \n\n// Structure to represent an edge\nstruct Edge {\n int src, tgt; \n float weight; \n}; \n\n// Structure to represent a subset for union-find\nstruct Subset {\n int parent, rank; \n}; \n\n// Class to represent a connected, undirected and weighted graph\nclass Graph {\npublic:\n int V, E; \n std::vector edges; \n\n Graph(int v, int e) {\n V = v; \n E = e; \n } \n\n // Add an edge to the graph\n void addEdge(int src, int tgt, float weight) {\n Edge edge; \n edge.src = src; \n edge.tgt = tgt; \n edge.weight = weight; \n edges.push_back(edge); \n } \n\n // Find set of an element i\n int find(Subset subsets[], int i) {\n if (subsets[i].parent != i)\n subsets[i].parent = find(subsets, subsets[i].parent); \n return subsets[i].parent; \n } \n\n // Union of two sets x and y\n void Union(Subset subsets[], int x, int y) {\n int xroot = find(subsets, x); \n int yroot = find(subsets, y); \n if (subsets[xroot].rank < subsets[yroot].rank)\n subsets[xroot].parent = yroot; \n else if (subsets[xroot].rank > subsets[yroot].rank)\n subsets[yroot].parent = xroot; \n else {\n subsets[yroot].parent = xroot; \n subsets[xroot].rank++; \n } \n } \n\n // Kruskal's algorithm to find MST\n void KruskalMST(PointCloudT::Ptr cloud) {\n std::vector result; // This will store the resultant MST \n\n // Sort all the edges in non-decreasing order of their weight\n std::sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {\n return a.weight < b.weight; \n }); \n\n // Allocate memory for creating V subsets\n Subset* subsets = new Subset[V]; \n for (int v = 0; v < V; ++v) {\n subsets[v].parent = v; \n subsets[v].rank = 0; \n } \n\n int i = 0; // Index used to pick the next smallest edge\n int e = 0; // Index used to pick the next edge to include in MST \n\n // Number of edges to be taken is equal to V-1\n while (e < V - 1 && i < E) {\n Edge next_edge = edges[i++]; \n\n int x = find(subsets, next_edge.src); \n int y = find(subsets, next_edge.tgt); \n\n // If including this edge does't cause cycle, include it in result and increment the index of result for next edge\n if (x != y) {\n result.push_back(next_edge); \n Union(subsets, x, y); \n ++e; \n } \n } \n\n // Visualize the resulting minimum spanning tree\n pcl::visualization::PCLVisualizer viewer("Minimum Spanning Tree"); \n viewer.setBackgroundColor(0.0, 0.0, 0.0); \n\n // Add the original point cloud to the viewer\n pcl::visualization::PointCloudColorHandlerCustompcl::PointXYZ single_color(cloud, 0, 255, 0); \n viewer.addPointCloudpcl::PointXYZ(cloud, single_color, "original_cloud"); \n\n // Add the edges of the MST to the viewer\n for (const auto& edge : result) {\n const auto& src_point = cloud->points[edge.src]; \n const auto& tgt_point = cloud->points[edge.tgt]; \n std::stringstream ss; \n ss << "edge_" << edge.src << "_" << edge.tgt; \n viewer.addLinepcl::PointXYZ(src_point, tgt_point, ss.str()); \n } \n\n viewer.spin(); \n } \n}; \n\nint main(int argc, char** argv) {\n if (argc != 2) {\n std::cerr << "Usage: " << argv[0] << " <input_ply_file>" << std::endl; \n return -1; \n } \n\n std::string input_file = argv[1]; \n\n // Load the input point cloud from PLY file\n PointCloudT::Ptr cloud(new PointCloudT); \n pcl::io::loadPLYFile(input_file, *cloud); \n\n // Compute the centroid of the point cloud\n Eigen::Vector4f centroid; \n pcl::compute3DCentroid(*cloud, centroid); \n\n // Compute the normals of the point cloud\n pcl::NormalEstimation<PointT, pcl::Normal> ne; \n pcl::PointCloudpcl::Normal::Ptr cloud_normals(new pcl::PointCloudpcl::Normal); \n pcl::search::KdTree::Ptr tree(new pcl::search::KdTree); \n ne.setInputCloud(cloud); \n ne.setSearchMethod(tree); \n ne.setKSearch(20); \n ne.compute(*cloud_normals); \n\n // Create a graph with V vertices and E edges\n int V = cloud->size(); \n int E = V * (V - 1) / 2; \n Graph graph(V, E); \n\n // Calculate the edge weights based on Euclidean distance between points\n for (int i = 0; i < V - 1; ++i) {\n const auto& src_point = cloud->points[i]; \n for (int j = i + 1; j < V; ++j) {\n const auto& tgt_point = cloud->points[j]; \n float distance = pcl::euclideanDistance(src_point, tgt_point); \n graph.addEdge(i, j, distance); \n } \n } \n\n // Perform Kruskal's algorithm to find the minimum spanning tree\n graph.KruskalMST(cloud); \n\n return 0; \n} \n