Konvexe Hülle

Konvexe Hülle

 aufwärts

Konvexe Polygone

Wir betrachten nun Polygone, also Gebiete, die von einfachen Polygonzügen umschlossen sind.

Definition:  Sei p ein Punkt in einem Polygon. Ein Punkt q ist von p aus sichtbar, wenn die Verbindungsstrecke zwischen p und q ganz im Polygon enthalten ist.

Die Vorstellung ist, dass der Rand des Polygons undurchsichtig ist. Ein Punkt ist von einem anderen Punkt aus nicht sichtbar, wenn die Verbindungsstrecke zwischen den Punkten den Rand des Polygons schneidet. In folgendem Bild 1 ist q von p aus nicht sichtbar.

Bild 1: Punkt q ist von p aus nicht sichtbar
Bild 1: Punkt q ist von p aus nicht sichtbar

Definition:  Ein Polygon heißt sternförmig, wenn es einen Punkt enthält, von dem aus alle Punkte des Polygons sichtbar sind. Ein Polygon heißt konvex, wenn von jedem seiner Punkte aus alle Punkte des Polygons sichtbar sind.

Beispiel:  Das Polygon von Bild 2a ist konvex; das Polygon von Bild 2b ist sternförmig – alle Punkte sind von der unteren Ecke aus sichtbar.

Bild 2: Konvexes Polygon (a), sternförmiges Polygon (b)
Bild 2: Konvexes Polygon (a), sternförmiges Polygon (b)

Satz:  Ein einfacher Polygonzug, der nur konvexe Ecken hat, umschließt ein konvexes Polygon.

Die Umkehrung gilt ebenfalls: wenn die Ecken eines konvexen Polygons entgegen dem Uhrzeigersinn durchlaufen werden, also so, dass die umschlossene Fläche stets links liegt, dann sind alle Ecken konvex.

Konvexe Hülle

Ein konvexes Polygon ist ein Spezialfall einer allgemeinen konvexen Menge von Punkten.

Definition:  Eine Menge von Punkten in der Ebene heißt konvex, wenn sie mit je zwei Punkten auch deren Verbindungsstrecke enthält.

Bild 3: Konvexe Menge (a) und nicht konvexe Menge (b)
Bild 3: Konvexe Menge (a) und nicht konvexe Menge (b)

Definition:  Gegeben sei eine Menge M von Punkten in der Ebene. Die konvexe Hülle von M ist die kleinste konvexe Menge, in der M enthalten ist.

Satz:  Wenn M eine endliche Menge ist, so ist die konvexe Hülle von M ein konvexes Polygon oder, wenn die Punkte von M alle auf einer Linie liegen, ein Liniensegment.

Beispiel:  Bild 4 zeigt eine endliche Menge von Punkten und deren konvexe Hülle.

Bild 4: Menge von Punkten (a) und deren konvexe Hülle (b)
Bild 4: Menge von Punkten (a) und deren konvexe Hülle (b)

Stellen wir uns die Punkte als Nägel vor, die in einem Brett stecken, dann erhalten wir den Rand der konvexen Hülle, indem wir ein Gummiband um die Nägel spannen.

 

Problem Konvexe Hülle
Eingabe:Endliche Menge M von Punkten in der Ebene
Ausgabe:Diejenigen Punkte von M, die auf dem Rand des konvexen Hüllpolygons von M liegen, in umlaufender Reihenfolge.

 

Untere Schranke

Es wird gezeigt, dass die Berechnung der konvexen Hülle von n Punkten mindestens so schwer ist wie das Sortieren von n verschiedenen Zahlen.

Hierzu wird das Sortierproblem auf das Problem der Berechnung der konvexen Hülle reduziert. Dies geschieht in drei Schritten:

Gegeben sei also ein beliebiges Exemplar des Sortierproblems mit n verschiedenen Zahlen x0, ..., xn-1. Zu jeder dieser Zahlen xi wird der Punkt (xi, xi2) erzeugt.

Die n Punkte liegen auf der Normalparabel (Bild 5), alle sind Eckpunkte des konvexen Hüllpolygons. Das Ergebnis der Berechnung der konvexen Hülle sind die n Eckpunkte in umlaufender Reihenfolge.

Die Lösung des Sortierproblems ergibt sich hieraus, indem zunächst der Eckpunkt mit kleinster x-Koordinate gesucht wird und von diesem aus die x-Koordinaten der anderen Eckpunkte in umlaufender Reihenfolge ausgegeben werden. Die Folge dieser x-Koordinaten ist die sortierte Folge x0, ..., xn-1.

Konvexe Hülle von Punkten auf der Parabel
Bild 5: Konvexe Hülle der Punktemenge { (xi, xi2) }

Die Transformation, nämlich das Erzeugen der n Punkte aus den n Zahlen, benötigt Zeit O(n). Die Rücktransformation, nämlich das Suchen des Punktes mit kleinster x-Koordinate, benötigt ebenfalls Zeit O(n). Somit muss die Berechnung der konvexen Hülle Zeit Ω(n log(n)) benötigen. Denn ginge es schneller, so könnten wir schneller als in Zeit Ω(n log(n)) sortieren. Dies aber ist nicht möglich, da Ω(n log(n)) eine untere Schranke für das Sortierproblem ist.

Satz:  Die Zeitkomplexität der Berechnung der konvexen Hülle von n Punkten liegt in Ω(n log(n)).

Die im Folgenden vorgestellten Algorithmen mit der Zeitkomplexität von O(n log n) sind also optimal.

Konvexe Hülle eines sternförmigen Polygons

Satz:  Die konvexe Hülle eines sternförmigen Polygons mit n Ecken lässt sich in Zeit Θ(n) berechnen.

Beweis:  Ein sternförmiges Polygon kann konkave Ecken haben. Die Idee ist, diese konkaven Ecken zu überbrücken, so dass schließlich ein konvexes Polygon entsteht.

Die Ecken des sternförmigen Polygons werden der Reihe nach entgegen dem Uhrzeigersinn durchlaufen. Immer wenn dabei eine konkave Ecke gefunden wird, wird diese überbrückt, so dass sie anschließend im Inneren des Polygons liegt (Bild 6a). Es kann vorkommen, dass die vorherige Ecke, die zunächst konvex war, hierdurch zu einer konkaven Ecke wird (Bild 6b). Es muss also in diesem Fall so weit zurückgegangen werden, bis die jeweils letzte Ecke konvex ist (Bild 6c).

Der Durchlauf beginnt bei einer Ecke mit minimaler y-Koordinate; diese ist auf jeden Fall konvex und braucht nicht untersucht zu werden. Während der Ausführung des Verfahrens bleibt das Polygon immer sternförmig. Zum Schluss hat es nur konvexe Ecken und ist damit konvex.

Obwohl möglicherweise auf dem Weg entlang des Polygonzugs auch zurückgegangen werden muss, benötigt das Verfahren nur O(n) Schritte, denn ein Rückwärtsschritt entsteht nur, wenn zuvor eine Ecke ins Innere des Polygons verbannt wurde. Dies kann höchstens n-mal geschehen.

Bild 6: Überbrücken von konkaven Ecken
Bild 6: Überbrücken von konkaven Ecken

Das Verfahren funktioniert im allgemeinen nur mit sternförmigen Polygonen.1)

Aufgabe 1:  Geben Sie einen einfachen, jedoch nicht sternförmigen Polygonzug an, bei dem durch das Verfahren ein nicht einfacher Polygonzug erzeugt wird.

Algorithmen zur Berechnung der konvexen Hülle

Der erste im Folgenden angegebene Algorithmus zur Berechnung der konvexen Hülle einer endlichen Menge von Punkten, der Graham-Scan-Algorithmus, baut auf dem Verfahren für sternförmige Polynome auf.

Es folgen dann zwei weitere Algorithmen, der Jarvis-March-Algorithmus und der Quickhull-Algorithmus.

Literatur

[PSh 85]F.P. Preparata, M.I. Shamos: Computational Geometry. Springer (1985)
[Klei 97]R. Klein: Algorithmische Geometrie. Addison-Wesley (1997)

1)  Es gibt jedoch andere Verfahren, die für beliebige einfache Polygonzüge die konvexe Hülle in Zeit Θ(n) berechnen.

 

Weiter mit:   [Graham-Scan-Algorithmus]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 25.12.2002   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