Znajdowanie regionów voronoi, które zawierają listę dowolnych współrzędnych

Question

Pracuję z algorytmem, który dla każdej iteracji musi znaleźć region diagramu Voronoi, do którego należy zestaw koordynatów arborystycznych. to znaczy, w którym regionie znajduje się każda współrzędna. (Możemy założyć, że wszystkie współrzędne będą należeć do regionu, jeśli czyni żadnej różnicy.)

nie mam żadnego kodu, który działa w Pythonie jeszcze, ale kod pseudo wygląda mniej więcej tak:

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

Wiem, że scipy.Delaunay ma funkcję o nazwie find_simplex, która zrobi prawie tyle, ile chcę dla simplices w triangulacji Delaunay, ale potrzebuję diagramu Voronoi, a skonstruowanie obu jest czymś, czego chcę uniknąć.

Pytania:

1. Czy istnieje biblioteka jakiegoś, który pozwoli mi to zrobić łatwo?

2. Jeśli nie, czy istnieje dobry algorytm, na który mogę popatrzeć, co pozwoli mi to zrobić skutecznie?

Aktualizacja

rozwiązanie Jamiego jest dokładnie to, co chciałem. Jestem trochę zawstydzony, że sam o tym nie pomyślałem ...

Answer 1

Nie musisz właściwie obliczyć regionów Voronoi. Z definicji region Voronoi wokół punktu w twoim zestawie składa się ze wszystkich punktów, które są bliższe temu punktowi niż do jakiegokolwiek innego punktu w zestawie. Musisz tylko obliczyć odległości i znaleźć najbliższego sąsiada. Korzystanie scipy na cKDTree można zrobić:

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 Teraz trzyma tablicę kształt (n_test, 1) z indeksami punktów w voronoi_points najbliżej siebie swojego test_points.