Bentley-Ottmann-Algorithmus Verständnisfrage

[Namenloser]

Morgen,

ich möchte mithilfe des Bentley-Ottmann-Algorithmus die Schnittpunkte einer Menge von Strecken bestimmen. Ich habe auf mehreren Seiten dazu recherchiert und der Algorithmus wird immer gleich beschrieben und so habe ich ihn so implementiert, aber er funktioniert nicht, auch nicht, wenn ich ihn manuell mit mit Stift und Papier ausführe. Also irgendwas muss ich falsch verstanden haben...

Ich kopier hier mal den übersichtlichsten Pseudocode (Quelle) rein, den ich gefunden habe (die Beschreibung auf Wikipedia und Co. ist aber äquivalent):

Code:

Q := the 2n segment end-points
D := {}
while Q <> {} do begin
     p := DELETEMIN(Q);

     if p is the left end-point of si then begin
          INSERT(si,D);
          A := ABOVE(si,D);
          B := BELOW(si,D);
          INSERT (in Q) A intersect si and B intersect si if they exist and are to the right of p
     end

     if p is the right end-point of si then begin
          A := ABOVE(si,D);
          B := BELOW(si,D);
          DELETE(si,D);
          INSERT (in Q) A intersect B if it exists and if it is to the right of p
     end

     if p := si intersect sj then begin
          {suppose si := ABOVE(sj)}
          INTERCHANGE(si,sj,D);
          A := ABOVE(sj,D);
          B := BELOW(si,D);
          INSERT (in Q) A intersect sj and B intersect si if they exist and are to the right of p
          REPORT(p);
     end

end

• Ich fange im Beispiel (Anhang) also ganz links an, am linken Endpunkt der Strecke a. Die füge ich in den Baum ein. Weiter ist nichts zu tun, weil sonst noch nichts im Baum ist.
  
• Als nächstes finde ich den linken Endpunkt von b. Den füge ich in den Baum ein, er landet über a. Ich prüfe den Schnittpunkt von a und b, aber einen solchen gibt es nicht, also passiert nichts.
  
• Das nächste Event ist der linke Endpunkt von c. Eingefügt im Baum landet er über b und a. Der Algorithmus schreibt vor, dass ich nur mit dem direkt darüber- und darunterliegnenden Segment auf Schnittpunkte prüfe – darüber liegt keiner; direkt darunter liegt b. Aber b und c schneiden sich nicht, also passiert wieder nichts.
  
• Als nächstes kommt der Endpunkt von a. Der würde im Baum ganz oben liegen, also über c, b und a. Der Algorithmus schreibt vor, dass ich die unmittelbaren Nachbarn finde, und prüfe, ob diese sich schneiden. In diesem Fall gibt es nur einen Nachbarn (c) also wird wieder nichts geprüft? a wird nun aus dem Baum entfernt.
  
  Den Rest kann ich mir sparen, denn nun ist ja schon jegliche Chance vertan, den Schnittpunkt überhaupt noch zu finden...

Wo liegt mein Fehler?

[Mikkey]

Zitat von NamenLozer:

Als nächstes kommt der Endpunkt von a. Der würde im Baum ganz oben liegen, also über c, b und a. Der Algorithmus schreibt vor, dass ich die unmittelbaren Nachbarn finde, und prüfe, ob diese sich schneiden. In diesem Fall gibt es nur einen Nachbarn (c) also wird wieder nichts geprüft? a wird nun aus dem Baum entfernt.

Wenn ich den Pseudocode richtig interpretiere, solltest Du an dieser Stelle den Schnittpunkt von a mit c finden.

Allerdings finde ich den Algorithmus anbetracht dessen, dass er so viele Sonderfälle einfach ausschließt (die also Sonderbehandlungen erfordern), weniger glücklich.

Ich könnte mir vorstellen, dass man mit dem Ansatz, dass zwei sich schneidende Linien eine nichtleere Teilmenge ihrer umgebenden Rechtecke haben müssen, direkt einfacher ans Ziel kommt.

Gruß, Mikkey

[Blup]

Zitat:

Als nächstes finde ich den linken Endpunkt von b. Den füge ich in den Baum ein, er landet über a.

Die Y-Liste enthält die "aktiven Linien" sortiert nach dem Schnittpunkt mit der "Sweep-Linie".
Soll eine neue Linie hinzugefügt werden, müssen die Schnittpunkte der vorhandenen Linien mit der "Sweep-Linie" neu bestimmt werden, damit die neue Linie an der richtigen Stelle eingefügt werden kann.
In diesem Fall wird b unter a eingefügt.

[Medium]

Zitat:

Ich könnte mir vorstellen, dass man mit dem Ansatz, dass zwei sich schneidende Linien eine nichtleere Teilmenge ihrer umgebenden Rechtecke haben müssen, direkt einfacher ans Ziel kommt.

Das haben allerdings auch sich nicht schneidende Strecken.

[Mikkey]

Zitat von Medium:

Das haben allerdings auch sich nicht schneidende Strecken.

Natürlich, aber es schränkt die erforderliche Anzahl von Prüfungen ebenfalls erheblich ein

[Namenloser]

Danke für eure Antworten!

Ich glaube, ich weiß jetzt was falsch ist... wenn man auf den linken Endpunkt einer Linie stößt, muss man trotzdem beide Endpunkte in den Baum einfügen. Getestet habe ich es allerdings noch nicht, also vielleicht melde ich mich doch noch mal.

[Blup]

Nein, in den Y-Baum (eigentlich eine Liste) fügt man Linien ein, nicht einzelne Punkte.
Beim Einfügen einer Linie vergleicht man den linken Punkt dieser Linie mit dem aktuellen Schnittpunkt der anderen Linien der Liste an dieser X-Position ("Sweep-Linie").
Dadurch wird die Einfügeposition in der Liste bestimmt.

[Namenloser]

Zitat von Blup:

Nein, in den Y-Baum (eigentlich eine Liste) fügt man Linien ein, nicht einzelne Punkte.
Beim Einfügen einer Linie vergleicht man den linken Punkt dieser Linie mit dem aktuellen Schnittpunkt der anderen Linien der Liste an dieser X-Position ("Sweep-Linie").
Dadurch wird die Einfügeposition in der Liste bestimmt.

Es kann nicht sein, dass an jedem Punkt der Schnittpunkt der Sweepline mit allen aktiven Segmenten neu berechnet wird, weil der Algorithmus dann mindestens eine Worst-Case-Komplexität von Θ(n²) hätte statt O((n+k) log n).

Nimm folgendes Szenario mit n Linien an:


Der Sinn des Algorithmus ist ja aber gerade, quadratisches Laufzeitverhalten zu vermeiden.

[Blup]

Die Neuberechnung betrifft nur die Linien, mit denen tatsächlich verglichen wird.
Die Steigung jeder Linie muss man nur einmal je Linie vorberechnen.
Dann beschränkt sich die Neuberechnung auf eine Multiplikation und eine Addition.
Vergleicht man jeweils die neue Linie in der Mitte der Menge der Linien, halbiert sich die für den Vergleich relevante Menge durchschnittlich mit jedem Vergleich.
Man benötigt also ca. 8 Berechnungen und Vergleiche um eine neue Linie in eine Liste mit 256 aktiver Linien einzufügen.

[Namenloser]

Zitat von Blup:

Die Neuberechnung betrifft nur die Linien, mit denen tatsächlich verglichen wird.

Erst mal müsste man ja wissen, mit welchen Linien man überhaupt vergleichen muss, und dazu müsste man bei deiner Vorgehensweise die aktuellen Schnittpunkte aller Kandidaten mit der Sweepline kennen. Also muss man im Worstcase für bis zu O(n) Linien die Schnittpunkte mit der Sweepline neu berechnen, und das für n Linien → O(n²).

Zitat von Blup:

Die Steigung jeder Linie muss man nur einmal je Linie vorberechnen.
Dann beschränkt sich die Neuberechnung auf eine Multiplikation und eine Addition.

Ist für die asymptotische Laufzeitkomplexität egal.

Ich bin mir zu 95% sicher, dass das, was ich gestern geschrieben habe, stimmt. Ich habe es mehrfach auf dem dem Papier durchgespielt und es hat in allen Fällen funktioniert, und es passt auch zu den Beschreibungen des Bentley-Ottman-Algorithmus. Deine Vorgehensweise taucht dagegen in keiner Beschreibung auf. Sie würde zwar auch funktionieren (auf Kosten einer schlechteren Laufzeitkomplexität), aber der Bentley-Ottman-Algorithmus geht nun mal anders.

Trotzdem Danke fürs Mitdenken!