Ich arbeite mit einem Algorithmus, der für jede Iteration herausfinden muss, zu welcher Region eines Voronoi-Diagramms eine Reihe von willkürlichen Koordinaten gehört. das heißt, in welchem ​​Bereich sich jede Koordinate befindet. (Wir können davon ausgehen, dass alle Koordinaten zu einer Region gehören, wenn dies einen Unterschied macht.)

Ich habe noch keinen Code, der in Python funktioniert, aber der Pseudocode sieht ungefähr so ​​aus:

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

Ich weiß, dass der scipy.Delaunay eine Funktion namens find_simplex hat, die ziemlich genau das tut, was ich für Vereinfachungen in einer Delaunay-Triangulation will, aber ich brauche das Voronoi-Diagramm, und beides zu konstruieren ist etwas, das ich vermeiden möchte.

Fragen:

1. Gibt es eine Bibliothek, mit der ich das ganz einfach machen kann?

2. Wenn nicht, gibt es einen guten Algorithmus, mit dem ich das effizient erledigen kann?

Aktualisieren

Jamies Lösung ist genau das, was ich wollte. Es ist mir ein wenig peinlich, dass ich selbst nicht daran gedacht habe ...