Konvexe Hülle

Graham-Scan-Algorithmus

 aufwärts

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
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
Bild 2: Aus dem sternförmigen Polygonzug erzeugtes konvexes Polygon

In folgender Realisierung des Graham-Scan-Algorithmus wird die Tatsache ausgenutzt, dass aufgrund der Sortierung der Punkte die Ecken p0 und p1 konvex sind.

 

Algorithmus Graham-Scan
Eingabe:Array p mit n Punkten
Ausgabe:Array p derart umgeordnet, dass die ersten h Einträge die Ecken des konvexen Hüllpolygons sind
Methode:
  1. bestimme Punkt q mit minimaler y-Koordinate
  2. subtrahiere q von allen Punkten des Arrays (so dass q selbst zum Nullpunkt wird)
  3. sortiere die Punkte des Arrays nach ihrem Winkel, und bei gleichem Winkel nach ihrem Abstand zum Nullpunkt (der Punkt q wird zu p0)
  4. addiere q zu allen Punkten des Arrays (so dass die ursprünglichen Punkte wiederhergestellt werden)
  5. // durchlaufe die Punkte und überbrücke konkave Ecken:

    setze i = 3 und k = 3

    solange k<n wiederhole

    1. vertausche pi und pk
    2. solange pi-2 pi-1 pi nicht konvex wiederhole
      1. vertausche pi-1 und pi
      2. setze i = i – 1
    3. setze i = i + 1 und k = k + 1

    setze h = i

 

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 Sortieralgorithmus muss nur wissen, welcher von jeweils zwei Punkten pi und pj den größeren Winkel hat. Dies lässt sich danach entscheiden, ob das Dreieck 0 pi pj einen positiven oder negativen Flächeninhalt hat. Der doppelte Flächeninhalt ergibt sich durch die einfache Berechnung xiyj – xjyi (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 Sortierfunktion 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 Hilfsfunktionen. Die Funktion exchange(i, j) vertauscht zwei Punkte im Array. Die Funktion makeRelTo(p0) rechnet alle Punkte des Arrays relativ zu p0 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 pi-1 pi pi+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

[CLRS 01]T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2. Auflage, The MIT Press (2001)
[Gra 72]R.L. Graham: An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters 1, 132-133 (1972)
[PSh 85]F.P. Preparata, M.I. Shamos: Computational Geometry. Springer (1985)
[Web 1]http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html  

 

Weiter mit:   [Jarvis-March-Algorithmus]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 12.05.2003   Updated: 20.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik