#include ///'iostream///'//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 ///'vector///'//n#include ///'unordered_map///'//n#include ///'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// 可视化结果的最小生成树///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}//n运行处结果保存到/'D:////DIANYUNWENJIANJIA////newKRUSKAL_ply.ply/'内容：Sorry, but I can't run this code for you as it requires the input file /'D:////DIANYUNWENJIANJIA////OUSHIJULEI_ply.ply/' and it will save the result to /'D:////DIANYUNWENJIANJIA////newKRUSKAL_ply.ply/