Forum: Algorithmen, Datenstrukturen und Klassendesign
by Namenloser,
22. Aug 2013
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²).
Ist für die asymptotische Laufzeitkomplexität egal.
Ich bin mir...
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Namenloser,
21. Aug 2013
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.
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Namenloser,
21. Aug 2013
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.
Forum: Algorithmen, Datenstrukturen und Klassendesign
by Namenloser,
19. Aug 2013
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......