Ich muss eure Euphorie leider trüben. Die Methode von Dejan Vu liefert unter Umständen falsche Ergebnisse.
Stimmt nicht. A,B und C wird als A,B,C sortiert. Der X-Wert ist für A,B und C wird als "identisch" angesehen, also wird nach Y sortiert und dann stimmt es.
Das ganze Verfahren hat einen ganz anderen Haken: Nehmen wir an, wir haben 3 Punkte (P1 - P3), die alle um 1E-4 (=eps) von einander entfernt sind. Sagen wir, in X-Richtung. Y ist überall identisch. (also P[i+1].X = P[i].X + eps*0.99). Welche Punkte sollen übrigbleiben? Es kommt darauf an, welchen Punkt ich als 'Referenz nehme'.
A) P1 ist Referenz. Dann ist P2 nahe an P1, also weg. P3 ist zu weit von P1 weg, bleibt also => (P1,P2,P3) => (P1,P3)
B) P2 ist Referenz. Sowohl P1 als auch P3 sind nahe an P2, also weg => (P1,P2,P3)=> (P2)
Hashmap funktioniert dann auch nicht, weil zwei eng nebeneinanderliegende Punkte in unterschiedliche Raster fallen könnten. Der eine Punkt P1 liegt ganz rechts im Quadrant X, und der andere Punkt P2 ganz links im Quadranten X+1 (also dem rechts daneben) und obwohl P2.X-P1.X < Eps, sind die Quadranten unterschiedlich: Mein Nachbar ist in einem anderen Bezirk (Berlin) als ich, genauso blöd, d.h. wir haben unterschiedliche Postleitzahlen
Wenn man das 'richtig' machen will, muss man die von Namenlosen erwähnten Ansätze verwenden.
Als grobe 'Entdoppelung' sollte das Rasterverfahren (nichts anderes ist ja die Sortierung und die Eliminierung mit Epsilon) jedoch ausreichen.
Man kann auch das zweistufige Verfahren von Horst_ nehmen, wobei man nach der Sortierung nach X die von mir o.g. Problematik berücksichtigen könnte. Aber ob das jetzt was bringt, glaube ich nicht, weil man ja wieder rastert.
Das Quicksort nicht stabil ist, ist hier unerheblich: Wenn A und B 'identisch' sind, ist es egal, ob erst A vor B ist oder umgekehrt. Nicht die Sortierung ist das Problem, sondern die Ordnungsfunktion ('Compare'), die eine willkürliche Rasterung vornimmt sowie die willkürliche Wahl eines 'Referenzpunktes' für die Bestimmung von Clustern. Hier müsste man für jeden Cluster den Punkt 'in der Mitte' nehmen und von dem aus alle Nachbarn (dx<eps und dy<eps) eliminieren.