Gift-Wrapping-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
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.

Beschreibung[Bearbeiten | Quelltext bearbeiten]

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.

Pseudocode[Bearbeiten | Quelltext bearbeiten]

  jarvis(S)
    startpunkt = Punkt mit kleinster Ordinate
    i = 0
    wiederhole
        P[i] = startpunkt
        endpunkt = S[0]
        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]

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]