Graham Scan
aus Wikipedia, der freien Enzyklopädie
Der Mathematiker Ronald Graham entdeckte 1972 einen effizienten Algorithmus zur Berechnung der konvexen Hülle eines simplen Polygons. Seine asymptotische Laufzeit ist O(n log n).
Inhaltsverzeichnis |
[Bearbeiten] Beschreibung
[Bearbeiten] Vorbereitung
Sei S = {P} eine endliche Punktmenge. Der Algorithmus beginnt mit einem Punkt der Menge welcher garantiert ein Eckpunkt der konvexen Hülle ist. Man sucht sich dazu den Punkt mit der kleinsten Ordinate. Sind dies mehrere, so sucht man sich aus diesen Punkten den mit der kleinsten Abzisse aus (lexikographische Suche). Diese Suche kann in O(n) Schritten durchgeführt werden. Nachdem der Startpunkt P0 gefunden wurde, sortiert der Algorithmus die restlichen Punkte P in S nach aufsteigendem Winkel zwischen P0 -> P und der x-Achse gegen den Uhrzeigersinn. Haben dabei zwei Punkte den gleichen Winkel (d.h. liegen mit P0 auf einer Linie, sind kollinear mit P0), so wird der Punkt welcher näher an P0 liegt verworfen.
Will man bestimmen, ob ein Punkt links von einem anderen liegt d.h. ob die Linie eines Punkts mit dem Startpunkt einen größeren Winkel zur x-Achse hat als ein anderer Punkt mit dem Startpunkt, sollte man keine trigonometrischen Funktionen verwenden. Die Funktion T(P1, P2, P3) liefert das gewünschte Ergebnis mit weniger Rechenaufwand (5 Subtraktionen, 2 Multiplikationen) und genauer. Das Ergebnis bleibt hier im rationalen Zahlenbereich, welcher von einigen Softwarepaketen ohne Verlust von Genauigkeit abgebildet werden kann. T bekommt drei Punkte P1, P2 und P3 übergeben. Das Ergebnis wird über den folgenden Ausdruck berechnet.
[Bearbeiten] Berechnung
S sei nun die sortierte Punktmenge. Als nächstes läuft man alle Punkte in S durch und prüft, ob diese Eckpunkte der konvexen Hülle sind. Es wird ein Stapelspeicher (Stack) angelegt, auf welchem sich alle Eckpunkte der konvexen Hülle für alle bereits abgearbeiteten Punkte befinden. Zu Beginn liegen P0 und P1 auf dem Stapel. Im k - ten Schritt wird Pk zur Betrachtung herangezogen und berechnet, wie er die vorherige konvexe Hülle verändert. Aufgrund der Sortierung liegt Pk immer außerhalb der Hülle der vorherigen Punkte Pi mit i < k.
Durch das Hinzufügen des Punktes kann es vorkommen, dass bereits auf dem Stapel liegende Punkte nicht mehr zur neuen konvexen Hülle gehören. Diese Punkte müssen mittels der „pop“ Operation vom Stapel entfernt werden. Ob ein Punkt noch zur konvexen Hülle gehört oder nicht ermitteln man, indem man berechnet, ob Pk links oder rechts des Vektors PT2->PT1 liegt (PT1 = oberstes Element des Stapels, PT2 = Element direkt unter PT1). Liegt Pk links, so bleibt PT1 weiterhin auf dem Stapel und Pk wird mit „push“ auf dem Stapel abgelegt, liegt Pk rechts, so wird PT1 von der neuen konvexen Hülle verschluckt, vom Stapel entfernt und die nächsten beiden oberen Punkte untersucht.
Dieser Test wird solange durchgeführt, bis Pk links des Vektors PT2->PT1 oder nur noch P0 auf dem Stapel liegt. In beiden Fällen wird dann Pk auf dem Stapel abgelegt und mit dem nächsten Punkt Pk+1 weitergerechnet. Die folgende Abbildung zeigt ein Beispiel, in welchem alle Fälle des eben beschriebenen Tests auftreten.
In nebenstehender Abbildung werden zunächst die Punkt Pt4, Pt3, Pt2 und Pk-1 auf den Stack gelegt. Zu jedem Zeitpunkt bilden die Punkte auf dem Stack ein konvexes Polygon (gestrichelte Linien). Erst als Pk hinzukommen soll, fliegen Pk-1 und Pt2 wieder raus, da sie zusammen mit Pk nicht konvex sind. Die konvexe Hülle dieser Punktmenge besteht aus P0, Pt4, Pt3 und Pk. P0 liegt dabei auf dem Stack ganz unten und Pk ganz oben. Die Punkte des gesuchten konvexen Polygons können mit "pop" im Uhrzeigersinn vom Stapel geholt werden.
[Bearbeiten] Anmerkung
Die Anzahl der "push" und "pop" Operationen übersteigt die obere Grenze von 2N (N = Anzahl der Punkte in der Eingabemenge) nicht. Die Berechnung ist also O(N). Die Sortierung der Punkte nach Winkel kann mit jedem beliebigen Sortieralgorithmus durchgeführt werden, z. B. dem QuickSort. Dieser hat im Durchschnitt average case die asympt. Laufzeit von O(N log N). Das bedeutet, dass die Laufzeit des Algorithmus durch die Sortierung vorgegeben ist da O(N) + O(N log N) = O(N log N).
[Bearbeiten] Pseudocode
