#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#include \n#include <unordered_map>\n"vtkAutoInit.h" \n\nVTK_MODULE_INIT(vtkRenderingOpenGL); // VTK was built with vtkRenderingOpenGL2\n\nusing namespace pcl; \ntypedef pcl::PointXYZ PointT; \ntypedef pcl::PointCloud PointCloudT; \n// Structure to represent an edge\nstruct Edge\n{\n int src, tgt; \n float weight; \n}\n// Structure to represent a subset for union-find\nstruct Subset\n{\n int parent, rank; \n}\n\n// Class to represent a connected, undirected and weighted graph\nclass Graph\n{\npublic: \n int V, E; \n std::vector edges; \n\n Graph(int v, int e)\n {\n V = v; \n E = e; \n }\n // Add an edge to the graph\n void addEdge(int src, int tgt, float weight)\n {\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 {\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 {\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, std::vector& result)\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 {\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 {\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 {\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 doesn't cause a cycle, include it in result and increment the index of result for next edge\n if (next_edge.weight < 0.043)\n {\n if (x != y)\n {\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); \n\n // Add the original point cloud to the viewer\n pcl::visualization::PointCloudColorHandlerCustompcl::PointXYZ single_color(cloud, 255, 255, 255); \n viewer.addPointCloudpcl::PointXYZ(cloud, single_color, "original_cloud"); \n // 将最小生成树的边添加到视图器中\n for (const auto& edge : result)\n {\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 // Connect two disconnected edges\n pcl::PointXYZ point1 = cloud->points[16]; \n pcl::PointXYZ point2 = cloud->points[33]; \n pcl::PointXYZ point3 = cloud->points[32]; \n pcl::PointXYZ point4 = cloud->points[38]; \n viewer.addLine<pcl::PointXYZ, pcl::PointXYZ>(point1, point2, 0, 255, 0, "line1"); \n viewer.addLine<pcl::PointXYZ, pcl::PointXYZ>(point3, point4, 0, 255, 0, "line2"); \n pcl::PointXYZ point5 = cloud->points[61]; \n viewer.addSphere(point5, 0.004, 0, 1, 0, "sphere", 0); \n\n // Find the node with the maximum value in the y direction and mark it as green\n std::unordered_map<int, int> countMap; \n for (const auto& edge : result)\n {\n countMap[edge.src]++; \n countMap[edge.tgt]++; \n } \n //出现三次的节点用绿色表示，表示为节点\n pcl::PointCloudpcl::PointXYZ::Ptr threejiedian(new pcl::PointCloudpcl::PointXYZ); \n int begin = 0; \n for (const auto& pair : countMap)\n {\n if (pair.second >= 3)\n {\n //std::cout << "该点坐标： " << pair.first << " 出现 " << pair.second << " 次" << std::endl; \n //std::cout << cloud->points[pair.first] << std::endl; \n pcl::PointXYZ point3 = cloud->points[pair.first]; \n std::stringstream sa; \n //std::cout << "节点索引号: " << pair.first << std::endl; \n sa << begin; \n begin++; \n viewer.addSphere(pcl::PointXYZ(point3), 0.0023, 0, 1, 0, sa.str()); \n threejiedian->push_back(point3); \n } \n } \n //出现一次的节点用红色表示，表示为叶尖\n pcl::PointCloudpcl::PointXYZ::Ptr singlejiedian(new pcl::PointCloudpcl::PointXYZ); \n int begin2 = 0; \n for (const auto& pair : countMap)\n {\n if (pair.second == 1)\n {\n pcl::PointXYZ point3 = cloud->points[pair.first]; \n std::stringstream sb; \n sb << begin2; \n begin2++; \n viewer.addSphere(pcl::PointXYZ(point3), 0.0023, 1, 0, 0, sb.str()); \n singlejiedian->push_back(point3); \n } \n } \n while (!viewer.wasStopped())\n {\n viewer.spinOnce(); \n } \n } \n}; \n\ndouble euclideanDistance(PointXYZ p1, PointXYZ p2)\n{\n double dx = p2.x - p1.x; \n double dy = p2.y - p1.y; \n double dz = p2.z - p1.z; \n return std::sqrt(dx * dx + dy * dy + dz * dz); \n}\nint main()\n{\n // Load the input point cloud from PLY file\n pcl::PointCloudpcl::PointXYZ::Ptr cloud(new pcl::PointCloudpcl::PointXYZ); \n pcl::io::loadPLYFilepcl::PointXYZ("D:\DIANYUNWENJIANJIA\newOUSHIJULEI_ply.ply", *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<pcl::PointXYZ, pcl::Normal> ne; \n pcl::PointCloudpcl::Normal::Ptr cloud_normals(new pcl::PointCloudpcl::Normal); \n pcl::search::KdTreepcl::PointXYZ::Ptr tree(new pcl::search::KdTreepcl::PointXYZ); \n ne.setInputCloud(cloud); \n ne.setSearchMethod(tree); \n ne.setKSearch(40); \n ne.compute(*cloud_normals); \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 // Calculate the edge weights based on Euclidean distance between points\n for (int i = 0; i < V - 1; ++i)\n {\n const auto& src_point = cloud->points[i]; \n for (int j = i + 1; j < V; ++j)\n {\n const auto& tgt_point = cloud->points[j]; \n float distance = euclideanDistance(src_point, tgt_point); \n graph.addEdge(i, j, distance); \n } \n } \n // 执行最小生成树\n std::vector result; \n graph.KruskalMST(cloud, result); \n\n // 创建一个新的点云对象来保存着色后的结果\n pcl::PointCloudpcl::PointXYZRGB::Ptr new_cloud(new pcl::PointCloudpcl::PointXYZRGB); \n new_cloud->width = cloud->width; \n new_cloud->height = cloud->height; \n new_cloud->points.resize(cloud->points.size()); \n // 将最小生成树的顶点添加到新的点云对象中。\n for (const auto& edge : result)\n {\n const auto& src_point = cloud->points[edge.src]; \n const auto& tgt_point = cloud->points[edge.tgt]; \n new_cloud->points[edge.src].x = src_point.x; \n new_cloud->points[edge.src].y = src_point.y; \n new_cloud->points[edge.src].z = src_point.z; \n\n new_cloud->points[edge.tgt].x = tgt_point.x; \n new_cloud->points[edge.tgt].y = tgt_point.y; \n new_cloud->points[edge.tgt].z = tgt_point.z; \n\n // 计算每个点在最小生成树中的出现次数\n int src_count = std::count_if(result.begin(), result.end(), [&](const Edge& e) { \n return (e.src == edge.src || e.tgt == edge.src); \n }); \n int tgt_count = std::count_if(result.begin(), result.end(), [&](const Edge& e) { \n return (e.src == edge.tgt || e.tgt == edge.tgt); \n }); \n\n // 设置颜色\n uint8_t red = 255 * std::min(1, src_count); \n uint8_t green = 255 * std::min(1, tgt_count); \n uint8_t blue = 0; \n\n new_cloud->points[edge.src].r = red; \n new_cloud->points[edge.src].g = green; \n new_cloud->points[edge.src].b = blue; \n\n new_cloud->points[edge.tgt].r = red; \n new_cloud->points[edge.tgt].g = green; \n new_cloud->points[edge.tgt].b = blue; \n } \n\n // Save the new point cloud as a PLY file\n pcl::io::savePLYFile("D:\DIANYUNWENJIANJIA\newKRUSKAL_ply.ply", *new_cloud, true); \n return 0; \n
