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