我将使用成千上万的积分.我可以实现或使用Fortunes算法的现有实现来生成点的Voronoi图,但是我的应用程序还要求我知道每个Voronoi Cell的相邻性.

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

是否有人知道算法,或者更好地了解可以完成单元邻接确定的已实现算法？我将要做的工作是在python中,但是任何事情都会很棒,因为我可以轻松地翻译代码.

谢谢！

解决方法:

虽然这是一个老问题,但我一直在寻找相同的东西,并认为答案可能对某些人有用.可以使用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()