Robert Sedgewick: Algorithmen

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


25. Bestimmung der konvexen Hülle



Einwickeln

Der natürlichste Algorithmus zur Bestimmung der konvexen Hülle, der der Art und Weise entspricht, wie ein Mensch die konvexe Hülle einer Punktmenge zeichnen würde, ist ein systematisches Verfahren des »Einwickelns« der Punktmenge. Man beginne bei irgendeinem Punkt, der garantiert zur konvexen Hülle gehört (etwa bei dem Punkt mit der kleinsten y-Koordinate), nehme einen horizontalen, in die positive Richtung verlaufenden Strahl und »schwenke« ihn nach oben, bis er auf einen weiteren Punkt trifft; dieser Punkt muß zur Hülle gehören. Dann benutze man diesen Punkt als Drehpunkt und »schwenke« weiter, bis wieder ein Punkt getroffen wird, usw., bis das »Paket« vollständig »eingewickelt« ist (der Anfangspunkt ist wieder erreicht). Abbildung 25.2 zeigt, wie für unsere Beispiel-Punktmenge die Hülle ermittelt wird. Punkt B hat die kleinste y-Koordinate und ist der Ausgangspunkt. Danach ist M der erste Punkt, auf den der schwenkende Strahl trifft, dann L usw.

Abbildung 25.2
Abbildung 25.2 Einwickeln einer Punktmenge.

Natürlich brauchen wir nicht wirklich durch alle möglichen Winkelpositionen zu schwenken; wir führen einfach eine standardmäßige Berechnung zum Auffinden eines Minimums aus, um den Punkt zu ermitteln, der als nächster getroffen würde. Jedesmal, wenn wir einen Punkt in die Hülle aufnehmen wollen, müssen wir alle Punkte betrachten, die noch nicht in die Hülle aufgenommen wurden. Daher ist das Verfahren der Anwendung von selection sort sehr ähnlich: Wir wählen sukzessive den jeweils »besten« unter den noch nicht gewählten Punkten aus, unter Benutzung einer groben Suchmethode für das Minimum. Die tatsächliche erforderliche Umordnung der Daten wird in Abbildung 25.3 dargestellt: Die M-te Zeile der Tabelle zeigt die Situation nach dem Hinzufügen des M-ten Punktes zur Hülle.

Abbildung 25.3
Abbildung 25.3 Datenumordnung beim Einwickeln eines Packets.

Das folgende Programm bestimmt die konvexe Hülle für ein Feld p[1..N] von Punkten, das in der zu Beginn von Kapitel 24 beschriebenen Form dargestellt ist. Die Grundlage für diese Implementation ist die Funktion theta(p1,p2: point), die im vorangegangenen Kapitel eingeführt wurde und von der man sich vorstellen kann, daß sie den Winkel zwischen p1, p2 und der Horizontalen liefert (obwohl sie in Wirklichkeit eine einfacher berechnete Zahl mit den gleichen Ordnungseigenschaften zurückgibt). Im übrigen folgt die Implementation unmittelbar aus der obigen Beschreibung. Die Position p[N + 1] des Felds wird benutzt, um eine Marke zu speichern.

    function wrap: integer;
      var i,min,M: integer;
          minangle,v: real;
          t: point;
      begin
      min:=1;
      for i:=2 to N do
        if p[i].y<p[min].y then min:=i;
      M:=0; p[N+1]:=p[min]; minangle:=0.0;
      repeat
        M:=M+1; t:=p[M]; p[M]:=p[min]; p[min]:=t;
        min:=N+1; v:=minangle; minangle:=360.0;
        for i:=M+1 to N+1 do
          if theta(p[M],p[i])>v then
            if theta(p[M],p[i])<minangle then
              begin min:=i; minangle:=theta(p[M],p[min]) end;
      until min=N+1;
      wrap:=M;
      end;

Zuerst wird der Punkt mit der kleinsten y-Koordinate gefunden und in p[N + 1] kopiert, um die Schleife abzubrechen. Die Variable M wird für die Anzahl der bisher in die Hülle aufgenommenen Punkte verwendet, und v ist der aktuelle Wert des »Schwenkwinkels« (des Winkels zwischen der Horizontalen und der Geraden, die p[M - 1] und p[M] verbindet). Die repeat-Schleife nimmt den letzten gefundenen Punkt in die Hülle auf, indem sie ihn mit dem M-ten Punkt vertauscht, und verwendet die Funktion theta aus dem vorangegangenen Kapitel, um den Winkel zu berechnen, der zwischen der Horizontalen und der diesen Punkt und jeden der noch nicht in die Hülle aufgenommenen Punkte verbindenden Geraden eingeschlossen ist. Dabei sucht sie denjenigen Punkt, dessen Winkel unter den Punkten, deren Winkel größer als v sind, am kleinsten ist. Die Schleife bricht ab, wenn der erste Punkt (in Wirklichkeit die Kopie des ersten Punktes, die in p[N + 1] gespeichert wurde) wieder erreicht wird.

Dieses Programm kann Punkte, die auf einer der die konvexe Hülle begrenzenden Seiten liegen, wahlweise zurückgeben oder nicht. Diese Situation tritt ein, wenn während der Ausführung des Algorithmus mehr als ein Punkt den gleichen Wert theta hat wie p[M]; die obige Implementation gibt denjenigen dieser Punkte zurück, der zuerst angetroffen wird, auch wenn es andere geben kann, die näher bei p[M] liegen. Wenn es wichtig ist, alle Punkte zu finden, die auf den Seiten der konvexen Hülle liegen, so können wir dies erreichen, indem wir theta so verändern, daß die Entfernung zwischen den Punkten mit berücksichtigt wird und dem näher liegenden Punkt einen kleineren Wert zuweisen, wenn zwei Punkte den gleichen Winkel haben.

Der Hauptnachteil beim »Einwickeln« besteht darin, daß im ungünstigsten Fall, wenn alle Punkte der konvexen Hülle angehören, die Laufzeit proportional zu N2 ist (ebenso wie selection sort). Andererseits hat das Verfahren den Vorzug, daß es sich auf drei (oder mehr) Dimensionen verallgemeinern läßt. Die konvexe Hülle einer Menge von Punkten in einem k-dimensionalen Raum ist das minimale konvexe Polytop, das alle diese Punkte enthält, wobei ein konvexes Polytop durch die Eigenschaft definiert ist, daß jede Linie, die zwei in seinem Inneren befindliche Punkte verbindet, sich selbst vollständig in seinem Inneren befinden muß. Beispielsweise ist die konvexe Hülle einer Menge von Punkten im dreidimensionalen Raum ein konvexes dreidimensionales Objekt mit ebenen Seitenflächen. Sie kann gefunden werden, indem eine Ebene »geschwenkt« wird, bis die Hülle berührt wird, und indem dann Seiten der Ebene »gefaltet« werden, wobei die Schwenkung um verschiedene Linien an der Grenze der Hülle erfolgt, so lange, bis das »Paket eingewickelt« ist. (Wie bei vielen geometrischen Algorithmen ist es viel leichter, diese Verallgemeinerung zu beschreiben, als sie zu implementieren!)


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