Bentley-Ottmann-Algorithmus Verständnisfrage

[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

[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:
scr6294_20130820.png

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.