Robert Sedgewick: Algorithmen

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


27. Geometrischer Schnitt



Implementation

Der erste Schritt bei der Implementation besteht im Sortieren der Endpunkte der Linien nach ihren y-Koordinaten. Da jedoch binäre Bäume benutzt werden sollen, um die Lage vertikaler Linien bezüglich der horizontalen Durchmusterungslinie zu registrieren, können sie ebensogut für das anfängliche Sortieren nach y verwendet werden! Genau gesagt, wollen wir zwei »indirekte« binäre Bäume für die Linienmenge verwenden, einen mit dem Kopfknoten hy und einen mit dem Kopfknoten hx. Der y-Baum soll alle Endpunkte von Linien enthalten, die der Reihe nach verarbeitet werden sollen; der x-Baum soll die Linien enthalten, die die aktuelle horizontale Durchmusterungslinie schneiden. Wir beginnen damit, daß wir wie in treeinitialize in Kapitel 14 sowohl hx als auch hy mit Schlüsseln 0 und Zeigern auf einen äußeren Pseudo-Knoten z initialisieren. Danach wird der hy-Baum konstruiert, indem sowohl die beiden y-Koordinaten von vertikalen Linien als auch die y-Koordinate von horizontalen Linien in den binären Suchbaum mit dem Kopfknoten hy eingefügt werden:

    procedure buildytree;
      var x1,y1,x2,y2: integer;
      begin
      hy:=bstinitialize; N:=0;
      repeat
        N:=N+1;
        read(x1,y1,x2,y2); if eoln then readln;
        lines[N].p1.x:=x1; lines[N].p1.y:=y1;
        lines[N].p2.x:=x2; lines[N].p2.y:=y2;
        bstinsert(N,y1,hy);
        if y2<>y1 then bstinsert(N,y2,hy);
      until eof;
      end;

Dieses Programm liest Gruppen von vier Zahlen ein, die Linien beschreiben, und speichert sie im Feld lines und im binären Suchbaum für die y-Koordinate. Das Standardprogramm bstinsert aus Kapitel 14 wird verwendet, mit den y-Koordinaten als Schlüssel und mit auf das Feld von Linien weisenden Indizes als Feld info. Für unser Beispiel einer Linienmenge wird der in Abbildung 27.5 dargestellte Baum erzeugt.

Abbildung 27.5
Abbildung 27.5 Sortieren für die Durchmusterung unter Verwendung des y-Baumes.

Nunmehr wird das Sortieren nach y mit Hilfe eines rekursiven Standardprogramms für die Inorder-Traversierung eines Baumes vorgenommen (siehe Kapitel 4 und 14). Wir besuchen die Knoten in der wachsenden y-Koordinaten entsprechenden Reihenfolge, indem wir alle Knoten im linken Teilbaum des hy-Baumes, dann die Wurzel und danach alle Knoten im rechten Teilbaum des hy-Baumes besuchen. Gleichzeitig verwalten wir einen separaten Baum (mit der Wurzel hx) in der oben beschriebenen Weise, um das Durchlaufen einer horizontalen Durchmusterungslinie zu simulieren;

    procedure scan(next: link);
      var t,x1,x2,y1,y2: integer;
          int: interval;
      begin
      if next<>z then
        begin
        scan(next^.l);
        x1:=lines[next^.info].p1.x; y1:=lines[next^.info].p1.y;
        x2:=lines[next^.info].p2.x; y2:=lines[next^.info].p2.y;
        if x2<x1 then begin t:=x2; x2:=x1; x1:=t end;
        if y2<y1 then begin t:=y2; y2:=x1; y1:=t end;
        if next^.key=y1 then bstinsert(next^.info,x1,hx);
        if next^.key=y2 then
          begin
          bstdelete(next^.info,x1,hx);
          int.x1:=x1; int.x2:=x2;
          bstrange(hx^.r,int);
          end;
        scan(next^.r)
        end
      end;

Anhand der obigen Beschreibung ist es sehr einfach, das Programm an der Stelle zusammenzusetzen, wo jeder Knoten »besucht« wird. Zuerst werden die Koordinaten des Endpunkts der entsprechenden Linie aus dem Feld lines geholt, indiziert durch das Feld info des Knotens. Danach wird das Feld key im Knoten mit diesen Koordinaten verglichen, um festzustellen, ob dieser Knoten dem oberen oder dem unteren Endpunkt der Linie entspricht; falls es der untere Endpunkt ist, wird er in den hx-Baum eingefügt, und falls es der obere Endpunkt ist, wird er aus dem hx-Baum gelöscht, und es wird eine Bereichssuche durchgeführt. Die Implementation unterscheidet sich leicht von dieser Beschreibung, und zwar dadurch, daß horizontale Linien in Wirklichkeit in den hx-Baum eingefügt und dann sofort gelöscht werden, und daß für vertikale Linien eine Bereichssuche für ein aus einem Punkt bestehendes Intervall durchgeführt wird. Dadurch wird erreicht, daß das Programm den Fall sich überlappender vertikaler Linien richtig behandelt, welche als »sich schneidend« betrachtet werden.

Diese Vorgehensweise mit einer gemischten Anwendung rekursiver Prozeduren, die mit den Koordinaten x und y operieren, ist bei geometrischen Algorithmen sehr wichtig. Ein weiteres Beispiel dafür ist der 2D-Baum-Algorithmus aus dem vorangegangenen Kapitel, und wir werden im folgenden Kapitel noch ein weiteres Beispiel kennenlernen.

Eigenschaft 27.1 Alle Schnitte von N horizontalen und vertikalen Linien können in einer Zeit gefunden werden, die zu N log N + I proportional ist, wobei I die Anzahl der Schnitte ist.

Für die im Baum durchzuführenden Operationen wird eine Zeit benötigt, die im durchschnittlichen Fall zu log N proportional ist (falls ausgeglichene Bäume verwendet würden, könnte für den ungünstigsten Fall log N garantiert werden), doch die für bstrange erforderliche Zeit hängt auch von der Gesamtzahl der Schnitte ab. Im allgemeinen kann die Zahl der Schnitte sehr groß werden. Wenn zum Beispiel N/2 horizontale Linien und N/2 vertikale Linien vorliegen, die in einem Gittermuster angeordnet sind, ist die Anzahl der Schnitte proportional zu N2. w.z.b.w.

Wie bei der Bereichssuche sollte, wenn im voraus bekannt ist, daß die Anzahl der Schnitte sehr groß ist, eine grober Ansatz benutzt werden. Typisch ist jedoch, daß bei Anwendungen eine Situation vom Typ »Stecknadel in einem Heuhaufen« vorliegt, wo eine große Menge von Linien auf wenige mögliche Schnitte hin überprüft werden muß.


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