Finding voronoi regions that contain a list of arbitrary coordinates

Question

I am working with an algorithm that, for each iteration, needs to find which region of a Voronoi diagram a set of arbirary coordinats belong to. that is, which region each coordinate is located within. (We can assume that all coordinates will belong to a region, if that makes any difference.)

I don't have any code that works in Python yet, but the the pseudo code looks something like this:

## we are in two dimensions and we have 0<x<1, 0<y<1.

for i in xrange(1000):
  XY = get_random_points_in_domain()
  XY_candidates = get_random_points_in_domain()
  vor = Voronoi(XY) # for instance scipy.spatial.Voronoi
  regions = get_regions_of_candidates(vor,XY_candidates) # this is the function i need

  ## use regions for something

I know that the scipy.Delaunay has a function called find_simplex which will do pretty much what I want for simplices in a Delaunay triangulation, but I need the Voronoi diagram, and constructing both is something I wish to avoid.

Questions:

1. Is there a library of some sort that will let me do this easily?

2. If not, is there a good algorithm I could look at that will let me do this efficiently?

Update

Jamie's solution is exactly what I wanted. I'm a little embarrassed that I didn't think of it myself though ...

Answer 1

You don't need to actually calculate the Voronoi regions for this. By definition the Voronoi region around a point in your set is made up of all points that are closer to that point than to any other point in the set. So you only need to calculate distances and find nearest neighbors. Using scipy's cKDTree you could do:

import numpy as np
from scipy.spatial import cKDTree

n_voronoi, n_test = 100, 1000

voronoi_points = np.random.rand(n_voronoi, 2)
test_points = np.random.rand(n_test, 2)

voronoi_kdtree = cKDTree(voronoi_points)

test_point_dist, test_point_regions = voronoi_kdtree.query(test_points, k=1)

test_point_regions Now holds an array of shape (n_test, 1) with the indices of the points in voronoi_points closest to each of your test_points.