Voronoi单元邻接关系的确定与存储

Question

我会用上千个点。我可以实现或使用Fortunes算法的现有实现来生成点的Voronoi图，但是我的应用程序还要求我知道每个Voronoi单元的邻接关系。在

更具体地说，对于任何Voronoi细胞，我需要知道与之相邻的细胞。在这一点上，我不关心输出或存储方法，因为我可能会对一个实现进行按摩，使其对我有利。在

有没有人知道一种算法，或者更好地知道一种可以实现单元邻接判定的算法？我将要做的工作是在python中，但是任何事情都会很好，因为我可以轻松地翻译代码。在

谢谢！在

Answer 1

你可以用几种不同的方法。在

如果您可以访问Voronoi图，您可以在单元之间查找共享的边段。如果发现两个单元共享Voronoi边段，则表示它们相邻。建立整个数据集的邻接信息的一种有效方法是通过扫描Voronoi单元列表来建立边缘哈希表。在

for (all cells in voronoi diagram)
    for (all edges in current cell)
        if (matching edge found in hash table)
            // the current cell is adjacent to the cell that added
            // the matching edge segment to the hash table
        else
            // push current edge segment onto hash table and mark with 
            // current cell index
        endif
    endfor
endfor

有许多很好的现有软件包可用于计算点集的Voronoi图/Delaunay三角剖分。由于这是一个计算开销大且对数字敏感的操作，我建议使用现有的库。Triangle和{a2}包被广泛使用。在

希望这有帮助。在

Answer 2

一个可能的算法是可用的here 它使用线性规划方法。在

PuLP可以生成MPS或LP文件并调用GLPK、COIN、CPLEX、和{a5}来解决线性问题。在

PuLP是一个用Python编写的LP建模器，可以用来在Python中建模这个线性程序，然后使用GLPK进行求解。在

Answer 3

虽然这是一个老问题，但我一直在寻找同样的答案，并认为这个答案对某些人还是有帮助的。可以从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()