Intersect n Liniensegmente (auf ganzzahligem Gitter)

Question

Ich habe ein Problem, das fast wie ein klassisches CS-Problem aussieht, alle Schnittpunkte von bestimmten Liniensegmenten zu finden.

Die leichte Modifikation ist die Tatsache, dass:
1. Ich alle Segmente an ihren Schnittpunkten
2. Die resultierenden Teilsegmente haben ganzzahlige Koordinaten müssen aufteilen müssen.

Wenn ich einfach den Standard-Sweepline-Algorithmus anwende, um alle Schnittpunkte zu finden und die Koordinaten dieser Punkte auf Integer umsetze, bekomme ich manchmal neue Schnittpunkte, die durch das Verschieben von Schnittpunkten auf das Integer-Gitter verursacht werden.

Ich kann diesen Algorithmus wiederholt anwenden, und wahrscheinlich (ich kann es nicht beweisen), in einer begrenzten Anzahl von Schritten erreichen einen Zustand, in dem ich keine neuen Schnittpunkte finden. Aber ich bin überzeugt, dass es eine einfachere, elegantere Lösung geben muss.

Ich habe versucht, ein Papier über einen solchen Algorithmus zu finden, aber irgendwie konnte ich keinen finden, der genau dieses Problem behandeln würde.

Kannst du mich auf solch ein Pape hinweisen, oder auf eine Beschreibung eines Algorithmus, der von Grafikbibliotheken (wie Boost Polygon Library) verwendet wird?

Vielen Dank.

Answer 1

Dies ist eine interessante Variante des Liniensegment-Schnittpunktproblems. Das ursprüngliche Problem, Koordinaten des Schnittpunkts dieser Segmente zu finden, kann mit dem Line Sweep-Algorithmus gelöst werden.

Here ist ein eingehender Artikel, der über Line-Sweep-Technik-Implementierung für das obige Problem spricht. Damit kann der Schnittpunkt in der Zeit O (n * logn) gefunden werden.

Um nun die ganzzahligen Koordinaten zu finden, können Sie die Schnittpunkte erzeugen. Aber hier müssen Sie sich über die Richtung des Castings (die später in der Konvergenz helfen wird) sicher sein.

Wenn C in einem Schnittpunkt auf dem Liniensegment AB, dann teilen Sie es in AC und CB. In AC, werfen Sie C in Richtung A, während in CB Sie es in Richtung B werfen. (Mit Richtung meine ich nicht entlang der Liniensegment-Richtung, sondern entlang der Halbebene, die einen anderen Endpunkt enthält.) Dies stellt sicher, dass die Länge des Liniensegments nach jedem Schnittpunkt verringert wird.

BEWEIS: Betrachten, M maximale Länge eines Liniensegments sein. Jedes Mal, wenn ein Schnittpunkt darauf liegt, wird die Länge des neuen Liniensegments um mindestens eine Einheit reduziert. So Anzahl von Iterationen durch M
So begrenzt ist, insgesamt Iterationen des Algorithmus nicht überschreiten M.

Komplexität = O (M * n * log n)