Trovare regioni Voronoi che contengono un elenco di coordinate arbitrarie

Question

sto lavorando con un algoritmo che, per ogni iterazione, ha bisogno di trovare la zona della Voronoi diagramma un insieme di coordinats arbirary appartengono. cioè, quale regione ciascuna coordinata si trova all'interno. (Si può presumere che tutte le coordinate apparterranno ad una regione, se questo fa alcuna differenza.)

non ho alcun codice che funziona in Python ancora, ma il codice pseudo simile a questa:

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

So che lo scipy.Delaunay ha una funzione chiamata find_simplex che farà praticamente quello che voglio per i simplices in una triangolazione di Delaunay, ma ho bisogno del diagramma di Voronoi, e la costruzione di entrambi è qualcosa che desidero evitare.

Domande:

1. C'è una biblioteca di qualche tipo che mi permette di farlo facilmente?

2. In caso contrario, c'è un buon algoritmo potevo guardare che mi permetta di fare questo in modo efficace?

Aggiornamento

soluzione di Jamie è esattamente quello che volevo. Sono un po 'imbarazzato che non pensavo di me stesso anche se ...

Answer 1

Non è necessario calcolare effettivamente le regioni di Voronoi per questo. Per definizione la regione di Voronoi attorno ad un punto nel set è composto da tutti i punti che sono più vicini a quel punto che a qualsiasi altro punto nel set. Quindi, avete solo bisogno di calcolare le distanze e trovare vicini più prossimi. Utilizzando SciPy di ​​cKDTree si potrebbe fare:

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 detiene ora una serie di forma (n_test, 1) con gli indici dei punti in voronoi_points più vicino a ciascuno dei tuoi test_points.