AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Wie kann man viele Punkte schnell vergleichen?

Ein Thema von Matze · begonnen am 15. Jun 2010 · letzter Beitrag vom 18. Jun 2010
Antwort Antwort
Seite 1 von 2  1 2   
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#1

Wie kann man viele Punkte schnell vergleichen?

  Alt 15. Jun 2010, 20:25
Hallo zusammen,

ich habe Punkte, die ich in einem Diagramm anzeigen lasse (verbunden ist es natürlich eine Kurve). D.h. jeder Punkt besitzt einen x- und eine y-Wert.

Nun habe ich mehrere Fenster festgelegt, mit denen ich die Kurvenabschnitte auswerte.

Ein Beispiel mit 2 Fenstern ist folgendes:

x = 12,5 bis 17,8
x = 16,9 bis 20

Ich kann beliebig viele Fenster (Rechtecke) vorgeben und ich möchte die Punkte darin schnell ausfindig machen, damit ich diese mit anderen Dingen vergleichen kann.

Würden sich die Fenster nicht überschneiden, könnte ich die Kurve in einer Schleife ein einziges Mal durchlaufen (von links nach rechts).
Da sich die Fenster überschneiden untersuche ich aktuell pro Fenster die Kurve vom niedrigsten x-Wert bis zum Ende des Fensters (dann kann ich den Suchdurchlauf natürlich abbrechen). D.h. es sind viele Vergleiche nötig, um überhaupt herauszufinden, ab wann die Kurve in das Fenster eintritt.

Ich kann nicht direkt auf die Punkte zugreifen, da ich erst herausfinden muss, welcher Punkt in welchem Fenster liegt.

Ein Zahlenbeispiel zur Verdeutlichung:

Punkte:
Code:
0    0,5    1    1,5    2    2,5    3    3,5    4    4,5    5
Die Fenster sind wie folgt definiert:
Code:
Fenster 1:
x = 0,7 bis 1,8

Fenster 2:
x = 1,4 bis 3,7
Mein Ziel ist es, den Punkt direkt vor dem Fenster und den ersten im Fenster zu ermitteln und beim Austritt ebenfalls. Hier zeige ich nur den Suchvorgang allgemein.

2 Bereiche -> 2 Schleifen:

Schleife 1 fürs 1. Fenster:
Diese läuft von x = 0 bis x = 2 und gibt mir als Werte innerhalb des Fensters 1 und 1,5 zurück.

Schleife 2 fürs 2. Fenster:
Diese läuft von x = 0 bis x = 4 und gibt mir als Werte innerhalb des Fensters 1,5 bis 3,5 zurück.

Bei tausenden Werten und vielen Fenstern kann das lange dauern.

Geht es irgendwie schneller?

Die Punkte liegen übrigens in 2 Arrays vor: in einem sind die x- und im anderen die y-Werte definiert.

Grüße, Matze
  Mit Zitat antworten Zitat
Benutzerbild von H4ndy
H4ndy

Registriert seit: 28. Jun 2003
Ort: Chemnitz
515 Beiträge
 
Delphi XE3 Professional
 
#2

AW: Wie kann man viele Punkte schnell vergleichen?

  Alt 15. Jun 2010, 20:31
Dreh es doch um, und lauf die Punkte nur einmal durch und vergleich pro Punkt, ob dieser in einem der Fenster liegt, koennte schneller sein, solange weniger Fenster als Punkt vorhanden sind. Vielleicht kann man auch was mit Sortierung noch rausholen.
Manuel
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
43.886 Beiträge
 
Delphi 12 Athens
 
#3

AW: Wie kann man viele Punkte schnell vergleichen?

  Alt 15. Jun 2010, 20:39
Wenn die Punkte-Liste sortiert ist, dann kannst du doch über eine binäre Suche ganz schnell den Anfang für deinen Bereich suchen.

Also den ersten Wert, welcher größer-gleich deinem Anfan für das Rechteck ist.

Diese Suche wäre dann mit O(log n) schon recht schnell, so daß bei 1.000.000 Punkten schon nach maximal 20 Vergleichen der Anfang gefunden wäre.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list : BugReports/FeatureRequests

Geändert von himitsu (15. Jun 2010 um 20:43 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#4

AW: Wie kann man viele Punkte schnell vergleichen?

  Alt 15. Jun 2010, 20:42
Puh, das wird komplex. Aber stimmt, das wäre evtl. schneller. Danke für den Hinweis.

Wie angedeutet, brauche ich jeweils den Punkt direkt vor dem Fenster, dann den ersten und letzten im Fenster und den ersten Punkt, der wieder aus dem Fenster draußen ist.
D.h. ich müsste immer den aktuellen und den nächsten Punkt mit den Fensterkanten vergleichen. Und es kommen zu den x-Wertenauch noch die y-Werte hinzu und die Vergleiche mit den Fensterober- und -unterkanten. Ohje ....

@Himi: Ich weiß nicht, ob das funktioniert, da ich keinen bestimmten Wert suche. D.h. die Suche würde bei mir fast immer "kein Treffer" liefern.
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
43.886 Beiträge
 
Delphi 12 Athens
 
#5

AW: Wie kann man viele Punkte schnell vergleichen?

  Alt 15. Jun 2010, 20:46
Klar funktioniert das.
Du suchst also einfach nur den wert, welcher Größer-Gleich deinem Startpunkt ist und welcher am nähesten an diesem Punkt liegt.

Schau dir mal die Find-Methode der TStringList an.
Über diese wird zwar ein bestimmter Wert gesucht, aber wenn nix gefunden wird, dann gibt diese die Position zurück welcher der Wert eingefügt werden könnte.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list : BugReports/FeatureRequests
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#6

AW: Wie kann man viele Punkte schnell vergleichen?

  Alt 15. Jun 2010, 20:49
Ich guck mal, ob ich den Algorithmus verstehe und ihn umsetzen kann.
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#7

AW: Wie kann man viele Punkte schnell vergleichen?

  Alt 15. Jun 2010, 21:51
Wie viele Punkte sind es denn ungefähr? Wie wäre es mit einem Quadtree? (Kann sein, dass himitsu mit Binärer Suche das gleiche meinte).

PS: Unten ist auch eine Seite mit Beispielen verlinkt.

Geändert von Namenloser (15. Jun 2010 um 21:54 Uhr) Grund: Quadtree, nicht Octree
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.682 Beiträge
 
Delphi 2007 Enterprise
 
#8

AW: Wie kann man viele Punkte schnell vergleichen?

  Alt 15. Jun 2010, 22:46
Im 3D-Bereich wird zum "culling" (Ablehnen von Polygonen/Vertices) gerne das Separating Axis Theorem ausgenutzt. Gerade mit achsenparallelen Rechtecken kann man da einiges optimieren, und das kann extrem flott gezüchtet werden. (Wird immerhin zum Frustum-Culling teils Bild für Bild in Spielen gemacht, und sogar in 3D mit schiefen Ebenen.) Es gibt die Wikipediaseite auch auf Deutsch, ich fand die Englische jetzt nur weit aus anschaulicher.
Das dürfte mehr oder minder State of the Art sein, es sei denn es gibt für 2D eine noch flottere Klamotte die mir dann unbekannt wäre
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe

Registriert seit: 20. Jan 2006
Ort: Lübbecke
11.373 Beiträge
 
Delphi 12 Athens
 
#9

AW: Wie kann man viele Punkte schnell vergleichen?

  Alt 16. Jun 2010, 00:55
Wenn ich das recht verstehe, betrachtest du lediglich die X-Werte der Punkte mit den jeweiligen Fenstergrenzen. Die Y-Werte interessieren dabei noch gar nicht.

Die Punkte scheinen in X aufsteigend sortiert zu sein, sonst funktioniert dein Algorithmus nämlich nicht.

Wenn man nun die Fenstergrenzen ebenfalls sortiert und mit Index-Arrays arbeitet, kann man mit zwei Durchläufen die Punktbereiche in den Fenstern ermitteln.

Hier der passende Code:

Delphi-Quellcode:
{ Punkte gibt die X-Werte der Punkte an, FensterLo die Untergrenzen, FensterHi die Obergrenzen der Fenster.
  insideLo und insideHi geben die Indizes der Punkte an, die gerade noch in dem jeweiligen Fenster liegen }

procedure FindeFenster(const Punkte, FensterLo, FensterHi: array of Double; var insideLo, insideHi: TIntegerDynArray);
var
  CntPunkte: Integer;
  CntFenster: Integer;
  orderLo: TIntegerDynArray;
  orderHi: TIntegerDynArray;
  I: Integer;
  idx: Integer;
  rng: Integer;
begin
  CntPunkte := Length(Punkte);
  CntFenster := Length(FensterLo);

  Assert(CntPunkte > 0);
  Assert(CntFenster > 0);
  Assert(CntFenster = Length(FensterHi));

  SetLength(insideLo, CntFenster);
  SetLength(insideHi, CntFenster);

  { orderLo enthält eine Liste von Indizes auf FensterLo, so daß die Werte aufsteigend sortiert sind.
    orderHi enthält eine Liste von Indizes auf FensterHi, so daß die Werte aufsteigend sortiert sind.
    Läßt sich mit einem angepassten QuickSort leicht implementieren. }


  orderLo := GetSortOrder(FensterLo);
  orderHi := GetSortOrder(FensterHi);

  { erster Durchlauf: untere Grenzen ermitteln }
  idx := 0;
  rng := orderLo[idx];
  for I := 0 to Length(Punkte) - 1 do begin
    if Punkte[I] >= FensterLo[rng] then begin
      { untere Grenze des nächsten Fensters überschritten }
      insideLo[rng] := I;
      { die folgenden Fenster prüfen bis wir eins finden, in dem wir noch nicht sind }
      Inc(idx);
      while idx < CntFenster do begin
        rng := orderLo[idx];
        if Punkte[I] < FensterLo[rng] then
          Break;
        insideLo[rng] := I;
        Inc(idx);
      end;
      { schon alle Fenster überprüft? }
      if idx >= CntFenster then
        Break;
      rng := orderLo[idx]
    end;
  end;

  { zweiter Durchlauf: obere Grenzen ermitteln }
  idx := CntFenster - 1;
  rng := orderHi[idx];
  for I := CntPunkte - 1 downto 0 do begin
    if Punkte[I] <= FensterHi[rng] then begin
      { obere Grenze des nächsten Fensters unterschritten }
      insideHi[rng] := I;
      { die folgenden Fenster prüfen bis wir eins finden, in dem wir noch nicht sind }
      Dec(idx);
      while idx >= 0 do begin
        rng := orderHi[idx];
        if Punkte[I] > FensterHi[rng] then
          Break;
        insideHi[rng] := I;
        Dec(idx);
      end;
      { schon alle Fenster überprüft? }
      if idx < 0 then
        Break;
      rng := orderHi[idx];
    end;
  end;
end;
Die Funktion GetSortOrder ruft einen angepassten Quicksort auf:

Delphi-Quellcode:
procedure QuickSort(const Values: array of Double; var Index: array of Integer; L, R: Integer);
var
  I, J, T: Integer;
  P: Double;
begin
  repeat
    I := L;
    J := R;
    P := Values[Index[(L + R) shr 1]];
    repeat
      while (Values[Index[I]] < P) do
        Inc(I);
      while (Values[Index[J]] > P) do
        Dec(J);
      if I <= J then
      begin
        if I <> J then
        begin
          T := Index[I];
          Index[I] := Index[J];
          Index[J] := T;
        end;
        Inc(I);
        Dec(J);
      end;
    until I > J;
    if L < J then
      QuickSort(Values, Index, L, J);
    L := I;
  until I >= R;
end;

function GetSortOrder(const Values: array of Double): TIntegerDynArray;
var
  I: Integer;
begin
  SetLength(result, Length(Values));
  for I := 0 to Length(result) - 1 do
    result[I] := I;

  QuickSort(Values, result, 0, Length(result) - 1);
end;
Uwe Raabe
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.682 Beiträge
 
Delphi 2007 Enterprise
 
#10

AW: Wie kann man viele Punkte schnell vergleichen?

  Alt 16. Jun 2010, 01:18
Öhm, sortiert und nur für eine Achse ginge das doch noch VIEL einfacher! Die Fenstergrenzen müssen dafür auch nach gleicher Weise wie die Punkte sortiert sein, und du kommst mit nur einem Durchlauf aus.

Mal so ein Fetzen Pseudocode:
Delphi-Quellcode:
type
  TWindow = class;
  TEdge = class
  public
    Value: Float;
    IsLeftEdge: Boolean; // im Konstruktor zuweisen, wird noch wichtig :)
    Window: TWindow; // im Konstruktor zuweisen, quasi der Parent, also Rückbezug
  end;
  TWindow = class
  public
    Left, Right: TEdge;
    LeftPointLeft: Float;
    LeftPointRight: Float;
    RightPointLeft: Float;
    RightPointRight: Float;
  end;

var
  Windows: array of TWindow;
  Edges: array of TEdge; // referenzen auf alle Edges aus dem Windows-Array sortiert nach Value
  CurrentEdgeIndex: Integer;
begin
  for i := 0 to maxPoints do
  begin
    if Points[i].X > Edges[CurrentEdgeIndex].Value then
    begin
      if Edges[CurrentEdgeIndex].IsLeftEdge then
      begin
        Edges[CurrentEdgeIndex].Window.LeftPointLeft := Points[i-1].Value;
        Edges[CurrentEdgeIndex].Window.LeftPointRight := Points[i].Value;
      end
      else
      begin
        Edges[CurrentEdgeIndex].Window.RightPointLeft := Points[i-1].Value;
        Edges[CurrentEdgeIndex].Window.RightPointRight := Points[i].Value;
      end;
      inc(CurrentEdgeIndex);
    end;
  end;
end;
Und schwupps stehen im TWindows-Array alle Punkte, die links und rechts der X-Fenstergrenzen liegen, in O(n).

Man könnte natürlich auch die Punkte in die TEdge Instanzen werfen, und sich dieses IsLeftEdge damit sparen:
Delphi-Quellcode:
type
  TWindow = class;
  TEdge = class
  public
    Value: Float;
    LeftValue, RightValue: Float;
  end;
  TWindow = class
  public
    Left, Right: TEdge;
  end;

var
  Windows: array of TWindow;
  Edges: array of TEdge; // referenzen auf alle Edges aus dem Windows-Array sortiert nach Value
  CurrentEdgeIndex: Integer;
begin
  for i := 0 to maxPoints do
  begin
    if Points[i].X > Edges[CurrentEdgeIndex].Value then
    begin
      Edges[CurrentEdgeIndex].LeftValue := Points[i-1].Value;
      Edges[CurrentEdgeIndex].RightValue := Points[i].Value;
      inc(CurrentEdgeIndex);
    end;
  end;
end;
Das spart evtl. noch (sehr minimal) Zeit in der Schleife (ein Vergleich und ein paar Dereferenzierungen, uhu), und die Werte stehen ggf. an sinnvollerer Stelle, je nach dem wie du es nachher brauchst.
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)

Geändert von Medium (16. Jun 2010 um 01:23 Uhr)
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 19:26 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz