Haltepunktkonvergenz in Fortune's Algorithmus

Question

Ich implementiere den Sweepline-Algorithmus von Fortune, um Voronoi-Diagramme zu berechnen. Meine primäre Referenz ist "Rechengeometrie: Algorithmen und Anwendungen" von De Berg et al., Und während ihre Abdeckung des Themas sehr klar ist, passieren sie mehrere kleine, aber wichtige Details, die ich habe, dass ich Probleme habe. Ich habe das Web zur Hilfe durchsucht, aber andere Websites geben entweder noch einen noch höheren Überblick als das Lehrbuch oder geben den gleichen Pseudocode, der vom Buch bereitgestellt wird.

Ich brauche einen Weg, um zu bestimmen, ob ein Paar von Haltepunkten, die von einem dreifachen Bögen an der Strandlinie an der Strandlinie entschieden werden, konvergiert oder divergiert, um bevorstehende Kreisereignisse zu erkennen. Es scheint, dass ich eine Entscheidung treffen würde, dass ich Wissen über die Form der Voronoi-Zellkanten benötigen würde, die die Haltepunkte als Fortune-Algorithmus fortschreiten. Wenn ich beispielsweise die Neigung der von einem Haltepunkt verfolgten Kante finden könnte, könnte ich berechnen, wo die beiden durch die Haltepunkte gebildeten Linien und ihre jeweiligen Hänge kreuzen, und entscheiden, ob sie basierend auf diesem Ergebnis konvergieren. Ich habe jedoch keine Ahnung, wie Sie Informationen auf den Pisten erhalten, nur die aktuelle Position der Haltepunkte.

Die einzigen Informationen, mit denen ich zusammenarbeiten muss, ist der X-, Y-Ort der drei Standorte und der aktuellen Y-Koordinate des Sweepline (ich verwende ein horizontales Sweepline).

Eigentlich habe ich eine Idee, um die Konvergenz zu bestimmen. Angesichts von zwei Standorten wird der Haltepunkt zwischen den beiden Abschnitten der Strahlenlinie, die sie definieren, nur durch die aktuelle Position der Sweep-Linie regiert. Ich dachte darüber nach, die Position der beiden Haltepunkte aufzunehmen, wodurch die Sweep-Linie vorübergehend einen kleinen Betrag vorrückte und ihre neuen Positionen aufzeichnet. Da Kanten in einem normalen Voronoi-Diagramm nicht krümmen, wenn der Abstand zwischen dem neuen Paar von Haltepunkten geringer ist als der Abstand zwischen dem alten Paar, dann konvergieren die Haltepunkte; Ansonsten divergieren sie. Aber das scheint sowohl gefährlich (ich habe keine Ahnung, ob es immer arbeitet) und hässlich. Sicher muss es einen besseren Weg geben.

Irgendwelche Ideen würden erkennen, und Pseudocode (in einer c # -ähnlichen Syntax, falls möglich), besonders so. Ich bin mir auch bewusst, dass es sich um rechnerische Geometrie-Bibliotheken gibt, die ich verwenden könnte, um Voronoi-Diagramme zu erhalten, aber dies ist eine persönliche Lernübung, also möchte ich alle Teile des Algorithmus selbst umsetzen.

Answer 1

Welcome Drake. Ich habe es implementiert, indem ich geprüft habe, ob die Haltepunkte in einem "fiktiven" Inkrement der Sweepline-Position physisch konvergieren. Dies kompliziert sich tatsächlich ein bisschen, da das Kreiszentrum in bestimmten Fällen in bestimmten Fällen fast oder genau an der Sweepline-Position sein kann, sodass das Sweepline-Inkrement proportional zu der Differenz zwischen der aktuellen Sweepline-Position und dem von Ihnen generierten Kreiszentrum ist.

sagen:

1. currentSweeplineY = 1.0f; circleCenterY = 0.5f (und wir bewegen uns nach unten, d. H. in der abnehmenden y-Richtung).

2. Set sweepYIncrement = (circleCenterY - currentSweepLineY) / 10.0f (der 10,0f-Divisor 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 dies wahrscheinlich sehr teuer ist, da Sie die Haltepositionen mehrmals berechnen müssen, aber ich bin zuversichtlich, dass es um alle möglichen Fälle kümmert wird.

Jedenfalls finde ich ernsthafte Probleme mit dem Floating Point-Präzisionsfehler an anderer Stelle im Algorithmus. Definitiv nicht so unkompliziert, wie ich anfangs dachte.

Answer 2

Das ist also eher peinlich, aber nach dem Schlafen an dem Problem scheint die Antwort offensichtlich. Ich schreibe dies, um Hoffentlich den Schülern in der Zukunft mit der gleichen Frage bei mir zu helfen.

Die Voronoi-Kante zwischen zwei Standorten senkt senkrecht das (imaginäre) Liniensegment, das die Sites verbindet. Sie könnten die Steigung der Kante ableiten, indem Sie die Senkrechten der Steigung des Verbindungsleitungssegments nehmen, und dann einen Linienkreuzungstest an den beiden Kanten durchführen, es gibt jedoch noch einfacherer Weg.

solange drei Standorte sind, sind nicht Collinear , dann tangieren die Kanten, die die Segmente zwischen den Stellen senkrecht durchsetzen, auch an den Kreis, dessen Kante alle drei Standorte enthält. Daher konvergieren die Haltepunkte, die durch ein Dreibettzimmer von Voronoi-Sites zusammengeführt werden, wenn das von den drei Standorten definierte Mitte des Kreises vor dem mittleren -ort ist, wobei "in vorne" und "hinter" von der Koordinate abhängen System- und Sweepline-Ausrichtung, die Sie gewählt haben.

In meinem Fall habe ich ein horizontales Sweeple, das ich von minimal y bis maximal y bewegt, so dass die Haltepunkte zusammenlaufen, wenn die Y-Koordinate der Mitte des Kreises größer ist als die Y-Koordinate der mittleren Stelle, und anderweitig divergieren.

edit: Kristian d'amato weist zu Recht darauf hin, dass der Algorithmus oben einige Konvergenzfälle verfehlt. Der endgültige Algorithmus, den ich endete, ist unten. Natürlich bin ich nicht zuversichtlich, dass es 100% richtig ist, aber es scheint für alle Fälle zu arbeiten, an denen ich es ausprobiert habe. generasacodicetagpre.

Answer 3

Wenn die Sites im Uhrzeigersinn um die Mitte des Kreises bestellt werden, konvergiert der Bogen.Wenn sie gegen den Uhrzeigersinn um die Mitte des Kreises bestellt werden, divergiert der ARC.(oder umgekehrt, abhängig von Ihrer Implementierung).Die Prüfung von CW- oder CCW fällt aus dem Code, den Sie verwenden, um die Mitte des Kreises zu finden.

Hier ist ein Snippet des C # -Codes zum Berechnen des Umschweigers D der Punkte A, B, C: generasacodicetagpre.