Нахождение вороной областей, содержащих список произвольных координат

Question

Я работаю с алгоритмом, который для каждой итерации должен найти, к какой области диаграммы Вороного принадлежит набор произвольных координат. в какой области находится каждая координата. (Мы можем предположить, что все координаты будут принадлежать области, если это имеет какое-либо значение.)

У меня пока нет кода, который работает на Python, но псевдокод выглядит примерно так:

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

Я знаю, что у scipy.Delaunay есть функция find_simplex, которая будет делать в значительной степени то, что я хочу для симплексов в триангуляции Делоне, но мне нужна диаграмма Вороного, и я хочу избегать построения обоих.

Вопросы:

1. Есть ли какая-нибудь библиотека, которая позволит мне сделать это легко?

2. Если нет, есть ли хороший алгоритм, на который я мог бы обратить внимание, который позволит мне сделать это эффективно?

Обновить

Решение Джейми именно то, что я хотел. Я немного смущен тем, что сам не думал об этом...

Answer 1

Для этого вам не нужно рассчитывать регионы Вороного. По определению область Вороного вокруг точки в вашем наборе состоит из всех точек, которые находятся ближе к этой точке, чем к любой другой точке в наборе. Так что вам нужно только рассчитать расстояния и найти ближайших соседей. Используя Сципи cKDTree Вы могли бы сделать:

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 Теперь содержит массив формы (n_test, 1) с индексами точек в voronoi_points ближе к каждому из ваших test_points,