Finden von Voronoi-Regionen, die eine Liste von beliebigen Koordinaten enthalten
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 ...