建设手机网站费用,数码网站建设维护,提供网站制作公司报价,查看网站建站时间文章目录 一、声明二、简介三、代码C代码Python代码 一、声明
本帖持续更新中如有纰漏望指正#xff01;
二、简介
#xff08;a#xff09;点云建立的k近邻图#xff08;b#xff09;k近邻图上建立的最小生成树
最小生成树 (Minimum Spanning Tree#xff0c;简称 M… 文章目录 一、声明二、简介三、代码C代码Python代码 一、声明
本帖持续更新中如有纰漏望指正
二、简介
a点云建立的k近邻图bk近邻图上建立的最小生成树
最小生成树 (Minimum Spanning Tree简称 MST) 是一种在带权无向图中的树它连接了图中所有节点并且总权重最小。在最小生成树中任意两个节点之间有且仅有一条路径同时这些路径的权重之和最小。 最小生成树的应用场景非常广泛。以下是一些常见的应用场景
网络设计在计算机网络或通信网络中最小生成树可以用来构建最优的网络拓扑结构以便实现高效的数据传输和通信。物流规划在物流管理中最小生成树可以用来确定最短路径从而有效地规划货物的运输路线降低物流成本。电力传输在电力系统中最小生成树可以用于确定电力输电线路的布置确保电力从发电站到各个用户点的传输成本最小。集群分析在数据挖掘和机器学习中最小生成树可以用于聚类分析帮助发现数据点之间的相关性和相似性。电路板设计在电路板设计中最小生成树可以用来确定电路中的连接线路以便最小化电路板的制造成本。
最小生成树算法有多种其中最著名且常用的算法是普里姆算法Prim’s algorithm和克鲁斯卡尔算法Kruskal’s algorithm它们可以高效地找到最小生成树。
三、代码
C代码
#include boost/graph/adjacency_list.hpp
#include boost/graph/kruskal_min_spanning_tree.hpp
#include iostream
#include vectorint main() {// Define the graph using adjacency_listtypedef boost::adjacency_listboost::vecS, boost::vecS, boost::undirectedS,boost::no_property, boost::propertyboost::edge_weight_t, int Graph;typedef boost::graph_traitsGraph::edge_descriptor Edge;typedef boost::property_mapGraph, boost::edge_weight_t::type WeightMap;// Create a graph objectGraph g;// Add edges to the graphadd_edge(0, 1, 2, g);add_edge(1, 2, 3, g);add_edge(0, 3, 1, g);// ... Add other edges as needed// Vector to store the resulting MST edgesstd::vectorEdge spanning_tree;// Compute the minimum spanning tree using Kruskals algorithmboost::kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));// Print the edges in the MSTfor (std::vectorEdge::iterator ei spanning_tree.begin(); ei ! spanning_tree.end(); ei) {std::cout source(*ei, g) -- target(*ei, g) with weight of get(boost::edge_weight, g, *ei) std::endl;}return 0;
}
Python代码
import open3d as o3d
import numpy as np
import networkx as nx
from scipy.spatial import KDTree
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3Ddef create_knn_graph(point_cloud, k):# Convert Open3D point cloud to numpy arraypoints np.asarray(point_cloud.points)# Build a KDTree for efficient nearest neighbor searchtree KDTree(points)# Create a graphG nx.Graph()# Add nodes and edges based on k nearest neighborsfor i in range(len(points)):distances, indices tree.query(points[i], kk1) # k1 because the point itself is includedfor j in range(1, k1): # Skip the first one (itself)G.add_edge(i, indices[j], weightdistances[j])return Gdef find_mst(graph):# Compute the minimum spanning treereturn nx.minimum_spanning_tree(graph)def plot_3d_graph(graph, pos_3d):# Create a 3D plotfig plt.figure(figsize(8, 6))ax fig.add_subplot(111, projection3d)# Extract the x, y, z coordinates of each nodexs, ys, zs zip(*[pos_3d[node] for node in graph.nodes()])# Plot the nodesax.scatter(xs, ys, zs)# Plot the edgesfor edge in graph.edges():x_coords, y_coords, z_coords zip(*(pos_3d[edge[0]], pos_3d[edge[1]]))ax.plot(x_coords, y_coords, z_coords, colorblue)# Set labels and show plotax.set_xlabel(X axis)ax.set_ylabel(Y axis)ax.set_zlabel(Z axis)# plt.show()plt.axis(equal)plt.savefig(1.png)# Load point cloud
pcd o3d.io.read_point_cloud(1.ply) # Adjust the file path# Create the kNN graph (choose your k)
k 5 # For example, k5
knn_graph create_knn_graph(pcd, k)# Find the minimum spanning tree
mst find_mst(knn_graph)# Extract positions from the 3D point cloud
pos_3d {i: pos for i, pos in enumerate(np.asarray(pcd.points))}# Plot the 3D graph of the minimum spanning tree
plot_3d_graph(mst, pos_3d)
