python - 确定和存储 Voronoi Cell Adjacency

Question

我将使用包含数千个点的集合。我可以实现或使用 Fortunes Algorithm 的现有实现来生成点的 Voronoi 图，但我的应用程序还要求我了解每个 Voronoi 单元的邻接关系。

更具体地说，对于任何 Voronoi 单元，我需要知道与其相邻的单元。在这一点上，我不关心输出或存储方法，因为我可能会调整一个实现以对我有利。

有没有人知道一种算法，或者更好的是知道可以完成小区邻接确定的已实现算法？我将要做的工作是用 python，但任何东西都会很棒，因为我可以轻松翻译代码。

谢谢!

Answer 1

尽管这是一个老问题，但我一直在寻找相同的问题，并认为答案可能对某些人仍然有帮助。可以使用 scipy 模块中的 Delaunay。

from scipy.spatial import Delaunay
from collections import defaultdict
import itertools

points=[[0.0, 0.0], [0.0, 1.0], [0.2, 0.5], [0.3, 0.6], [0.4, 0.5], [0.6, 0.3], [0.6, 0.5], [1.0, 0.0], [1.0, 1.0]]
tri = Delaunay(points)
neiList=defaultdict(set)
for p in tri.vertices:
    for i,j in itertools.combinations(p,2):
        neiList[i].add(j)
        neiList[j].add(i)

for key in sorted(neiList.iterkeys()):
    print("%d:%s" % (key,','.join([str(i) for i in neiList[key]])))

0:1,2,5,7
1:0,8,2,3
2:0,1,3,4,5
3:8,1,2,4,6
4:2,3,5,6
5:0,2,4,6,7
6:8,3,4,5,7
7:8,0,5,6
8:1,3,6,7
   
# This is for visualization
from scipy.spatial import Voronoi, voronoi_plot_2d
import matplotlib.pyplot as plt
vor = Voronoi(points)
voronoi_plot_2d(vor)
for i,p in enumerate(x):
    plt.text(p[0], p[1], '#%d' % i, ha='center')
plt.show()