Doppel schnell aus Liste löschen.

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

[Dejan Vu]

Zitat von Bjoerk:

Nein, so kann man keine Koordinaten sortieren (Siehe auch Namenloser und Horst).

Natürlich kann man das. Beide liegen mit welchen Überlegungen daneben bzw. bestätigen meine Einschränkung:
Unter der Prämisse, das man mit den hier vorgestellten Verfahren eh kein vollständiges 'Ersetze Cluster von sehr nahe beieinanderliegenden Punkten durch einen Referenzpunkt und minimiere dabei die Gesamtanzahl der Punkte' bekommt, sind die Lösungen alle äquivalent. Dein Test "gibt es nach dem 'removeduplicates' noch 'identische' Punkte" meldet auch bei meinem einfachen Scan keine Doppelten. Was willst Du denn noch? Zeig mir doch einfach, *was* daran falsch sein soll. Oder lass es sein und mach weiter so im produzieren von Code

Edit: Nicht falsch verstehen, ich finde das Thema recht interessant, würde nur gerne wissen, was dich an der offensichtlich einfachsten und schnellsten Lösung stört?

[Bjoerk]

Bud, ich versteh dich nicht falsch. Mit eindimensionaler Sortierung kann man das hier (wenn überhaupt) nur bei mit stabilen Sortierverfahren so machen.

[Horst_]

Hallo,

ich habe endlich den casus cnactus gefunden.
Deine SortCompareX darf nur mit eps= 0 arbeiten.Ich habe wie blöd gesucht, warum größere x-Werte vor kleineren auftauchten....
Ich hab jetzt auf einem Kreis mit Radius cEps um Punkt A verglichen.
RemoveDoublesII behält die Daten in der Ausgangsliste, also muss kein extra Feld angelegt werden.

Delphi-Quellcode:

procedure TFloatPoints.RemoveDoublesII;
var
  I, j: integer;
  ll, ul: integer;// lower, upper limit
  tmpf : tFloatPoint;
begin
  SortByX;

  ll := Low(FItems);
  ul := ll;
  for i := ll + 1 to FCOunt-1 do
  begin
    tmpf := FItems[i];
    while (ll < ul) and (tmpf.X >= FItems[ll].X + cEps) do
      Inc(ll);
    IF ll>ul then
    begin
      Inc(ul);
      FItems[ul] := tmpF;
    end
    else
    Begin
      j := ll;
      while j <= ul do
      begin
        if SameFloatPoint(tmpF, FItems[j]) then
          Break;
        Inc(j);
      end;
      if j > ul then
      begin
        Inc(ul);
        FItems[ul] := tmpF;
      end
    end;
  end;
  FCount := ul+1;
end;

Einen Test mit N= 100000 empfehle ich nicht, denn der anschliessende Check auf Doppelte dauert ewig...
Gruß Horst

[Dejan Vu]

Zitat von Bjoerk:

Bud, ich versteh dich nicht falsch. Mit eindimensionaler Sortierung kann man das hier (wenn überhaupt) nur bei mit stabilen Sortierverfahren so machen.

Hmnjamnjgfrftslmf. Jain.
Vereinfachen wir das auf eine Dimension. Die zweite braucht man nicht für die Betrachtung
Sei : P1=irgendwas, P2=P1+eps, P3=P2+eps
Dann gilt: P1=P2, P2=P3 und P1<P3
Sortiermöglichkeiten (egal ob stabil oder instabil):
P1,P2,P3 => Es wird nur P2 wird eliminiert, P3 aber nicht
P2,P1,P3 => P1 und P2 wird eliminiert
andere Möglichkeiten gibt es nicht
Ist das dein Problem? Das wirst du immer haben... Also mit den hier beschriebenen Verfahren.

[Bjoerk]

Zitat von Horst_:

Hallo,
ich habe endlich den casus cnactus gefunden.
Deine SortCompareX darf nur mit eps= 0 arbeiten.Ich habe wie blöd gesucht, warum größere x-Werte vor kleineren auftauchten....
Ich hab jetzt auf einem Kreis mit Radius cEps um Punkt A verglichen.
RemoveDoublesII behält die Daten in der Ausgangsliste, also muss kein extra Feld angelegt werden.

[.. Code ..]

Danke für den Code. Der gepostete Algo macht es aber leider nicht.

.. and (tmpf.X >= FItems[ll].X + cEps) do

weiß nicht recht..

Und das Eps von Null ist ja auch nur eins von 1E-15 oder so.

Anyway.

Bin eigentlich mit meinem Code #61 zufrieden. 100.000 Punkte 1..2 sec.

Edit: Man kann sich die zuzsätzlichen Listen auch sparen, wenn man direkt QuickSort(Von, Bis) durchführt. So fand ich's aber übersichtlicher.

LG
Thomas

[Horst_]

Hallo,

der gepostete Schnipsel soll nur das Vorgehen zeigen.
cEps ist global definiert in uFloatPoint.pas

In den angehängten Dateien ist es dann funktionstüchtig. ( Man kann sich das auch tatsächlich mal anschauen )
Es ging doch darum, das Deine Sortierung nicht wirklich aufsteigend sortiert, weil dort
Result := CompareValue(A.X, B.X, cEps); immer eine Umgebung betrachtet wird.
Ich hatte auch mal sowas im Testprogramm:

Delphi-Quellcode:

  for I := 1 to N do
    FLoatPoints.AddXY(i*cEps/20,i);
  //Zufaellige Punkte in y minimal verschieben -> doppelte
  for I := FLoatPoints.Count-1 downto 0 do
    with FloatPoints[Random(N)] do
      FLoatPoints.AddXY(X, Y-0.5*eps);

Also werden in sehr kleinem x-Abstand Punkte erzeugt, die sich y-mäßig sehr stark unterscheiden.Man muss dabei die letzten 20 Punkte in x-Richtung betrachten.Deshalb funktioniert dann Dejan Vu Version nicht mehr.

Gruß Horst
P.S:
Wie kann man jetzt feststellen, das man nicht zuviele Punkte rausgeschmissen hat?
P.S.S:
Kann man den Titel ändern.
Irgendwas mit doppelten XY-Koordinaten löschen wäre angebrachter.

[Dejan Vu]

Zitat von Horst_:

...Also werden in sehr kleinem x-Abstand Punkte erzeugt, die sich y-mäßig sehr stark unterscheiden.Man muss dabei die letzten 20 Punkte in x-Richtung betrachten.Deshalb funktioniert dann Dejan Vu Version nicht mehr...

Das probiere ich... So. Probiert. Klappt immer noch.

[Horst_]

Hallo,

das ist ja gut.
Man braucht ein paar wiederholbare Testfälle.Dazu sollte man random eigentlich weglassen.Damit man sieht, dass aus 1000 + 1000 verschobenene eben auch am Ende wieder 1000 werden.
Sonst wird ein Punkt öfter verschoben, und es belieben dann eben 1100 über.

Gruß Horst

[Dejan Vu]

Vollkommen richtig. Aber 1000 Punkte sind auch wieder 'ins Blaue geraten'. Drei oder vier sollten reichen. Hast Du denn eine Idee im Kopf, bei welchen Fällen es schiefgehen kann?

Ich bin mir sehr sicher, das die Eliminierung von trivialen Dopplungen (also P1 und P1' sehr nahe beieinander, aber sonst nichts in der Nähe) problemlos möglich ist.

Ich warte immer noch auf den Beleg (oder ein Beispiel), wo das eine Verfahren funktioniert, aber das andere nicht.

Oder: wir lassen den Murks und überlegen, was man eigentlich erreichen will: Was soll z.B. herauskommen, wenn ich eine ganze Punkteschar habe, die sehr eng beieinander liegt und bei der es einen Punkt Px gibt, der quasi in der Mitte dieses 'Clusters' liegt. Dann könnte ich alle Punkte dieses Clusters (bis auf den in der Mitte) eliminieren.
Also: Welches Ergebnis wird erwartet, wenn ich folgende Punkteschar erzeuge:

Delphi-Quellcode:

for i:=1 to 100000 do
  Points.AddXY (Eps*RandomRange(-1,1), Eps*RandomRange(-1,1));