该算法的核心是将 Voronoi 图转换为加权图,其中 Voronoi 图是基于平面上特定子集中点到距离的分区。在 Python 中,这个加权图由 networkx 对象表示。
算法的输入是二维空间中的点列表。使用 scipy.spatial 库计算 Voronoi 图,返回表示该图的顶点和边的集合。
然后,算法遍历 Voronoi 图的边,并检查每条边是否连接两个坐标范围在 [0,1] 内的点。如果是,则将该边作为 networkx 图中的一条边添加,其权重等于该边两端点之间的欧几里得距离。
最后,返回生成的 networkx 图作为输出。该图将 Voronoi 图表示为加权图,其中顶点对应于输入列表中的点,边表示 Voronoi 区域之间的边界,边上的权重表示这些边界的长度。
Voronoi 图本身可以被视为平面图,其中顶点表示输入点,边表示 Voronoi 区域之间的边界。该图可用于各种应用,例如地理信息系统、计算机视觉和计算几何。
import numpy as np
import networkx as nx
from scipy.spatial import Voronoi,voronoi_plot_2d
import matplotlib.pyplot as plt
def voronoi_to_networkx(points):
vor = Voronoi(points)
G = nx.Graph()
for simplex in vor.ridge_vertices:
if -1 not in simplex:
i, j = simplex
p = vor.vertices[i]
q = vor.vertices[j]
if 0 <= p[0] <= 1 and 0 <= p[1] <= 1 and 0 <= q[0] <= 1 and 0 <= q[1] <= 1:
distance = np.linalg.norm(p - q)
G.add_edge(tuple(p), tuple(q),weight=distance)
return G
points=np.random.rand(20,2)
vor=Voronoi(points)
voronoi_plot_2d(vor)
plt.show()
graph=voronoi_to_networkx(points)
pos = dict(zip(graph.nodes(), graph.nodes()))
nx.draw(graph, pos,node_size=5)
print(nx.is_planar(graph))
plt.show()
IF edge N-M does NOT intersect previous edges
的意思。我猜这意味着“如果添加N-M不会使图形非平面化”。检查平面性并不那么简单。 - Gene