在Python中生成一个随机平面图

Question

我正在寻找一种在Python中生成随机的平面图，大约有20个顶点。我查看了这个平面图生成器，但出现了两个问题：

1. 上述GitHub项目中的算法似乎有点过于复杂，以生成没有那么多边的随机平面图
2. 因为它旨在生成大规模图形，所以该算法非常复杂，因此也有点笨重和难以使用

有了这些说法，是否有更简单的方法在python中随机生成一个相对较小的平面图呢？

- Emilio

Answer 1

Create required number of nodes
Assign random x,y locations to the nodes.
WHILE nodes with no connected edges
    Select N a random node with no edge
    LOOP select M a different node at random
        IF edge N-M does NOT intersect previous edges
             Add N-M edge to graph
             BREAK out of LOOP

- ravenspoint

---

我不确定 IF edge N-M does NOT intersect previous edges 的意思。我猜这意味着“如果添加N-M不会使图形非平面化”。检查平面性并不那么简单。 - Gene

非常简单。只需谷歌查找线段相交检测，或是任何一本解析几何教材。 - ravenspoint

你能提供一个更实际的例子吗？特别是在检查边缘是否与其他边缘相交的部分。 - Emilio

你想让别人帮你谷歌吗？真是难以置信。https://zh.wikipedia.org/wiki/%E7%9B%B4%E7%BA%BF%E7%9B%B4%E7%BA%BF%E4%BA%A4%E7%82%B9%E5%BC%8F - ravenspoint

这是最简单的算法之一，但必须注意，它生成的样本来自于一种非常特定的随机连通平面图分布。使用不同的方法几乎肯定会产生不同的分布。例如：G = networkx.some_random_generator(...); while not networkx.is_planar(G): G = networkx.some_random_generator(...) - Ron Kaminsky

Answer 2

该算法的核心是将 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

#we create a function to generate a planar graph from a voronoi diagram

def voronoi_to_networkx(points):
# we get the voronoi diagram
  vor = Voronoi(points)

  G = nx.Graph()

# Add an edge for each ridge in the Voronoi diagram that connects two points in the range [0,1] 
  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) # Calculate the Euclidean distance between p and q
              G.add_edge(tuple(p), tuple(q),weight=distance)

  return G

#We create 20 points from which the voronoi diagram will be generated
points=np.random.rand(20,2)

#we plot the diagram
vor=Voronoi(points)
voronoi_plot_2d(vor)
plt.show()

#We convert diagram to networkx
graph=voronoi_to_networkx(points)
#We assign each node to its actual position in the plane
pos = dict(zip(graph.nodes(), graph.nodes()))
nx.draw(graph, pos,node_size=5)
#We check that the graph is planar.
print(nx.is_planar(graph))
plt.show()

- diego garcia tinajero