Ich möchte Voronoi und seine duale Delaunay-Triangulation berechnen. Ich verwende den Watson-Bowyer-Algorithmus. Mein Ziel danach ist es, Alpha-Formen (konkave Hüllen) zu berechnen. Also muss ich für einen bestimmten Punkt, die Nachbarn, schnell auf die Voronoi-Zelle zugreifen ...

Welche Datenstrukturen haben Sie für Ihren Voronoi / Delaunay-Algorithmus verwendet? Ich habe darüber nachgedacht, eine disjunkte Mengen-Datenstruktur mit Union-Find-Operationen zu verwenden, damit ich an ein übergeordnetes Element binden kann, den Punkt p im ursprünglichen Datensatz, den Punktsatz in Vp. Ein Punkt im Voronoi-Diagramm gehört jedoch zu mehreren Voronoi-Zellen.

Was ist Ihr Rat oder könnten Sie auf eine gute Referenz hinweisen?

Grüße.