Doppel schnell aus Liste löschen.

[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.

[Bjoerk]

Ich hab mehrere Tests mit dem Code #47 durchgeführt. Scheint zu stimmen. Weiß aber nicht wieso?

Falls jemand probieren möchte (Testform):

[Namenloser]

@Dejan Vu: Das war jetzt nicht auf das Beispiel bezogen sondern allgemein.

Solange es immer nur Paare von zusammengehörenden Punkten gibt, sollte es wohl kein Problem geben. Problematisch könnte es aber werden, wenn es mehr als zwei zusammengehörige Punkte gibt.

Könnte sein, dass du z.B. irgendwie in einer Reihe die Punkte a b c d hast, wobei jeder Punkt zu seinen Nachbarn, und nur zu seinen Nachbarn, „gleich“ ist. Dann könnte es womöglich passieren, dass der Algorithmus die Punkte durcheinanderwürfelt und a c b d daraus macht oder so, sodass anschließend wieder keine Duplikate erkannt werden. Genau überlegt habe ich es mir nicht, ich warne nur.

Allerdings ist eh etwas unklar, was in einem solchen Fall passieren soll, wie du ja auch schon angemerkt hast.

[Dejan Vu]

Perfekt ist das Verfahren nicht. Aber wir verstehen es wenigstens. Bei so einem Kd-Baum oder spacial indexes müsste ich mich erst mal reinfräsen.

Zitat von Bjoerk:

Ich hab mehrere Tests mit dem Code #47 durchgeführt. Scheint zu stimmen. Weiß aber nicht wieso?

Also darauf würde ich mich jetzt mal nicht verlassen. Der zweite Sortiervorgang könnte die Ordnung durcheinanderbringen (instabiles Sortierverfahren).

Klappt mein Code nicht? Immerhin wird nur 1x sortiert und schnell ist er auch und ich glaube auch, das er korrekt ist . Und hör mit dem 'Delete' auf, das ist doch Grottenlangsam.

[Bjoerk]

Hier nein. Das Delete ist der Witz an der Sache. Sonst würde es nicht funktionieren. SortX und SortY müssen auf verschiedene Listen angewendet werden, sonst hat man nur SortY (Siehe auch Namenloser).

[Horst_]

Hallo,

da bin ich missverstanden worden...
Beim Versuch mit kleinem eps

Delphi-Quellcode:

procedure TFloatPointsTestForm.RemoveDoublesButtonClick(Sender: TObject);
const
  Eps = 1E-3;

steigt das Programm sofort aus.

Gruß Horst

[Bjoerk]

Nein, ich hatte nur das als letzte Möglichkeit gesehen um nicht groß am Code ändern zu müssen. Gut. Dann wäre das jetzt geklärt, daß es auch so nicht geht. Danke Horst. Allerdings steigt das Progamm nicht aus, sondern eine MessageBox wird angezeigt, daß FLoatPoints.RemoveDoubles nicht erfolgreich war. Dann kann man das mit der Sort Variante hier vergessen. Daß ich sattdessen im Code nun auf if List.IndexOf(Value) < 0 prüfe bevor Elemente hinzugefügt werden hab ich ja schon geschrieben.

Edit: Man könnte auch zuerst nach x sortieren und in Listen mit gleichen X splitten und dann nach y sortieren und später wieder zusammenfügen. Hab jetzt aber kein Bock mehr auf das Thema (zumindest heute nicht mehr).

[Dejan Vu]

Zitat von Dejan Vu:

Klappt mein Code nicht?

Zitat von Bjoerk:

Hier nein.

Echt? Geht Doch.

Delphi-Quellcode:

Function ComparePoints(Const P1, P2 : TFloatPoint) : Integer;
Begin
  Result := SortCompareX(p1,p2);
  if Result = 0 then REsult := SortCompareY(p1,p2);
End;

procedure TFloatPoints.FastRemoveDoubles;
var
  i,j : Integer;

Begin
  QuickSort(0,Count-1,ComparePoints);
  j:=0;
  For i:=1 to Count - 1 do
    if ComparePoints(Fitems[i],fItems[j])<>0 then begin
      inc(j);
      fItems[j] := fItems[i];
    end;
  fCount := j;
End;

Oder hatte ich was anderes geschrieben?

Im älteren Code von dir schien aber die Quicksort-Methode nicht richtig zu sortieren, jedenfalls bei mir. Aber jetzt scheint alles in Ordnung zu sein.

[Bjoerk]

Nein, so kann man keine Koordinaten sortieren (Siehe auch Namenloser und Horst). BTW, bei deiner FastAddPoints, fehlen da nicht die FillChars, TFLoatPoint ist doch ein Record?

Sort muss z.B. so:

Delphi-Quellcode:

procedure TFloatPoints.Sort(const RemoveDoubles: boolean);
const
  Eps = 1E-4;
var
  X: double;
  I, J: integer;
  NewList, SortList: TFloatPoints;
begin
  if FCount > 1 then
  begin
    NewList := TFloatPoints.Create;
    try
      SortList := TFloatPoints.Create;
      try
        SortByX;
        I := 0;
        while I < FCount do
        begin
          SortList.Clear;
          X := FItems[I].X;
          while (I < FCount) and (SameValue(X, FItems[I].X, Eps)) do
          begin
            SortList.Add(FItems[I]);
            Inc(I);
          end;
          SortList.SortByY;
          if RemoveDoubles then
          begin
            for J := SortList.Count - 1 downto 1 do
              if SameFloatPoint(SortList[J], SortList[J - 1]) then
                SortList.Delete(J);
          end;
          NewList.AddPoints(SortList);
        end;
        Assign(NewList);
      finally
        SortList.Free;
      end;
    finally
      NewList.Free;
    end;
  end;
end;