"#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""#include "vtkAutoInit.h"\n#include <pcl/visualization/point_cloud_color_handlers.h>\nVTK_MODULE_INIT(vtkRenderingOpenGL); // VTK was built with vtkRenderingOpenGL2\n\nusing namespace pcl;\ntypedef pcl::PointXYZ PointT;\ntypedef pcl::PointCloud PointCloudT;\n\n// 表示一条边的结构体\nstruct Edge\n{\n\t int src, tgt;\n\t float weight;\n};\n\n// 表示并查集的子集的结构体\nstruct Subset\n{\n\t int parent, rank;\n};\n\n// 表示一个连通的、无向的、带权重的图的类\nclass Graph\n{\npublic:\n\t int V, E;\n\t std::vector edges;\n\n\t Graph(int v, int e)\n\t {\n\t\t V = v;\n\t\t E = e;\n\t }\n\n\t // 添加一条边到图中\n\t void addEdge(int src, int tgt, float weight)\n\t {\n\t\t Edge edge;\n\t\t edge.src = src;\n\t\t edge.tgt = tgt;\n\t\t edge.weight = weight;\n\t\t edges.push_back(edge);\n\t }\n\n\t // 查找某个元素所在的集合\n\t int find(Subset subsets[], int i)\n\t {\n\t\t if (subsets[i].parent != i)\n\t\t\t subsets[i].parent = find(subsets, subsets[i].parent);\n\t\t return subsets[i].parent;\n\t }\n\n\t // 合并两个集合\n\t void Union(Subset subsets[], int x, int y)\n\t {\n\t\t int xroot = find(subsets, x);\n\t\t int yroot = find(subsets, y);\n\t\t if (subsets[xroot].rank < subsets[yroot].rank)\n\t\t\t subsets[xroot].parent = yroot;\n\t\t else if (subsets[xroot].rank > subsets[yroot].rank)\n\t\t\t subsets[yroot].parent = xroot;\n\t\t else {\n\t\t\t subsets[yroot].parent = xroot;\n\t\t\t subsets[xroot].rank++;\n\t\t }\n\t }\n\n\t // Kruskal算法找到最小生成树\n\t void KruskalMST(PointCloudT::Ptr cloud, std::vector& result, float threshold)\n\t {\n\t\t // 将边按照权重从小到大排序\n\t\t std::sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b)\n\t\t {\n\t\t\t return a.weight < b.weight;\n\t\t });\n\n\t\t // 为V个元素创建并查集的子集\n\t\t Subset* subsets = new Subset[V];\n\t\t for (int v = 0; v < V; ++v)\n\t\t {\n\t\t\t subsets[v].parent = v;\n\t\t\t subsets[v].rank = 0;\n\t\t }\n\n\t\t int i = 0; // 用于选择下一条边的索引\n\t\t int e = 0; // 用于选择下一条边加入最小生成树的索引\n\n\t\t // 需要选择V-1条边\n\t\t while (e < V - 1 && i < E)\n\t\t {\n\t\t\t Edge next_edge = edges[i++];\n\n\t\t\t int x = find(subsets, next_edge.src);\n\t\t\t int y = find(subsets, next_edge.tgt);\n\n\t\t\t // 如果加入这条边不会形成环，并且权重大于阈值，则加入到结果中，并且增加已选择边的计数\n\t\t\t if (next_edge.weight >= threshold && x != y)\n\t\t\t {\n\t\t\t\t result.push_back(next_edge);\n\t\t\t\t Union(subsets, x, y);\n\t\t\t\t ++e;\n\t\t\t }\n\t\t }\n\n\t\t // 可视化最小生成树的结果\n\t\t pcl::visualization::PCLVisualizer viewer("Minimum Spanning Tree" );\n\t\t viewer.setBackgroundColor(0, 0, 0);\n\n\t\t // 将原始点云添加到可视化窗口中\n\t\t pcl::visualization::PointCloudColorHandlerCustompcl::PointXYZ single_color(cloud, 255, 255, 255);\n\t\t viewer.addPointCloudpcl::PointXYZ(cloud, single_color, "original_cloud" );\n\n\t\t // 将最小生成树的边添加到可视化窗口中\n\t\t for (const auto& edge : result)\n\t\t {\n\t\t\t const auto& src_point = cloud->points[edge.src];\n\t\t\t const auto& tgt_point = cloud->points[edge.tgt];\n\t\t\t std::stringstream ss;\n\t\t\t ss << "edge_" << edge.src << "_" << edge.tgt;\n\t\t\t viewer.addLinepcl::PointXYZ(src_point, tgt_point, ss.str());\n\t\t }\n\t\t // Count the number of points in the minimum spanning tree\n\t\t int numPoints = 0;\n\t\t for (const auto& edge : result)\n\t\t {\n\t\t\t const auto& src_point = cloud->points[edge.src];\n\t\t\t const auto& tgt_point = cloud->points[edge.tgt];\n\t\t\t numPoints += 2;\n\t\t }\n\n\t\t std::cout << "Number of points in the minimum spanning tree: " << numPoints << std::endl;\n\t\t while (!viewer.wasStopped())\n\t\t {\n\t\t\t viewer.spinOnce();\n\t\t }\n\t }\n};\n\n// 计算两个点之间的欧式距离\ndouble euclideanDistance(PointXYZ p1, PointXYZ p2)\n{\n\t double dx = p2.x - p1.x;\n\t double dy = p2.y - p1.y;\n\t double dz = p2.z - p1.z;\n\t return std::sqrt(dx * dx + dy * dy + dz * dz);\n}\n\nint main()\n{\n\t // 从PLY文件加载输入点云\n\t pcl::PointCloudpcl::PointXYZ::Ptr cloud(new pcl::PointCloudpcl::PointXYZ);\n\t pcl::io::loadPLYFilepcl::PointXYZ("D:\DIANYUNWENJIANJIA\newOUSHIJULEI_ply.ply", *cloud);\n\n\t // 计算点云的质心\n\t Eigen::Vector4f centroid;\n\t pcl::compute3DCentroid(*cloud, centroid);\n\n\t // 计算点云的法线\n\t pcl::NormalEstimation<pcl::PointXYZ, pcl::Normal> ne;\n\t pcl::PointCloudpcl::Normal::Ptr cloud_normals(new pcl::PointCloudpcl::Normal);\n\t pcl::search::KdTreepcl::PointXYZ::Ptr tree(new pcl::search::KdTreepcl::PointXYZ);\n\t ne.setInputCloud(cloud);\n\t ne.setSearchMethod(tree);\n\t ne.setKSearch(40);\n\t ne.compute(*cloud_normals);\n\n\t // 创建一个有V个顶点和E个边的图\n\t int V = cloud->size();\n\t int E = V * (V - 1) / 2;\n\t Graph graph(V, E);\n\n\t // 基于点之间的欧式距离计算边的权重\n\t for (int i = 0; i < V - 1; ++i)\n\t {\n\t\t const auto& src_point = cloud->points[i];\n\t\t for (int j = i + 1; j < V; ++j)\n\t\t {\n\t\t\t const auto& tgt_point = cloud->points[j];\n\t\t\t float distance = euclideanDistance(src_point, tgt_point);\n\t\t\t graph.addEdge(i, j, distance);\n\t\t }\n\t }\n\t // 设置修剪的阈值\n\t float threshold = 0.00080;\n\t // 执行Kruskal算法找到最小生成树\n\t std::vector result;\n\t graph.KruskalMST(cloud, result, threshold);\n\n// 创建一个新的点云对象保存修剪后的最小生成树结果\n\t pcl::PointCloudpcl::PointXYZ::Ptr new_cloud(new pcl::PointCloudpcl::PointXYZ);\n\t new_cloud->width = cloud->width;\n\t new_cloud->height = cloud->height;\n\t new_cloud->points.resize(cloud->points.size());\n\n\t // 找到在最小生成树中出现三次的节点\n\t std::unordered_map<int, int> node_count;\n\t for (const auto& edge : result)\n\t {\n\t\t node_count[edge.src]++;\n\t\t node_count[edge.tgt]++;\n\t }\n\n\t std::vector threejiedian;\n\t for (const auto& pair : node_count)\n\t {\n\t\t if (pair.second == 3)\n\t\t {\n\t\t\t threejiedian.push_back(pair.first);\n\t\t }\n\t }\n\t // 如果与threejiedian相连的边的权重小于0.0008，则从最小生成树中移除该边\n\t std::vector pruned_result;\n\t for (const auto& edge : result)\n\t {\n\t\t if (std::find(threejiedian.begin(), threejiedian.end(), edge.src) != threejiedian.end() ||\n\t\t\t std::find(threejiedian.begin(), threejiedian.end(), edge.tgt) != threejiedian.end())\n\t\t {\n\t\t\t if (edge.weight <= 0.008)\n\t\t\t {\n\t\t\t\t pruned_result.push_back(edge);\n\t\t\t }\n\t\t }\n\t\t else\n\t\t {\n\t\t\t pruned_result.push_back(edge);\n\t\t }\n\t }\n\t // 将修剪后的最小生成树的顶点添加到新的点云对象中\n\t for (const auto& edge : pruned_result)\n\t {\n\t\t const auto& src_point = cloud->points[edge.src];\n\t\t const auto& tgt_point = cloud->points[edge.tgt];\n\t\t new_cloud->points[edge.src] = src_point;\n\t\t new_cloud->points[edge.tgt] = tgt_point;\n\t }\n\t // 将与threejiedian相连的边的顶点设置为绿色\n\t pcl::PointCloudpcl::PointXYZRGB::Ptr colored_cloud(new pcl::PointCloudpcl::PointXYZRGB);\n\t colored_cloud->points.resize(cloud->points.size());\n\t for (size_t i = 0; i < cloud->points.size(); ++i)\n\t {\n\t\t colored_cloud->points[i].x = cloud->points[i].x;\n\t\t colored_cloud->points[i].y = cloud->points[i].y;\n\t\t colored_cloud->points[i].z = cloud->points[i].z;\n\n\t\t colored_cloud->points[i].r = 255;\n\t\t colored_cloud->points[i].g = 0;\n\t\t colored_cloud->points[i].b = 0;\n\t }\n\t // 将threejiedian的顶点设置为绿色\n\t for (const auto& index : threejiedian)\n\t {\n\t\t colored_cloud->points[index].r = 0;\n\t\t colored_cloud->points[index].g = 255;\n\t\t colored_cloud->points[index].b = 0;\n\t }\n\t // 将最小生成树中出现一次的节点设置为红色\n\t for (const auto& pair : node_count)\n\t {\n\t\t if (pair.second == 1)\n\t\t {\n\t\t\t colored_cloud->points[pair.first].r = 255;\n\t\t\t colored_cloud->points[pair.first].g = 0;\n\t\t\t colored_cloud->points[pair.first].b = 0;\n\t\t }\n\t }\n\t // 找到y值最大的threejiedian节点\n\t float max_y = std::numeric_limits::min();\n\t int max_y_index = -1;\n\t for (const auto& index : threejiedian)\n\t {\n\t\t const auto& point = cloud->points[index];\n\t\t if (point.y > max_y)\n\t\t {\n\t\t\t max_y = point.y;\n\t\t\t max_y_index = index;\n\t\t }\n\t }\n\t // 将y值最大的threejiedian节点用绿色小球显示\n\t colored_cloud->points[max_y_index].r = 0;\n\t colored_cloud->points[max_y_index].g = 255;\n\t colored_cloud->points[max_y_index].b = 0;\n\t // 将新的点云保存为PLY文件\n\t pcl::io::savePLYFile("D:\DIANYUNWENJIANJIA\newKRUSKAL_ply.ply", *new_cloud, true);\n\t return 0;\n
