Delphi-PRAXiS - Bentley-Ottmann-Algorithmus Verständnisfrage

Seite 1 von 2

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)

- Algorithmen, Datenstrukturen und Klassendesign (https://www.delphipraxis.net/78-algorithmen-datenstrukturen-und-klassendesign/)

- - Bentley-Ottmann-Algorithmus Verständnisfrage (https://www.delphipraxis.net/176196-bentley-ottmann-algorithmus-verstaendnisfrage.html)

Bentley-Ottmann-Algorithmus Verständnisfrage

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?