Bentley-Ottmann-Algorithmus für zwei Liniengruppen Segmente

Question

Der Bentley-Ottmann-Algorithmus wird zur Berechnung des Schnittpunkts von Liniensegmenten verwendet.

Anstatt jedoch die Schnittpunkte aller Linien untereinander zu finden, möchte ich die Schnittpunkte zwischen zwei Liniengruppen finden. Das heißt, dass ich für jede Zeile in der Zeilengruppe A die Schnittpunkte zwischen diesen Zeilen und den Zeilen in der Gruppe B erfahren möchte.

Gibt es trotzdem kann ich die Bentley-Ottmann algorithm dafür verlängern? Ich habe bereits den vorhandenen Bentley-Ottmann-Algorithmus implementiert (in the library of CGAL), und ich bin nicht scharf darauf, es zu modifizieren. Ich bin jedoch daran interessiert, Wege zu finden, sie wiederzuverwenden und zu erweitern.

Bearbeiten: Alle anderen Algorithmen (nicht unbedingt auf Bentley-Ottmann basiert) sind willkommen. Es wäre besser, wenn diese Algorithmen bereits in der vorhandenen Bibliothek implementiert sind.

Answer 1

Sie können alle Schnittpunkte zwischen allen Linien in A+B finden, dann entfernen Sie Schnittpunkte zwischen den Linien in demselben Satz. Sie erhöhen die Komplexität nicht um ein Vielfaches und dies ermöglicht Ihnen, die Bibliotheksfunktion von CGAL unverändert mit nur einer einfachen Wrapper-Funktion zu verwenden.

Answer 2

Wo Bentley-Ottman einen Baum von Liniensegmenten hält, die nach ihrer aktuellen vertikalen Position geordnet sind, können Sie nicht zwei Bäume halten, je einen für die Gruppen A und B? Wenn der ursprüngliche Algorithmus dann die Nachbarn oberhalb und unterhalb des aktuellen Punkts überprüft, prüfen Sie den obigen A-Nachbarn gegen den darunter liegenden B-Nachbarn und umgekehrt.

Dies basiert auf einem schnellen Überfliegen des Wikipedia-Artikels; Ich habe in den letzten zehn Jahren nicht viel geometrischen Code geschrieben.

Answer 3

Hinzufügen dieser Antwort für Vollständigkeit, obwohl es möglicherweise nicht die effizienteste Methode für 2 Dimensionen ist.

In 3D-Grafik ist es üblich, 2 KD-Bäume, die alle überlappenden Knoten erkennen können (kann für boolesche Operationen auf Geometrie verwendet werden).

Arbeitsbeispiel (C-Code). https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdopbvh.c;3b4a8f1cfa7339f3db9ddd4a7974b8cc30d7ff0b $ 1089

Wenn es viele kleine Segmente gibt (z. B. den Pfad einer von Hand gezeichneten Linie), wird dies einigermaßen effizient sein. Wenn es jedoch viele lange Kanten gibt (glaube Pick-up-Sticks) ... wird dies schlecht funktionieren, und Sie würden Blattknoten in der BVH-Struktur aufteilen, um bessere Leistung zu erhalten. Wenn dies jedoch der Fall ist, ist es wahrscheinlich besser, eine andere Methode zu verwenden, wie in anderen Antworten vorgeschlagen.

Answer 4

Ja Bentley-Ottmann-Algorithmus kann dazu erweitert werden, zusammen mit anderen Methoden.

In der Literatur beschrieben die Aufgabe, die Sie entlang der Linien von berichteten Kreuzungen zwischen roten und blauen Linien.

Hier ist ein Papier erweitert B-O Sweep zu einem optimalen Algorithmus. http://www.cs.unc.edu/~snoeyink/demos/rbseg/jcdcg25.pdf

Ich würde mit @ Marcogs Behauptung über die Komplexität nicht übereinstimmen. Das Papier verknüpft Ansprüche optimale Zeit von O (n log (n + k)), wenn Sie die Schnittpunkte filtern, müssen Sie einen B-O-Sweep auf allen Linien durchführen, und es wäre ((n + k) log n).

Es gibt noch andere ähnliche Algorithmen, die keine komplexen Datenstrukturen http://www.cs.swarthmore.edu/~adanner/cs97/s08/pdf/palazzi93counting.pdf

Für weniger Kanten und weniger Überschneidungen zwischen den Kanten erfordern kann, die Lösung in gut Antwort Macht Arbeit @ marcog. (Hier ist ein Beispiel von CGAL http://doc.cgal.org/latest/Arrangement_on_surface_2/Arrangement_on_surface_2_2consolidated_curve_data_8cpp-example.html).

Wenn Sie komplexe Polygone (GIS-Daten usw.) verarbeiten müssen oder einen allgemeinen Algorithmus benötigen, lohnt sich diese Klasse von Algorithmen.