Konvexe Hülle Graham-Scan-Algorithmus

Idee

Gesucht ist die konvexe Hülle einer endlichen Menge von Punkten in der Ebene. Die Idee des Verfahrens von Graham [Gra 72] ist, aus der Punktemenge zunächst ein sternförmiges Polygon zu konstruieren und dieses anschließend in ein konvexes Polygon umzuformen.

Verfahren

Aus der Punktemenge (Bild 1a) wird zunächst der Punkt q mit minimaler y-Koordinate, bzw. bei mehreren Punkten mit minimaler y-Koordinate, von diesen der Punkt mit minimaler x-Koordinate gewählt. Ausgehend von q werden die Winkel zu allen anderen Punkten bestimmt (Bild 1b). Die Punkte werden nach diesem Winkel sortiert und zu einem Polygonzug verbunden. Es entsteht ein sternförmiges Polygon (Bild 1c).

Bild 1:  Aus der Punktemenge konstruierter sternförmiger Polygonzug

Es kann vorkommen, dass mehrere Punkte den gleichen Winkel haben (vgl. Bild 1b). Punkte gleichen Winkels werden zusätzlich absteigend nach ihrem Abstand zu q sortiert. Bei dem entstehenden Polygonzug können sich Kanten überlappen, so dass ein nicht einfacher Polygonzug entsteht. Dieser ist aber dennoch für den Algorithmus geeignet.

Der sternförmige Polygonzug wird nun ausgehend von q durchlaufen; dabei werden konkave Ecken überbrückt (siehe konvexe Hülle eines sternförmigen Polygons). Das Ergebnis ist ein konvexes Polygon, das die konvexe Hülle der Punktemenge darstellt.

Bild 2:  Aus dem sternförmigen Polygonzug erzeugtes konvexes Polygon

Der Graham-Scan-Algorithmus lässt sich mit folgendem Verfahren realisieren. In dieser Implementierung wird die Tatsache ausgenutzt, dass aufgrund der Sortierung der Punkte die Ecken p₀ und p₁ konvex sind.

Der Algorithmus hat die kleine Unschönheit, dass die letzte Ecke des berechneten konvexe Hüllpolygons eine 180°-Ecke sein kann (vgl. Bild 2). Wenn dies stört, ist es einfach, diese noch zu entfernen.

Sortieren der Punkte

Um die Punkte nach ihrem Winkel zu sortieren, ist es nicht nötig, die Winkel tatsächlich zu berechnen. Der Sortier­algorithmus muss nur wissen, welcher von jeweils zwei Punkten p_i und p_j den größeren Winkel hat. Dies lässt sich danach entscheiden, ob das Dreieck 0 p_i p_j einen positiven oder negativen Flächeninhalt hat. Der doppelte Flächeninhalt ergibt sich durch die einfache Berechnung x_iy_j – x_jy_i (vgl. Fläche eines Dreiecks ). Bei gleichem Winkel, d.h. wenn die Dreiecksfläche gleich Null ist, werden die Punkte nach ihrem Abstand zum Nullpunkt sortiert. Es genügt hier, mit dem Manhattan-Abstand |x| + |y| zu rechnen.

Die Methode isLess der Klasse Point implementiert einen solchen Vergleich. Sie wird in der Sortier­funktion des Graham-Scan-Algorithmus benutzt.

Implementierung

Die folgende Klasse GrahamScan implementiert den Graham-Scan-Algorithmus. Der Aufruf erfolgt mit

    GrahamScan c=new GrahamScan();
    h=c.computeHull(p);

Hierbei ist p ein Array von Punkten. Als Ergebnis der Berechnung werden die Punkte im Array so umgeordnet, dass die ersten h Punkte die Ecken des konvexen Hüllpolynoms in umlaufender Reihenfolge bilden.

Die weiteren Funktionen sind Hilfs­funktionen. Die Funktion exchange(i, j) vertauscht zwei Punkte im Array. Die Funktion makeRelTo(p0) rechnet alle Punkte des Arrays relativ zu p₀ als Nullpunkt um. Die Funktion indexOfLowestPoint() sucht den Punkt mit kleinster y-Koordinate, oder bei mehreren Punkten mit kleinster y-Koordinate, von diesen den Punkt mit kleinster x-Koordinate. Als Ergebnis wird die Position des Punktes im Array zurückgegeben. Die Funktion isConvex(i) testet, ob die Punkte p_i-1 p_i p_i+1 eine konvexe Ecke eines Polygonzuges darstellen. Für das Sortieren der Punkte wird Quicksort verwendet.

public class GrahamScan
{
    private Point[] p;
    private int n;
    private int h;

    public int computeHull(Point[] p)
    {
        this.p=p;
        n=p.length;
        if (n<3) return n;
        h=0;
        grahamScan();
        return h;
    }

    private void grahamScan()
    {
        exchange(0, indexOfLowestPoint());
        Point pl=new Point(p[0]);
        makeRelTo(pl);
        sort();
        makeRelTo(pl.reversed());
        int i=3, k=3;
        while (k<n)
        {
            exchange(i, k);
            while (!isConvex(i-1))
                exchange(i-1, i--);
            k++;
            i++;
        }
        h=i;
    }

    private void exchange(int i, int j)
    {
        Point t=p[i];
        p[i]=p[j];
        p[j]=t;
    }

    private void makeRelTo(Point p0)
    {
        int i;
        Point p1=new Point(p0); // notwendig, weil p0 in p[] sein kann
        for (i=0; i<n; i++)
            p[i].makeRelTo(p1);
    }

    private int indexOfLowestPoint()
    {
        int i, min=0;
        for (i=1; i<n; i++)
            if (p[i].y<p[min].y || p[i].y==p[min].y && p[i].x<p[min].x)
                min=i;
        return min;
    }

    private boolean isConvex(int i)
    {
        return p[i].isConvex(p[i-1], p[i+1]);
    }

    private void sort()
    {
        quicksort(1, n-1); // ohne Punkt 0
    }

    private void quicksort(int lo, int hi)
    {
        int i=lo, j=hi;
        Point q=p[(lo+hi)/2];
        while (i<=j)
        {
            while (p[i].isLess(q)) i++;
            while (q.isLess(p[j])) j--;
            if (i<=j) exchange(i++, j--);
        }
        if (lo<j) quicksort(lo, j);
        if (i<hi) quicksort(i, hi);
    }

}   // end class GrahamScan

Literatur

Weiter mit:   [Jarvis-March-Algorithmus]   oder

H.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 12.05.2003   Updated: 29.03.2011