Ich implementiere den Sweepline-Algorithmus von Fortune zur Berechnung von Voronoi-Diagrammen. Meine wichtigste Referenz ist "Computational Geometry: Algorithms and Applications" von de Berg et al., Und obwohl sie das Thema sehr klar abdecken, gehen sie auf einige kleine, aber wichtige Details ein, die ich selbst nicht selbst erarbeiten konnte. Ich habe im Internet nach Hilfe gesucht, aber andere Websites bieten entweder einen noch besseren Überblick als das Lehrbuch oder geben genau den gleichen Pseudocode wie das Buch.
Ich brauche einen Weg, um zu bestimmen, ob ein Paar Haltepunkte, die durch ein Tripel von Bögen auf der Strandlinie bestimmt sind, konvergiert oder divergiert, um bevorstehende Kreisereignisse zu erkennen. Es scheint, dass ich für eine Entscheidung Wissen über die Form der Voronoi-Zellenränder benötigen würde, die die Haltepunkte bei Fortschreiten des Fortune-Algorithmus nachzeichnen. Wenn ich zum Beispiel die Steigung der Kante finden könnte, die von einem Haltepunkt verfolgt wird, könnte ich berechnen, wo sich die zwei durch die Haltepunkte und ihre jeweiligen Steigungen gebildeten Linien schneiden, und basierend auf diesem Ergebnis entscheiden, ob sie konvergieren. Allerdings habe ich keine Ahnung, wie man Informationen über die Pisten bekommt, nur die aktuelle Position der Haltepunkte.
Die einzige Information, mit der ich arbeiten muss, ist die x, y-Position der drei Stellen und die aktuelle y-Koordinate der Messlinie (ich verwende eine horizontale Messlinie).
Eigentlich habe ich eine Idee, um die Konvergenz zu bestimmen. Bei zwei Standorten wird der Haltepunkt zwischen den beiden Abschnitten der Strandlinie nur durch die aktuelle Position der Sweep-Linie bestimmt. Ich dachte darüber nach, die Position der beiden Haltepunkte aufzuzeichnen, die Sweep-Linie vorübergehend etwas vorzurücken und ihre neuen Positionen aufzunehmen. Da Kanten in einem normalen Voronoi-Diagramm nicht gekrümmt sind, wenn der Abstand zwischen dem neuen Paar von Unterbrechungspunkten kleiner als der Abstand zwischen dem alten Paar ist, konvergieren die Unterbrechungspunkte; ansonsten divergieren sie. Aber das scheint sowohl gefährlich (ich habe keine Ahnung, ob es immer funktioniert) und hässlich. Sicherlich muss es einen besseren Weg geben.
Irgendwelche Ideen würden geschätzt werden, und Pseudocode (in einer C # -ähnlichen Syntax, wenn möglich) besonders so. Ich weiß auch, dass es Berechnungsbibliotheken gibt, mit denen ich Voronoi-Diagramme erstellen kann, aber das ist eine persönliche Lernübung, daher möchte ich alle Teile des Algorithmus selbst implementieren.
Willkommen Drake. Ich habe es implementiert, indem ich überprüft habe, ob die Haltepunkte in einem "fiktiven" Inkrement der Position der Suchlinie physikalisch auf dem Kreismittelpunkt konvergieren. Dies verkompliziert sich tatsächlich ein wenig, weil in bestimmten Fällen der Kreismittelpunkt fast oder genau an der Pfeillinienposition liegen kann, so dass das Pfeillinieninkrement proportional zu der Differenz zwischen der aktuellen Pfeillinienposition und dem erzeugten Kreismittelpunkt sein muss. p>
Sprich:
1. currentSweeplineY = 1.0f ; circleCenterY = 0.5f (und wir bewegen uns abwärts, d. h. in der abnehmenden y-Richtung).
2. Set sweepYIncrement = (circleCenterY - currentSweepLineY) / 10.0f (der 10.0f-Teiler wird willkürlich gewählt).
3. Check new breakpoint positions at new sweepline position .
4. Check distance to circle center .
5. If both distances are less than current distances, the breakpoints converge .
Ich weiß, dass das wahrscheinlich sehr teuer ist, da Sie die Haltepunktpositionen mehrfach berechnen müssen, aber ich bin zuversichtlich, dass es sich um alle möglichen Fälle kümmert.
Jedenfalls finde ich gravierende Probleme mit Gleitkomma-Präzisionsfehlern an anderen Stellen im Algorithmus. Definitiv nicht so einfach wie ich anfangs dachte.
Das ist also ziemlich peinlich, aber nachdem ich über das Problem geschlafen habe, scheint die Antwort offensichtlich. Ich schreibe dies, um den Schülern hoffentlich in Zukunft die gleiche Frage zu stellen wie ich.
Die Voronoi-Kante zwischen zwei Stellen halbiert senkrecht das (imaginäre) Liniensegment, das die Orte verbindet. Sie könnten die Neigung der Kante ableiten, indem Sie die Senkrechte der Neigung des Verbindungsliniensegments nehmen und dann einen Linienschnitttest an den beiden Kanten durchführen, aber es gibt einen noch einfacheren Weg.
Solange drei Seiten nicht sind kollinear , dann tangieren die Kanten, die die Segmente zwischen den Stellen senkrecht halbieren, auch den Kreis, dessen Kante alle drei Stellen enthält. Daher konvergieren die durch ein Tripel von Voronoi-Seiten definierten Haltepunkte, wenn der Mittelpunkt des durch die drei Stellen definierten Kreises vor der mittleren Stelle liegt, wobei "vor" und "hinten" von der Koordinate abhängen System- und Metrikausrichtung, die Sie gewählt haben.
In meinem Fall habe ich eine horizontale Bewegungslinie, die ich von minimalem y zu maximalem y bewege, so dass die Bruchpunkte konvergieren, wenn die y-Koordinate des Mittelpunkts des Kreises größer ist als die y-Koordinate des mittleren Ortes. und divergieren sonst.
Edit: Kristian D'Amato weist mit Recht darauf hin, dass der obige Algorithmus einige Konvergenzfälle vermisst. Der letzte Algorithmus, den ich benutzt habe, ist unten. Natürlich bin ich nicht sicher, dass es zu 100% korrekt ist, aber es scheint für alle Fälle zu funktionieren, in denen ich es ausprobiert habe.
%Vor%Wenn die Orte im Uhrzeigersinn um die Mitte des Kreises angeordnet sind, konvergiert der Bogen. Wenn sie gegen den Uhrzeigersinn um die Mitte des Kreises angeordnet sind, divergiert der Bogen. (oder umgekehrt, abhängig von Ihrer Implementierung). Das Testen auf cw oder ccw fällt nicht in den Code, den Sie verwenden, um das Zentrum des Kreises zu finden.
Hier ist ein Ausschnitt aus C # -Code zur Berechnung des Umkreismittelpunkts d der Punkte a, b, c:
%Vor%Tags und Links algorithm breakpoints computational-geometry voronoi