Doppel schnell aus Liste löschen.

[Namenloser]

Ich muss eure Euphorie leider trüben. Die Methode von Dejan Vu liefert unter Umständen falsche Ergebnisse.

Stellt euch mal folgende Punktkonstellation vor:

Code:

            A B





            C

Die Koordinaten sind z.B. A(10.0, 2.0), B(10.001, 2.0), C(10.0, 5.0). A und B sollen im Rahmen des Epsilons als identisch gelten.

Wenn du das jetzt lexikographisch nach sortierst (nach der X-Koordinate zuerst), dann kommt die Reihenfolge A, C, B heraus. A und B werden also nie als Duplikate erkannt, weil sie nach der Sortierung nicht hintereinander stehen.

Das funktioniert leider so nur im Eindimensionalen.

Im Mehrdimensionalen braucht man andere Indexstrukturen, wie K-d-Bäume. Genau für solche Anwendungsfälle, wie die nächsten Nachbarn eines Punktes suchen, wurden die erfunden.