#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\n// 结构体表示边\nstruct Edge\n{\n\tint src, tgt;\n\tfloat weight;\n}\n\n// 结构体表示并查集中的子集\nstruct Subset\n{\n\tint parent, rank;\n}\n\n// 表示一个连接的、无向的、有权的图的类\nclass Graph\n{\npublic:\n\tint V, E;\n\tstd::vector edges;\n\n\tGraph(int v, int e)\n\t{\n\t\tV = v;\n\t\tE = e;\n\t}\n\n\t// 添加一条边到图中\n\tvoid addEdge(int src, int tgt, float weight)\n\t{\n\t\tEdge edge;\n\t\tedge.src = src;\n\t\tedge.tgt = tgt;\n\t\tedge.weight = weight;\n\t\tedges.push_back(edge);\n\t}\n\n\t// 查找元素i的集合\n\tint find(Subset subsets[], int i)\n\t{\n\t\tif (subsets[i].parent != i)\n\t\t\tsubsets[i].parent = find(subsets, subsets[i].parent);\n\t\treturn subsets[i].parent;\n\t}\n\n\t// 合并两个集合x和y\n\tvoid Union(Subset subsets[], int x, int y)\n\t{\n\t\tint xroot = find(subsets, x);\n\t\tint yroot = find(subsets, y);\n\t\tif (subsets[xroot].rank < subsets[yroot].rank)\n\t\t\tsubsets[xroot].parent = yroot;\n\t\telse if (subsets[xroot].rank > subsets[yroot].rank)\n\t\t\tsubsets[yroot].parent = xroot;\n\t\telse {\n\t\t\tsubsets[yroot].parent = xroot;\n\t\t\tsubsets[xroot].rank++;\n\t\t}\n\t}\n\n\t// Kruskal算法找到最小生成树\n\tvoid KruskalMST(PointCloudT::Ptr cloud)\n\t{\n\t\tstd::vector result; // 存储最小生成树的边\n\n\t\t// 将所有边按权重非递减的顺序排序\n\t\tstd::sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b)\n\t\t{\n\t\t\treturn a.weight < b.weight;\n\t\t});\n\n\t\t// 为创建V个子集分配内存\n\t\tSubset* subsets = new Subset[V];\n\t\tfor (int v = 0; v < V; ++v)\n\t\t{\n\t\t\tsubsets[v].parent = v;\n\t\t\tsubsets[v].rank = 0;\n\t\t}\n\n\t\tint i = 0; // 用于选择下一个最小边的索引\n\t\tint e = 0; // 用于选择下一条要包含在MST中的边的索引\n\n\t\t// 要选择的边的数量等于V-1\n\t\twhile (e < V - 1 && i < E)\n\t\t{\n\t\t\tEdge next_edge = edges[i++];\n\n\t\t\tint x = find(subsets, next_edge.src);\n\t\t\tint y = find(subsets, next_edge.tgt);\n\n\t\t\t// 如果包含这条边不会导致环路，则将其加入结果，并增加结果的索引\n\t\t\tif (x != y && next_edge.weight < 0.045)\n\t\t\t{\n\t\t\t\tresult.push_back(next_edge);\n\t\t\t\tUnion(subsets, x, y);\n\t\t\t\t++e;\n\t\t\t}\n\t\t}\n\n\t\t// 创建一个新的点云对象来保存MST的点\n\t\tPointCloudT::Ptr mst_cloud(new PointCloudT);\n\n\t\t// 将MST中的点添加到mst_cloud中\n\t\tfor (const auto& edge : result)\n\t\t{\n\t\t\tconst auto& src_point = cloud->points[edge.src];\n\t\t\tconst auto& tgt_point = cloud->points[edge.tgt];\n\t\t\tmst_cloud->push_back(src_point);\n\t\t\tmst_cloud->push_back(tgt_point);\n\t\t}\n\n\t\t// 将MST保存到PLY文件\n\t\tpcl::io::savePLYFile("D:\DIANYUNWENJIANJIA\newKRUSKAL_ply.ply", mst_cloud);\n\n\t\t// 可视化结果的最小生成树\n\t\tpcl::visualization::PCLVisualizer viewer("最小生成树");\n\t\tviewer.setBackgroundColor(1, 1, 1);\n\n\t\t// 将原始点云添加到视图器中\n\t\tpcl::visualization::PointCloudColorHandlerCustompcl::PointXYZ single_color(cloud, 0, 0, 0);\n\t\tviewer.addPointCloudpcl::PointXYZ(cloud, single_color, "original_cloud");\n\n\t\t// 将最小生成树的边添加到视图器中\n\t\tfor (const auto& edge : result)\n\t\t{\n\t\t\tconst auto& src_point = cloud->points[edge.src];\n\t\t\tconst auto& tgt_point = cloud->points[edge.tgt];\n\t\t\tstd::stringstream ss;\n\t\t\tss << "edge_" << edge.src << "_" << edge.tgt;\n\t\t\tviewer.addLinepcl::PointXYZ(src_point, tgt_point, ss.str());\n\t\t}\n\n\t\t/ Connect two disconnected edges\n\t\tpcl::PointXYZ point1 = cloud->points[55];\n\t\tpcl::PointXYZ point2 = cloud->points[56];\n\t\tviewer.addLine<pcl::PointXYZ, pcl::PointXYZ>(point1, point2, 0, 255, 0, "line");\n\t\t*/\n\t\t// 找到y方向上值最大的节点，并将其标记为绿色\n\t\tstd::unordered_map<int, int> countMap;\n\t\tfor (const auto& edge : result)\n\t\t{\n\t\t\tcountMap[edge.src]++;\n\t\t\tcountMap[edge.tgt]++;\n\t\t}\n\n\t\tpcl::PointCloudpcl::PointXYZ::Ptr jie(new pcl::PointCloudpcl::PointXYZ);\n\t\tint begin = 0;\n\t\tfor (const auto& pair : countMap)\n\t\t{\n\t\t\tif (pair.second >= 3)\n\t\t\t{\n\t\t\t\tstd::cout << "该点坐标： " << pair.first << " 出现 " << pair.second << " 次" << std::endl;\n\t\t\t\tstd::cout << cloud->points[pair.first] << std::endl;\n\t\t\t\tpcl::PointXYZ point3 = cloud->points[pair.first];\n\n\t\t\t\tstd::stringstream sa;\n\t\t\t\tsa << begin;\n\t\t\t\tbegin++;\n\t\t\t\tviewer.addSphere(pcl::PointXYZ(point3), 0.0023, 1, 0, 0, sa.str());\n\t\t\t\tjie->push_back(point3);\n\t\t\t}\n\t\t}\n\n\t\tpcl::PointXYZ maxPoint;\n\t\tpcl::PointXYZ minPoint;\n\t\tfloat maxY = -1;\n\t\tfloat minY = 1;\n\t\tfor (size_t i = 0; i < jie->size(); ++i)\n\t\t{\n\t\t\tpcl::PointXYZ point = jie->at(i);\n\t\t\tif (point.y > maxY)\n\t\t\t{\n\t\t\t\tmaxY = point.y;\n\t\t\t\tmaxPoint = point;\n\t\t\t}\n\t\t\tif (point.y < minY)\n\t\t\t{\n\t\t\t\tminY = point.y;\n\t\t\t\tminPoint = point;\n\t\t\t}\n\t\t}\n\n\t\tstd::cout << "节点上的最高点为 (" << maxPoint.x << ", " << maxPoint.y << ", " << maxPoint.z << ")" << std::endl;\n\t\tstd::cout << "节点上的最低点为 (" << minPoint.x << ", " << minPoint.y << ", " << minPoint.z << ")" << std::endl;\n\n\t\tviewer.addSphere(pcl::PointXYZ(maxPoint), 0.0023, 0, 255, 0);\n\n\t\twhile (!viewer.wasStopped())\n\t\t{\n\t\t\tviewer.spinOnce();\n\t\t}\n\n\t}\n};\n\ndouble euclideanDistance(PointXYZ p1, PointXYZ p2)\n{\n\tdouble dx = p2.x - p1.x;\n\tdouble dy = p2.y - p1.y;\n\tdouble dz = p2.z - p1.z;\n\treturn std::sqrt(dx*dx + dy * dy + dz * dz);\n}\n\nint main()\n{\n\t// 从PLY文件中加载输入点云\n\tpcl::PointCloudpcl::PointXYZ::Ptr cloud(new pcl::PointCloudpcl::PointXYZ);\n\tpcl::io::loadPLYFilepcl::PointXYZ("D:\DIANYUNWENJIANJIA\OUSHIJULEI_ply.ply", *cloud);\n\n\t// 计算点云的质心\n\tEigen::Vector4f centroid;\n\tpcl::compute3DCentroid(*cloud, centroid);\n\n\t// 计算点云的法向量\n\tpcl::NormalEstimation<pcl::PointXYZ, pcl::Normal> ne;\n\tpcl::PointCloudpcl::Normal::Ptr cloud_normals(new pcl::PointCloudpcl::Normal);\n\tpcl::search::KdTreepcl::PointXYZ::Ptr tree(new pcl::search::KdTreepcl::PointXYZ);\n\tne.setInputCloud(cloud);\n\tne.setSearchMethod(tree);\n\tne.setKSearch(10);\n\tne.compute(*cloud_normals);\n\n\t// 创建一个具有V个顶点和E条边的图\n\tint V = cloud->size();\n\tint E = V * (V - 1) / 2;\n\tGraph graph(V, E);\n\n\t// 根据点之间的欧几里得距离计算边的权重\n\tfor (int i = 0; i < V - 1; ++i)\n\t{\n\t\tconst auto& src_point = cloud->points[i];\n\t\tfor (int j = i + 1; j < V; ++j)\n\t\t{\n\t\t\tconst auto& tgt_point = cloud->points[j];\n\t\t\tfloat distance = euclideanDistance(src_point, tgt_point);\n\t\t\tgraph.addEdge(i, j, distance);\n\t\t}\n\t}\n\n\t// 执行Kruskal算法找到最小生成树\n\tgraph.KruskalMST(cloud);\n\n\treturn 0;\n