Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


26. Bereichssuche



Gitterverfahren

Eine einfache, doch effiziente Methode für die Beibehaltung von Nachbarschaftsbeziehungen zwischen Punkten in der Ebene besteht darin, ein künstliches Gitter zu konstruieren, das die zu durchsuchende Fläche in kleine Quadrate zerlegt, und kurze Listen der in jedem Quadrat befindlichen Punkte anzulegen. (Diese Methode wird zum Beispiel in der Archäologie verwendet.) Wenn dann Punkte gesucht werden, die innerhalb eines gegebenen Rechtecks liegen, brauchen nur diejenigen Listen durchsucht zu werden, die Quadraten entsprechen, die sich mit dem Rechteck überschneiden. In unserem Beispiel werden nur E, C, F und K geprüft, wie Abbildung 26.3 zeigt.

Abbildung 26.3
Abbildung 26.3 Gitterverfahren für die Bereichssuche.

Die wichtigste Entscheidung, die zu treffen ist, ist die Festlegung der Größe des Gitters: Falls es zu grob ist, enthält jedes Quadrat des Gitters zu viele Punkte, und falls es zu fein ist, müssen zu viele Gitterquadrate abgesucht werden (von denen die meisten leer sind). Ein Kompromiß zwischen diesen beiden Extremfällen läßt sich finden, indem die Größe des Gitters so gewählt wird, daß die Anzahl der Gitterquadrate ein konstanter Bruchteil der Gesamtzahl der Punkte ist. Dann ist zu erwarten, daß die Anzahl der Punkte in jedem Quadrat ungefähr gleich einer gewissen kleinen Konstante ist. Für unser kleines Beispiel einer Punktmenge bedeutet die Verwendung eines 4x4-Gitters für eine aus 16 Punkten bestehende Menge, daß jedes Gitterquadrat im Mittel einen Punkt enthält.

Nachfolgend wird eine einfache Implementation eines Programms zur Erzeugung der Gitterstruktur angegeben, das die Punkte in einem Feld p[0..N] von Punkten des zu Beginn von Kapitel 24 beschriebenen Typs enthält. Die Variable size wird verwendet, um die Größe der Gitterquadrate zu steuern und demzufolge das Auflösungsvermögen des Gitters zu bestimmen. Der Einfachheit halber wird angenommen, daß die Koordinaten aller Punkte zwischen 0 und einem gewissen maximalen Wert max liegen. Dann wird size für die Breite eines Gitterquadrats genommen, und es gibt max/size mal max/size Gitterquadrate. Um zu ermitteln, welchem Gitterquadrat ein Punkt angehört, dividieren wir seine Koordinaten durch size:

    const maxG=20;
    type link=^node;
         node=record p: point; next: link end;
    var grid: array[0..maxG,0..maxG] of link;
        size: integer;
        z: link;
    procedure preprocess;
      procedure insert(p: point);
        var t: link;
        begin
        new(t); t^.p:=p;
        t^.next:=grid[p.x div size,p.y div size];
        grid[p.x div size,p.y div size]:=t;
        end;
      begin
      new(z);
      size:=1; while size*size<max*max/N do size:=size+size;
      for i:=0 to maxG do
        for j:=0 to maxG do grid[i,j]:=z;
      for i:=0 to N do insert(p[i]);
      end;

Dieses Programm verwendet unsere standardmäßigen Darstellungen mittels verketteter Listen mit einem Pseudo-Endknoten z. Die Variable max wird wiederum als global vorausgesetzt; vielleicht wird sie während der Eingabe der Punkte gleich dem maximalen auftretenden Wert einer Koordinaten gesetzt.

Wie oben erwähnt wurde, hängt die Festlegung des Wertes der Variablen size von der Anzahl der Punkte, vom Umfang des verfügbaren Speicherplatzes und von der Streubreite der Werte der Koordinaten ab. Grob gesagt, um M Punkte pro Gitterquadrat zu erhalten, sollte für size die ganze Zahl gewählt werden, die max dividiert durch sqrtN/M am nächsten kommt. Dies führt zu ungefähr N/M Gitterquadraten. Diese Abschätzungen sind für kleine Parameterwerte ungenau, doch sie sind für die meisten Situationen nützlich; für spezielle Anwendungen können leicht ähnliche Abschätzungen angegeben werden. Der Wert braucht nicht exakt berechnet zu werden; in der obigen Implementation wird für size eine Zweierpotenz verwendet, was die Multiplikation mit size und die Division durch size in den meisten Programmierumgebungen wesentlich effizienter machen dürfte.

In der obigen Implementation wird M = 1 verwendet, was eine häufig getroffene Wahl ist. Wenn Platz sehr kostbar ist, kann ein großer Wert geeignet sein, doch ein kleinerer Wert ist, außer in sehr speziellen Situationen, sicherlich nicht sinnvoll.

Nunmehr wird die Hauptarbeit bei der Bereichssuche einfach ausgeführt, indem auf das Feld grid Bezug genommen wird:

    procedure gridrange(rect: rectangle);
      var t: link;
          i,j: integer;
      begin
      for i:=(rect.x1 div size) to (rect.x2 div size) do
        for j:=(rect.y1 div size) to (rect.y2 div size) do
          begin
          t:=grid[i,j];
          while t<>z do
            begin
            if insiderect(t^.p, rect) 
              then {point t^.p is within the range}
              t:=t^.next
            end
          end
      end;

Die Laufzeit dieses Programms ist proportional zur Anzahl der betroffenen Gitterquadrate. Da wir dafür gesorgt hatten, daß jedes Gitterquadrat im Durchschnitt eine konstante Anzahl von Punkten enthält, ist die Anzahl der betroffenen Gitterquadrate im Durchschnitt gleichfalls zur Anzahl der betrachteten Punkte proportional.

Eigenschaft 26.2 Das Gitterverfahren für die Bereichssuche ist im durchschnittlichen Fall linear bezüglich der Anzahl der Punkte im Bereich und im ungünstigsten Fall linear bezüglich der Gesamtzahl der Punkte.

Wenn R die Anzahl der Punkte in dem den Suchbereich darstellenden Rechteck ist, so ist die Anzahl der untersuchten Gitterquadrate proportional zu R. Die Anzahl der untersuchten Gitterquadrate, die sich nicht vollständig innerhalb des Suchrechtecks befinden, ist sicherlich kleiner als eine kleine Konstante mal R, so daß die Gesamtlaufzeit (im Durchschnitt) linear in R ist. Für große R wird die Anzahl der untersuchten Punkte, die sich nicht im Suchrechteck befinden, sehr klein: Alle derartige Punkte liegen in einem Gitterquadrat, das sich mit dem Rand des Rechtecks überschneidet, und die Anzahl solcher Quadrate ist für große R proportional zu sqrtR. Beachten Sie, daß diese Überlegung nicht zutrifft, wenn die Gitterquadrate zu klein sind (zu viele leere Quadrate innerhalb des Suchrechtecks), oder wenn sie zu groß sind (zu viele Punkte in Gitterquadraten an Rand des Rechtecks), oder wenn das Rechteck schmaler ist als die Gitterquadrate (es könnte viele Gitterquadrate schneiden, jedoch nur wenige Punkte enthalten). w.z.b.w.

Das Gitterverfahren ist gut geeignet, falls die Punkte über den angenommenen Bereich gut verteilt sind, doch schlecht, falls sie gehäuft beieinander liegen. (Zum Beispiel könnten alle Punkte in einem Feld des Gitters enthalten sein, was bedeuten würde, daß der gesamte Aufwand mit dem Gitter nichts genützt hätte.) Das Verfahren, das wir als nächstes betrachten, macht diesen ungünstigsten Fall sehr unwahrscheinlich, indem der Platz in einer ungleichmäßigen Weise unterteilt wird, die an die vorliegende Punktmenge angepaßt ist.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]