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

У меня пока нет кода, который работает на 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. Если нет, есть ли хороший алгоритм, на который я мог бы обратить внимание, который позволит мне сделать это эффективно?

Обновить

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