Erhalten eines begrenzten Polygon Koordinaten von Voronoi Zellen
Ich habe Punkte (z. B. lat, lon Paare von Zellen Turmpositionen) und ich muss das Polygon der Voronoi Zellen, die sie bilden.
%Vor%Nun muss ich die Polygongrenzen in Lat-, Lon- Koordinaten für jede Zelle (und was der Schwerpunkt dieses Polygons ist) erhalten. Ich brauche auch diese Voronoi. Das bedeutet, dass die Grenzen nicht in die Unendlichkeit gehen, sondern innerhalb einer Begrenzungsbox.
1 Antwort
Bei einer rechteckigen Boundingbox war meine erste Idee, eine Art Schnittpunktoperation zwischen dieser Begrenzungsbox und dem Voronoï-Diagramm zu definieren, das von scipy.spatial.Voronoi . Eine Idee, die nicht unbedingt großartig ist, da dies eine große Anzahl von Grundfunktionen der Computergeometrie erfordert.
Aber hier kommt mir die zweite Idee (hack?) in den Sinn: Die Algorithmen zur Berechnung des Voronoï-Diagramms einer Menge von n -Punkten in der Ebene haben eine zeitliche Komplexität von O(n ln(n)) . Was ist mit dem Hinzufügen von Punkten, um die Voronoï-Zellen der Anfangspunkte in der Bounding Box zu beschränken?
Lösung für ein begrenztes Voronoï-Diagramm
Ein Bild ist eine großartige Rede wert:
Was ich hier gemacht habe? Das ist ziemlich einfach! Die Anfangspunkte (in blau) liegen in [0.0, 1.0] x [0.0, 1.0] . Dann bekomme ich die Punkte (in blau) auf der linken Seite (d. H.% Co_de%) durch eine Reflexionssymmetrie nach [-1.0, 0.0] x [0.0, 1.0] (linke Kante der Bounding Box). Mit Reflection Symmetries nach x = 0.0 , x = 1.0 und y = 0.0 (andere Kanten der Bounding Box), bekomme ich alle Punkte (in blau) Ich muss den Job machen.
Dann starte ich y = 1.0 . Das vorherige Bild zeigt das resultierende Voronoï-Diagramm (ich verwende scipy.spatial.Voronoi ).
Was ist als nächstes zu tun? Filtern Sie einfach Punkte, Kanten oder Flächen entsprechend der Begrenzungsbox. Und erhalte den Schwerpunkt jedes Gesichts nach der bekannten Formel, um Zentroid des Polygons zu berechnen. Hier ist ein Bild des Ergebnisses (Schwerpunkte sind in rot):
Etwas Spaß bevor Code angezeigt wird
Großartig! Es scheint zu funktionieren. Was, wenn ich nach einer Iteration versuche, den Algorithmus auf den Schwerpunkten (in Rot) anstatt auf den Anfangspunkten (in Blau) erneut auszuführen? Was, wenn ich es immer wieder versuche?
Schritt 2
Schritt 10
Schritt 25
Cool! Voronoï-Zellen neigen dazu, ihre Energie zu minimieren ...
Hier ist der Code
%Vor%Tags und Links python computational-geometry voronoi polygons