geradliniger Polygonschnittpunkt

Das Buch Algorithmische Geometrie: Eine Einführung von Preparata und Shamos hat ein Kapitel über geradlinige Polygone.

Verwenden Sie einen Sweepline-Algorithmus, der die Tatsache nutzt, dass ein geradliniges Polygon durch seine Eckpunkte definiert wird.

Stellen Sie die Scheitelpunkte zusammen mit dem Rechteck dar, zu dem sie gehören, also etwa wie (x, y, #rect) . Fügen Sie zu dieser Punktmenge die Punkte hinzu, die sich aus den Schnittpunkten aller Kanten ergeben. Diese neuen Punkte haben die Form (x, y, final) , da wir bereits wissen, dass sie zu der resultierenden Menge von Punkten gehören.

Jetzt:

• Sortiere alle Punkte nach ihrem x-Wert
• benutze eine Sweep-Linie, beginnend bei der ersten x-Koordinate; für jeden neuen Punkt:
  • Wenn es sich um einen "Startpunkt" handelt, fügen Sie es zu einem temporären Set T hinzu. Markieren Sie "final", wenn es sich um einen Punkt von Rechteck A und zwischen y-Koordinaten von Punkten von Rechteck B in T (oder umgekehrt) handelt.
  • Wenn es ein "Endpunkt" ist, entferne es und den entsprechenden Startpunkt von T.

Danach bezeichnen alle Punkte, die mit "final" markiert sind, die Eckpunkte des resultierenden Polygons.

N sei die Gesamtzahl der Punkte. Unter der Annahme, dass das Testen, ob wir einen Punkt als "final" markieren sollen, Zeit O (log (n)) erfordert, indem wir T nachschlagen, liegt dieser ganze Algorithmus in O (N * log (N)).

Beachten Sie, dass die Aufgabe, alle Schnittpunkte zu finden, in den obigen Algorithmus integriert werden kann, da das effiziente Auffinden aller Schnittpunkte selbst in der Regel ein Sweep-Line-Algorithmus ist. Beachten Sie auch, dass die resultierende Menge von Punkten mehr als ein Polygon enthalten kann, wodurch es etwas schwieriger wird, die Lösungspolygone aus den "letzten" Scheitelpunkten zu rekonstruieren.