Doppel schnell aus Liste löschen.

[Bjoerk]

Ok. Thanx. Schau ich mir an.

Als letzter Versuch fäll tmir noch das ein? Der Quicksort ist ja unfassbar schnell. Ist das so korrekt?

Delphi-Quellcode:

function SortCompareX(const A, B: TFLoatPoint): integer;
const
  Eps = 1E-4;
begin
  Result := CompareValue(A.X, B.X, Eps);
end;

function SortCompareY(const A, B: TFLoatPoint): integer;
const
  Eps = 1E-4;
begin
  Result := CompareValue(A.Y, B.Y, Eps);
end;

function SortCompareXY(const A, B: TFLoatPoint): integer;
begin
  if SortCompareX(A, B) = 0 then
    Result := SortCompareY(A, B)
  else
    Result := 0;
end;

procedure TFloatPoints.Sort;
begin
  if FCount > 1 then
  begin
    QuickSort(0, FCount - 1, SortCompareX);
    QuickSort(0, FCount - 1, SortCompareXY);
  end;
end;

[Namenloser]

Ich bezweifel es, aber einen Gegenbeweis kann ich jetzt nicht direkt liefern.

Ein paar Dinge, die man berücksichtigen sollte:
- Du hast bei Quicksort keinen Einfluss darauf, welche Paare miteinander verglichen werden und in welcher Reihenfolge
- Die „Gleichheit“ von Float-Werten ist keine Äquivalenzrelation, die Transitivität ist nicht erfüllt. Also macht es eben wohl einen Unterschied in welcher Reihenfolge die Elemente verglichen werden.
- Quicksort ist nicht stabil. Bei mir schrillen deshalb die Alarmglocken, wenn ich sehe, dass du zwei Sortiervorgänge direkt hintereinander ausführst. Was auch immer du dir davon erhoffst, wird nicht erfüllt sein.

Ich denke, man kann dieses Problem prinzipiell nicht mit eindimensionaler Sortierung lösen, egal was für eine ausgeklügelte Sortierung man sich einfallen lässt.

[Bjoerk]

Der QuickSort hat die unangenehme Angewohnheit, daß wenn es Beispielsweise in einer Adressenverwaltung 2 Hans Müller in 12345 Berlin gibt, und man die Adressen nach Postleitzahl sortiert, daß einmal der eine und einmal der andere Müller vorne stehen kann. M.E. hat das hier aber keinen Einfluß, weil identisch und hintereinander (Wenn 2 Durchläufe). Ich weiß es aber eben auch nicht genau ..

[Namenloser]

Das Ding ist, dass durch deinen zweiten Sortiervorgang der erste theoretisch komplett zunichte gemacht wird. Instabil heißt ja gerade, dass eine wie auch immer geartetet Vorsortierung nicht erhalten bleibt. Wenn der erste Sortiervorgang also irgendeinen Einfluss hat, dann ist das lediglich Zufall, und du kannst dich im Allgemeinen nicht darauf verlassen.

[Horst_]

Hallo,

also wäre es geschickter alle Punkte nach x zu sortieren und anschliessend nur einen Bereich von x_center+-eps zu betrachten und diesen nach y zu sortieren und zu untersuchen.( Sweep-line )
Anschliessend wandert man um ein eps weiter.
Das ist viel Sortiererei, aber man kann sich merken, wie x_center+eps nach y sortiert war. Das wird im nächsten Schritt ja x_center-eps.Da bietet sich ja mergesort an.

Gruß Horst

[Dejan Vu]

Zitat von Namenloser:

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.

[Bjoerk]

Stimmt. Leider.. Das Thema macht mich echt fertig. Horst, und wieso jetzt plötzlich das funzt? Keinen Plan.. Man findet im Netz über Delphi Koordinaten Sortieren fast nichts.

Delphi-Quellcode:

procedure TFloatPoints.ProbablyRemoveDoubles;
var
  I: integer;
begin
  SortbyX;
  for I := FCount - 1 downto 1 do
    if Util_SameFloatPoint(FItems[I], FItems[I - 1]) then
      Delete(I);
  SortbyY;
  for I := FCount - 1 downto 1 do
    if Util_SameFloatPoint(FItems[I], FItems[I - 1]) then
      Delete(I);
end;

Bis auf weiteres hab ich an den wichtigsten Stellen if List.IndexOf(Value) < 0 then List.Add(Value) ergänzt und ruf die RemoveDoubles gar nicht mehr auf.

[Dejan Vu]

Die Idee von Horst bringt doch nichts. Ob ich die Daten erst nach X sortiere, oder mit dem SamePoint gleich einmal durch, ist doch egal: Punkte, die bezüglich des X-Wertes nahe beieinander liegen, werden bezüglich des Y-Wertes sortiert. Somit liegen fast gleiche Punkte auch nebeneinander, weil sie durch die Vergleichsfunktion als 'Identisch' betrachtet werden.

Es wird keine totale Ordnung auf den numerischen X- und Y-Werten aufgebaut!

Such mal lieber nach kd-Baum oder 2D-Index. Oder frag den Namenlosen, der scheint Ahnung davon zu haben

[Namenloser]

Zitat von Dejan Vu:

Zitat von Namenloser:

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 Problem ist: Quicksort setzt eigentlich eine Halbordnung voraus. Der Fuzzy-Vergleich ist aber keine, da die Transitivität (a ≤ b und b ≤ c ⇒ a ≤ c) nicht erfüllt ist. Und zwar ist sie das dann nicht, wenn a und b nahe genug bei einander liegen um als „gleich“ zu gelten, und b und c auch, aber a und c nicht.

Ich bin mir nicht sicher, inwieweit einem das auf die Füße fallen kann. Aber man müsste jedenfalls erst mal beweisen, dass der Quicksort-Algorithmus unter diesen Voraussetzungen überhaupt funktioniert.

[Dejan Vu]

Doch, a, b und c werden bezüglich des X-Wertes als identisch angesehen.

Zitat:

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.

Die Vergleichsfunktion "V" wird folgende Ergebnisse liefern:
V(A,B)=> 0
V(A,C)=> -1 (A<B)
V(B,C)=> -1 (B<C)

Also wird so sortiert (A,B,C) oder (B,A,C).... Aber egal wie, B (oder A) wird immer eliminiert.

Beweisen ist natürlich toll, aber kurzes Nachdenken reicht auch:
1. Der Sortieralgorithmus wird 'identische' Werte unmittelbar aufeinanderfolgend sortieren, jedoch in willkürlicher Reihenfolge.
2. Der Eliminationsalgorithmus wird jede Sequenz von 'identischen' Werten W1...WN durch W1 ersetzten, und die Werte W2...WN aus der Liste entfernen. Hierfür wird die gleiche Vergleichsfunktion wie beim Sortieren verwendet, d.h. die Definition von 'identisch' ist bei beiden Algorithmen die gleiche.