Determining and storing Voronoi Cell Adjacency

Question

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.

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.

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.

Thanks!

Answer 1

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