Gift-Wrapping-Algorithmus

Algorithmus zur Berechnung der Konvexen Hülle im zweidimensionalen Raum
Animation des Gift-Wrapping-Algorithmus. Die rote Linien zeigen die bereits gefundenen Strecken der konvexen Hülle, die schwarze zeigt die aktuell Beste, und die grüne Linie zeigt die Strecke, die gerade überprüft wird.

Der Gift-Wrapping-Algorithmus, auch Jarvis-March genannt, ist ein Algorithmus zur Berechnung der konvexen Hülle einer Punktemenge im zweidimensionalen Raum. Er wurde 1973 von R. A. Jarvis veröffentlicht. Der Algorithmus gehört zu den „ausgabesensitiven“ (englisch output-sensitive) Algorithmen.

BeschreibungBearbeiten

Gegeben sei eine Menge   von Punkten in einer Ebene. Als Startpunkt   wird der Punkt mit der kleinsten Ordinate gewählt. Sind dies mehrere, so wird aus diesen der Punkt mit der kleinsten Abszisse gewählt. Der Startpunkt ist somit Teil der konvexen Hülle. Nun wird ein beliebiger Punkt aus der Menge   gewählt, mit welchem der Startpunkt eine Gerade bildet. Als nächstes werden die restlichen Punkte aus der Menge   überprüft, ob ein Punkt links dieser Geraden liegt. Rechts und links ergeben sich in diesem Zusammenhang aus dem Winkel zwischen dem Richtungsvektor der Trennungsgeraden und dem Vektor definiert durch den Anfangspunkt der Geraden und den zu überprüfenden Punkt. Ist dieser Winkel kleiner als 180°, dann wird der Punkt als rechts von der Geraden betrachtet, bei Winkeln größer 180° als links von ihr. Wird ein Punkt links der Geraden gefunden, bildet   mit diesem eine neue Gerade. Anschließend wird der Rest der Menge   überprüft. Für jeden Punkt, der links von dieser Geraden liegt, wird dieser Vorgang wiederholt. Wurden alle Punkte überprüft, ist der zuletzt gefundene Punkt   der nächste Punkt auf der konvexen Hülle. Nun wird   als neuer Startpunkt gewählt und der gesamte Vorgang wiederholt, bis   wieder der Startpunkt ist.

Für jeden Punkt auf der konvexen Hülle muss die komplette Menge   durchlaufen werden. Dieser Teil wird in einer Schleife ausgeführt, wobei jeder Schleifendurchlauf eine Laufzeit von   besitzt. Sei   die Anzahl der Punkte auf der konvexen Hülle, ergibt sich eine Laufzeit von  . Im Worst Case, wenn alle Punkte auf der konvexen Hülle liegen, ergibt sich somit eine Laufzeit von  . Da der Algorithmus von der Anzahl der Punkte auf der konvexen Hülle abhängt, gehört er zu den sogenannten ausgabesensitiven Algorithmen.

PseudocodeBearbeiten

  jarvis(S)
    startpunkt = Punkt mit kleinster Ordinate
    i = 0
    wiederhole
        P[i] = startpunkt
        endpunkt = S[0]
        wenn startpunkt == endpunkt
          endpunkt = S[1]
        für j von 1 bis |S|
          ist (endpunkt == startpunkt) oder (S[j] links von der Geraden zwischen startpunkt und endpunkt)
            endpunkt = S[j]
        startpunkt = endpunkt
        i++
    bis endpunkt == P[0]

LiteraturBearbeiten

WeblinksBearbeiten