Wie kann man viele Punkte schnell vergleichen?

[Uwe Raabe]

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;