Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding voronoi regions that contain a list of arbitrary coordinates

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 ...

like image 412
inconvergent Avatar asked Jul 25 '13 11:07

inconvergent


People also ask

How do I get from Delaunay to Voronoi?

The Voronoi diagram is just the dual graph of the Delaunay triangulation. So, the edges of the Voronoi diagram are along the perpendicular bisectors of the edges of the Delaunay triangulation, so compute those lines. Then, compute the vertices of the Voronoi diagram by finding the intersections of adjacent edges.

How do you calculate the Voronoi edge?

for each Voronoi vertex v do if v is inside H: v H then Compute radius of circle centered on v and update max. for each Voronoi edge e do Compute p = e H, the intersection of e with the hull boundary.


1 Answers

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.

like image 143
Jaime Avatar answered Oct 06 '22 00:10

Jaime