context.triangles
says in which Delaunay triangles input point participate. Each triangle is related to a Voronoi vertex. Triangles and vertices are stored parallel in triangles
and vertices
arrays.
To find Voronoi cell for a given point p
, it is needed to find all vertices (triangles) in which input point is used. And than find order how these vertices are connected by edges
array.
Here is a simple (not quite tested) code to do that:
from voronoi import voronoi
import random
from collections import defaultdict
num_points = 50
points = [(random.uniform(0,10), random.uniform(0,10)) for i in xrange(num_points)]
c = voronoi(points)
# For each point find triangles (vertices) of a cell
point_in_triangles = defaultdict(set)
for t_ind, ps in enumerate(c.triangles):
for p in ps:
point_in_triangles[p].add(t_ind)
# Vertex connectivity graph
vertex_graph = defaultdict(set)
for e_ind, (_, r, l) in enumerate(c.edges):
vertex_graph[r].add(l)
vertex_graph[l].add(r)
def cell(point):
if point not in point_in_triangles:
return None
vertices = set(point_in_triangles[point]) # copy
v_cell = [vertices.pop()]
vertices.add(-1) # Simulate infinity :-)
while vertices:
neighbours = vertex_graph[v_cell[-1]] & vertices
if not neighbours:
break
v_cell.append(neighbours.pop())
vertices.discard(v_cell[-1])
return v_cell
for p in xrange(num_points):
print p, cell(p)