Pracuję z algorytmem, który dla każdej iteracji musi znaleźć region diagramu Voronoi, do którego należy zestaw współrzędnych arbirary. 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 to ma jakieś znaczenie).

Nie mam jeszcze żadnego kodu, który działa w Pythonie, ale pseudo kod 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 to, co chcę dla uproszczeń w triangulacji Delaunaya, ale potrzebuję diagramu Voronoi, a konstruowanie obu jest czymś, czego chcę uniknąć.

pytania:

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

2. Jeśli nie, czy istnieje dobry algorytm, który mógłbym zobaczyć, który pozwoli mi to zrobić efektywnie?

Aktualizacja

Rozwiązanie Jamiego jest dokładnie tym, czego chciałem. Jestem trochę zakłopotany, że sam o tym nie pomyślałem ...