Auf Thema antworten

Dankeschön für die Mühe! Ich hatte es ähnlich implementiert wie du, nur ohne über ein SortedSet drauf zuzugreifen und ohne den Geraden ein compareTo, equals() oder HashCode() zu spendieren. Bei deiner Implementierung wird es aber wahrscheinlich dasselbe Problem geben: remove() wird oftmals nicht die richtige Gerade finden, bzw. add() nicht feststellen dass es das Objekt an anderer Stelle schon gibt.





An sich wäre es schon möglich, das Problem ist nur, dass der Algorithmus als obere Schranke der amortisierten Laufzeit gerade die Zeit hat die für teuersten Operationen im Baum benötigt werden. Ich probiere jetzt gerade das ganze durch eine TreeMap zu ersetzen und das irgendwie wirksam sortiert zu halten. Sollte es zu ernsteren Erfolgen kommen schreibe ich nochmal :)




Fast, ich benutze einen modifizierten Bentley-Ottmann Algorithmus :) Laut aller Literatur die ich dazu finden konnte ist ein balancierter Baum auch genau das richtige, ich scheine nur etwas Wesentliches zu übersehen.


Naja, ich probiere noch ein wenig herum, ihr braucht euch nicht den Kopf damit zuzukleistern, habt mir schon genug geholfen. Danke an alle! Falls ich des Rätsels Lösung finde schreibe ich nochmal.



Oben