我将使用一组数千个点。我可以实现或使用现有的财富算法实现来生成点的 Voronoi 图，但我的应用程序还要求我知道每个 Voronoi 单元的邻接关系。
更具体地说，对于任何 Voronoi 单元，我需要知道与其相邻的单元。在这一点上，我不关心输出或存储方法，因为我可能会按摩实现以对我有利。
有没有人知道算法，或者更好地知道可以完成小区邻接确定的已实现算法？我将要做的工作是在 python 中，但任何事情都会很棒，因为我可以轻松地翻译代码。
谢谢！
问问题
3637 次
3 回答
11
尽管这是一个老问题，但我一直在寻找相同的问题，并认为答案可能对某人仍有帮助。可以Delaunay从scipy模块中使用。
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()
于 2013-05-28T12:51:27.560 回答
3
你可以通过几种不同的方式做到这一点。
如果您只能访问 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和QHull包被广泛使用。
希望这可以帮助。
于 2012-03-11T09:42:26.227 回答