Graham-Scan - Graham scan

Eine Demo von Grahams Scan, um eine konvexe 2D-Hülle zu finden.

Grahams Scan ist eine Methode zum Auffinden der konvexen Hülle einer endlichen Menge von Punkten in der Ebene mit der Zeitkomplexität O ( n log n ). Es ist nach Ronald Graham benannt , der den ursprünglichen Algorithmus 1972 veröffentlichte. Der Algorithmus findet alle Ecken der konvexen Hülle, die entlang ihrer Grenze geordnet sind. Es verwendet einen Stapel , um Konkavitäten in der Grenze effizient zu erkennen und zu entfernen.

Algorithmus

Wie man sehen kann, sind PAB und ABC gegen den Uhrzeigersinn, BCD jedoch nicht. Der Algorithmus erkennt diese Situation und verwirft zuvor ausgewählte Segmente, bis die Drehung gegen den Uhrzeigersinn erfolgt (in diesem Fall ABD).

Der erste Schritt in diesem Algorithmus besteht darin, den Punkt mit der niedrigsten y-Koordinate zu finden. Wenn die niedrigste y-Koordinate in mehr als einem Punkt in der Menge vorhanden ist, sollte der Punkt mit der niedrigsten x-Koordinate aus den Kandidaten ausgewählt werden. Rufen Sie diesen Punkt P . Dieser Schritt dauert O ( n ), wobei n die Anzahl der fraglichen Punkte ist.

Als nächstes muss die Menge der Punkte in aufsteigender Reihenfolge des Winkels sortiert werden, den sie und der Punkt P mit der x-Achse bilden. Hierfür ist jeder allgemeine Sortieralgorithmus geeignet, beispielsweise Heapsort (das ist O( n log n )).

Die Sortierung nach Winkel erfordert keine Berechnung des Winkels. Es ist möglich, jede beliebige Funktion des Winkels zu verwenden, die im Intervall monoton ist . Der Kosinus wird leicht unter Verwendung des Skalarprodukts berechnet , oder es kann die Steigung der Geraden verwendet werden. Wenn es um numerische Genauigkeit geht, kann die vom Sortieralgorithmus verwendete Vergleichsfunktion das Vorzeichen des Kreuzprodukts verwenden , um relative Winkel zu bestimmen. ${\displaystyle [0,\pi]}$

Der Algorithmus fährt fort, indem er jeden der Punkte in dem sortierten Array der Reihe nach betrachtet. Für jeden Punkt wird zuerst bestimmt, ob das Fahren von den zwei diesem Punkt unmittelbar vorausgehenden Punkten eine Linkskurve oder eine Rechtskurve darstellt. Bei einer Rechtskurve ist der vorletzte Punkt nicht Teil der konvexen Hülle und liegt 'in' dieser. Dieselbe Bestimmung wird dann für die Menge des letzten Punktes und die zwei Punkte, die unmittelbar vor dem Punkt, der innerhalb der Hülle lag, durchgeführt und wird wiederholt, bis eine "Linkskurve"-Menge angetroffen wird, an welcher Stelle der Algorithmus weitergeht zum nächsten Punkt in der Menge von Punkten in der sortierten Anordnung abzüglich aller Punkte, die innerhalb der Hülle gefunden wurden; diese Punkte müssen nicht noch einmal betrachtet werden. (Wenn die drei Punkte zu irgendeinem Zeitpunkt kollinear sind, kann man sich entscheiden, sie entweder zu verwerfen oder zu melden, da es in einigen Anwendungen erforderlich ist, alle Punkte auf der Grenze der konvexen Hülle zu finden.)

Auch hier erfordert die Bestimmung, ob drei Punkte eine "Linkskurve" oder eine "Rechtskurve" bilden, keine Berechnung des tatsächlichen Winkels zwischen den beiden Liniensegmenten und kann tatsächlich nur mit einfacher Arithmetik erreicht werden. Für drei Punkte , und berechnen die z - Koordinate des Kreuzprodukt der beiden Vektoren und , die durch den Ausdruck gegeben ist . Wenn das Ergebnis 0 ist, sind die Punkte kollinear; wenn sie positiv ist, bilden die drei Punkte eine "Linksdrehung" oder eine Ausrichtung gegen den Uhrzeigersinn, andernfalls eine "Rechtsdrehung" oder eine Ausrichtung im Uhrzeigersinn (für nummerierte Punkte gegen den Uhrzeigersinn). ${\displaystyle P_{1}=(x_{1},y_{1})}$${\displaystyle P_{2}=(x_{2},y_{2})}$${\displaystyle P_{3}=(x_{3},y_{3})}$ ${\displaystyle {\overrightarrow {P_{1}P_{2}}}}$${\displaystyle {\overrightarrow {P_{1}P_{3}}}}$${\displaystyle (x_{2}-x_{1})(y_{3}-y_{1})-(y_{2}-y_{1})(x_{3}-x_{1})}$

Dieser Prozess wird schließlich zu dem Punkt zurückkehren, an dem er begonnen hat, an dem der Algorithmus abgeschlossen ist und der Stapel nun die Punkte auf der konvexen Hülle im Gegenuhrzeigersinn enthält.

Zeitkomplexität

Das Sortieren der Punkte hat die Zeitkomplexität O( n log n ). Obwohl es den Anschein hat, dass die Zeitkomplexität der Schleife O( n ² ) ist, weil sie für jeden Punkt zurückgeht, um zu überprüfen, ob einer der vorherigen Punkte eine "Rechtskurve" macht, ist es tatsächlich O( n ), weil jeder Punkt wird in gewisser Weise höchstens zweimal berücksichtigt. Jeder Punkt kann nur einmal als Punkt in einer "Linkskurve" (da der Algorithmus danach zum nächsten Punkt vorrückt ) und als Punkt in einer "Rechtskurve" (da der Punkt entfernt wird) erscheinen. Die Gesamtzeitkomplexität beträgt daher O( n log n ), da die Sortierzeit die Zeit für die tatsächliche Berechnung der konvexen Hülle dominiert. ${\displaystyle (x_{2},y_{2})}$${\displaystyle (x_{3},y_{3})}$${\displaystyle (x_{2},y_{2})}$${\displaystyle (x_{2},y_{2})}$

Pseudocode

Der folgende Code verwendet eine Funktion ccw: ccw > 0, wenn sich drei Punkte gegen den Uhrzeigersinn drehen, im Uhrzeigersinn, wenn ccw < 0, und kollinear, wenn ccw = 0. (Wenn die Koordinaten in realen Anwendungen beliebige reelle Zahlen sind, erfordert die Funktion genauer Vergleich von Gleitkommazahlen, und man muss sich bei "fast" kollinearen Punkten vor numerischen Singularitäten hüten.)

Lassen Sie dann das Ergebnis in der stack.

let points be the list of points
let stack = empty_stack()

find the lowest y-coordinate and leftmost point, called P0
sort points by polar angle with P0, if several points have the same polar angle then only keep the farthest

for point in points:
    # pop the last point from the stack if we turn clockwise to reach this point
    while count stack > 1 and ccw(next_to_top(stack), top(stack), point) <= 0:
        pop stack
    push point to stack
end

Jetzt enthält der Stapel die konvexe Hülle, wobei die Punkte gegen den Uhrzeigersinn ausgerichtet sind und P0 der erste Punkt ist.

Hier next_to_top()ist eine Funktion zum Zurückgeben des Elements einen Eintrag unter dem oberen Ende des Stapels, ohne den Stapel zu ändern, und ähnlich top()zum Zurückgeben des obersten Elements.

Dieser Pseudocode ist von Introduction to Algorithms adaptiert .

Anmerkungen

Die gleiche Grundidee funktioniert auch, wenn die Eingabe nach x-Koordinate statt nach Winkel sortiert wird und die Hülle in zwei Schritten berechnet wird, wobei der obere bzw. der untere Teil der Hülle erzeugt wird. Diese Modifikation wurde von AM Andrew entwickelt und ist als Andrews Monotone Chain Algorithm bekannt . Es hat die gleichen grundlegenden Eigenschaften wie der Scan von Graham.

Die in Grahams Scan verwendete Stapeltechnik ist der für das Problem aller nächsten kleineren Werte sehr ähnlich , und es können auch parallele Algorithmen für alle nächsten kleineren Werte verwendet werden (wie Grahams Scan), um konvexe Hüllen von sortierten Folgen von Punkten effizient zu berechnen.

Numerische Robustheit

Numerische Robustheit ist ein Problem bei Algorithmen, die Gleitkomma- Computerarithmetik mit endlicher Genauigkeit verwenden . Ein Paper aus dem Jahr 2004 analysierte eine einfache inkrementelle Strategie, die insbesondere für eine Implementierung des Graham-Scans verwendet werden kann. Das erklärte Ziel des Papiers war nicht, den Algorithmus speziell zu analysieren, sondern vielmehr ein Lehrbuchbeispiel dafür zu liefern, was und wie an Gleitkommaberechnungen in der Computergeometrie scheitern kann . Später haben D. Jiang und NF Stewart dies näher erläutert und mit Hilfe der Rückwärtsfehleranalyse zwei Hauptschlussfolgerungen gezogen. Der erste ist, dass die konvexe Hülle ein gut konditioniertes Problem ist und man daher Algorithmen erwarten kann, die eine Antwort innerhalb einer vernünftigen Fehlerspanne liefern. Zweitens demonstrieren sie, dass eine Modifikation des Graham-Scans, die sie Graham-Fortune nennen (die Ideen von Steven Fortune für numerische Stabilität einbezieht ) die Probleme endlicher Präzision und ungenauer Daten "in dem Maße, in dem dies möglich ist" überwindet.

Siehe auch

• Algorithmen mit konvexer Hülle

Verweise

Weiterlesen

• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "33.3: Finden der konvexen Hülle". Einführung in Algorithmen (2. Aufl.). MIT Press und McGraw-Hill. S. 949–955. ISBN 0-262-03293-7.