确定和存储Voronoi细胞邻接 [英] Determining and storing Voronoi Cell Adjacency

问题描述

我将处理数千个点。我可以实现或使用财富算法的现有实现来生成点的Voronoi图，但是我的应用程序还要求我了解每个Voronoi单元的邻接关系。

I will be working with a set of thousands of points. I can implement or use existing implementations of Fortunes Algorithm to produce the Voronoi diagram of the points, but my application also requires me to know adjacency with respect to each Voronoi Cell.

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

More specifically, for any Voronoi cell I need to know the cells that are adjacent to this. At this point I'm not to concerned with output or storage method as I can likely massage an implementation to work in my favor.

有人知道一种算法，或者更好地意识到一种可以完成小区邻接确定的算法吗？我将做的工作是在python中进行，但是任何事情都将是很棒的，因为我可以轻松地翻译代码。

Is anyone aware of an algorithm, or better yet aware of an implemented algorithm that can accomplish cell adjacency determination? The work I will be doing is in python, but anything would be great as I can easily translate the code.

谢谢！

推荐答案

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

Although this is an old question, I was searching for same and thought that the answer might still be helpful for somebody. One can use Delaunay from scipy module.

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()

这篇关于确定和存储Voronoi细胞邻接的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！