Robert Sedgewick: Algorithmen

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


25. Bestimmung der konvexen Hülle



Das Durchsuchen nach Graham

Das nächste Verfahren, das wir betrachten wollen und das 1972 von R. L. Graham entwickelt wurde, ist interessant, weil der größte Teil der erforderlichen Berechnungen das Sortieren betrifft: Der Algorithmus enthält ein Sortierverfahren, dem eine relativ einfache (wenn auch nicht unmittelbar offensichtliche) Berechnung folgt. Der Algorithmus beginnt mit der Konstruktion eines einfachen geschlossenen Polygons aus den Punkten unter Anwendung der Methode aus dem vorangegangenen Kapitel: Sortieren der Punkte, wobei als Schlüssel die Werte der Funktion theta verwendet werden, die dem Winkel entsprechen, den die Gerade, die jeden Punkt mit einem »Anker«-Punkt p[1] (dem Punkt mit der kleinsten y-Koordinate) verbindet, mit der Horizontalen einschließt, so daß die Verbindung von p[1], p[2], ... , p[N], p[1] ein geschlossenes Polygon ergibt. Für unsere Beispiel-Punktmenge erhalten wir das einfache geschlossene Polygon aus dem vorangegangenen Kapitel. Beachten Sie, daß p[N], p[1] und p[2] aufeinanderfolgende Punkte der Hülle sind; indem wir sortieren, durchlaufen wir die erste Iteration der Prozedur des »Einwickelns« (in beiden Richtungen).

Die Bestimmung der konvexen Hülle wird vollendet, indem die Punkte der Reihe nach durchlaufen werden und dabei versucht wird, jeden Punkt in die Hülle aufzunehmen, wobei zuvor aufgenommene Punkte, die der Hülle nicht angehören können, entfernt werden. Für unser Beispiel betrachten wir die Punkte in der Reihenfolge B M J L N P K F I E C O A H G D; die ersten Schritte zeigt Abbildung 25.4. Zu Beginn wissen wir aufgrund der Anordnung, daß B und M der Hülle angehören. Wenn J vorgefunden wird, nimmt es der Algorithmus in die Versuchs-Hülle für die ersten drei Punkte auf. Danach, wenn L angetroffen wird, stellt der Algorithmus fest, daß J nicht der Hülle angehören kann (da der Punkt zum Beispiel innerhalb des Dreiecks BML liegt).

Abbildung 25.4
Abbildung 25.4 Beginn des Durchsuchens nach Graham.

Im allgemeinen ist die Überprüfung, welche Punkte entfernt werden müssen, nicht schwierig. Jedesmal, wenn ein Punkt hinzugefügt worden ist, nehmen wir an, daß wir genügend viele Punkte entfernt haben, so daß das, was wir bisher gezeichnet haben, ein Teil der konvexen Hülle auf der Basis der bisher betrachteten Punkte ist. Wenn wir die Punkte der Reihe nach durchlaufen, erwarten wir bei jeder Ecke der Hülle ein Abbiegen nach links. Wenn ein neuer Punkt uns zwingt, nach rechts abzubiegen, so muß der gerade hinzugefügte Punkt entfernt werden, da bereits ein konvexes Polygon existiert, welches ihn enthält. Der Test für das Entfernen eines Punktes verwendet die Prozedur ccw aus dem vorangegangenen Kapitel. Angenommen, wir haben ermittelt, daß p[1..M] der partiellen Hülle angehören, die auf der Basis der Betrachtung von p[1..i-1] bestimmt wurde. Wenn wir dann einen neuen Punkt p[i] betrachten, entfernen wir p[M] aus der Hülle, falls ccw(p[M], p[M - 1], p[i]) nichtnegativ ist. Andernfalls kann der Punkt p[M] noch immer der Hülle angehören, so daß wir ihn nicht entfernen.

Abbildung 25.5 zeigt die Vollendung dieses Prozesses für unsere Beispiel-Punktmenge. Die Situation, die jedesmal vorliegt, wenn ein neuer Punkt vorgefunden wird, ist hier schematisch dargestellt: Jeder neue Punkt wird zu der bis dahin konstruierten partiellen Hülle hinzugefügt und wird dann als »Zeuge« für das Entfernen von (null oder mehr) zuvor betrachteten Punkten benutzt. Nachdem L, N und P zur Hülle hinzugefügt worden sind, wird P entfernt, wenn K betrachtet wird (da NPK einem Abbiegen nach rechts entspricht); dann werden F und I hinzugefügt, was zur Betrachtung von E führt. An dieser Stelle muß I entfernt werden, weil FIE ein Abbiegen nach rechts bedeutet; danach müssen F und K entfernt werden, weil KFE und NKE einem Abbiegen nach rechts entsprechen. Demzufolge kann während der Prozedur des »Zurückschauens« mehr als ein Punkt entfernt werden, möglicherweise mehrere. Indem in dieser Weise fortgefahren wird, erreicht der Algorithmus schließlich wieder B.

Abbildung 25.5
Abbildung 25.5 Vollendung des Durchsuchens nach Graham.

Das Sortieren am Anfang garantiert, daß ein Punkt nach dem anderen als möglicher Punkt der Hülle betrachtet wird, da alle zuvor betrachteten Punkte einen kleineren Wert von theta aufweisen. Jede Linie, die die »Beseitigungen« übersteht, hat die Eigenschaft, daß sich alle bis dahin betrachteten Punkte auf der gleichen Seite von ihr befinden, so daß wir, wenn wir wieder zum Punkt p[N] gelangen, der aufgrund des Sortierverfahrens gleichfalls der Hülle angehören muß, die vollständige konvexe Hülle aller Punkte erhalten haben.

Wie beim Verfahren des »Einwickelns« können Punkte, die sich auf dem Rand der Hülle befinden, aufgenommen werden oder auch nicht, obwohl es zwei verschiedene Situationen gibt, die bei kollinearen Punkten eintreten können. Erstens kann, wenn zwei mit p[1] kollineare Punkte vorhanden sind, das theta benutzende Sortierverfahren sie in der richtigen Reihenfolge längs ihrer gemeinsamen Linie einordnen oder auch nicht. Punkte, die sich in dieser Situation nicht in der richtigen Reihenfolge befinden, werden während des Durchsuchens entfernt. Zweitens können kollineare Punkte längs der Versuchs-Hülle auftreten (und nicht entfernt werden).

Nachdem das zugrundeliegende Verfahren klar ist, ist die Implementation sehr einfach, obwohl ein paar Details beachtet werden müssen. Zuerst wird der Punkt, der von allen Punkten mit minimalem y-Wert den maximalen x-Wert hat, mit p[1] vertauscht. Danach wird für das Umordnen der Punkte shellsort verwendet (jedes auf Vergleichen beruhende Standardprogramm zum Sortieren wäre geeignet), geeignet modifiziert, um zwei Punkte unter Benutzung ihrer theta-Werte mit p[1] zu vergleichen. Nach dem Sortieren wird p[N] in p[0] kopiert, um als Marke zu dienen, falls p[3] nicht der Hülle angehört. Schließlich wird das oben beschriebene Durchsuchen ausgeführt. Das folgende Programm ermittelt die konvexe Hülle der Punktmenge p[1..N]:

    function grahamscan: integer;
      var i,j,min,M: integer;
          l: line; t: point;
      begin
      min:=1;
      for i:=2 to N do
        if p[i].y<p[min].y then min:=i;
      for i:=1 to N do
        if (p[i].y=p[min].y) and (p[i].x>p[min].x) then min:=i;
      t:=p[1]; p[1]:=p[min]; p[min]:=t;
      shellsort;
      p[0]:=p[N];
      M:=3;
      for i:=4 to N do
        begin
        while ccw(p[M],p[M-1],p[i])>=0 do M:=M-1;
        M:=M+1;
        t:=p[M]; p[M]:=p[i]; p[i]:=t;
        end;
      grahamscan:=M;
      end;

Die Schleife speichert eine partielle Hülle in p[1..M], wie oben beschrieben wurde. Für jeden neuen betrachteten Wert von i wird, wenn notwendig, M dekrementiert, um Punkte aus der partiellen Hülle zu entfernen, und dann wird p[i] mit p[M + 1] ausgetauscht, um den entsprechenden Punkt (versuchsweise) zur partiellen Hülle hinzuzufügen. Abbildung 25.6 zeigt für unser Beispiel den Inhalt des Feldes p jedesmal, wenn ein neuer Punkt betrachtet wird.

Abbildung 25.6
Abbildung 25.6 Datenumordnung beim Durchsuchen nach Graham.

Der Leser kann nachprüfen, warum es für die Berechnung von min notwendig ist, unter allen Punkten mit der kleinsten y-Koordinate den Punkt mit der größten x-Koordinate zu finden, also die in Kapitel 24 beschriebene kanonische Form. Wie bereits erwähnt wurde, ist ein weiterer schwieriger Punkt die Untersuchung der Auswirkung der Tatsache, daß kollineare Punkte zu gleichen theta-Werten führen und möglicherweise nicht, wie es wünschenswert wäre, in der Reihenfolge sortiert werden, in der sie auf der Linie angeordnet sind.

Ein Grund dafür, daß die Untersuchung dieses Verfahrens interessant ist, ist die Tatsache, daß es sich um eine einfache Form von backtracking (Zurückverfolgen) handelt. Dies sind Algorithmen der Art »versuche etwas, und wenn es nicht klappt, versuche etwas anderes«, auf die wir in Kapitel 44 zurückkommen werden.


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