Eu estou trabalhando com um algoritmo que, para cada iteração, precisa encontrar em qual região de um diagrama de Voronoi um conjunto de coordenadas arbóreas pertence. isto é, em qual região cada coordenada está localizada. (Podemos supor que todas as coordenadas pertencerão a uma região, se isso fizer alguma diferença).

Eu não tenho nenhum código que funcione em Python ainda, mas o pseudo código é algo como isto:

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

Eu sei que o scipy.Delaunay tem uma função chamada find_simplex que fará praticamente o que eu quero para simplificar em uma triangulação de Delaunay, mas eu preciso do diagrama de Voronoi, e construir ambos é algo que eu gostaria de evitar.

Questões:

1. Existe alguma biblioteca que me permita fazer isso facilmente?

2. Se não, existe um bom algoritmo que eu poderia olhar que me permita fazer isso de forma eficiente?

Atualizar

A solução de Jamie é exatamente o que eu queria. Estou um pouco envergonhada por não ter pensado nisso ...