Bentley-Ottmann-Algorithmus Verständnisfrage

[Blup]

Zitat:

Zitat von NamenLozer (Beitrag 1225850)

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.

Muss man nicht, man kennt aus der Reihenfolge in der Y-Liste in welcher Reihenfolge von Oben nach Unten die Linien durch die Sweep-Linie geschnitten werden.

So wie ich die Beschreibungen verstanden habe ist bei der Y-Liste nie von Punkten die Rede.
Der Algo sieht vor das Linien eingefügt, innerhalb der Liste getauscht oder entfernt werden.

In der X-Liste werden allerdings tatsächlich Punkte eingefügt.
Punkte an denen Linien beginnen oder enden und die Schnittpunkte.

Bin mal gespannt auf deine Implementation.