Konvexe Hülle

Idee

Der Quickhull-Algorithmus zur Berechnung der konvexen Hülle einer endlichen Menge von Punkten in der Ebene verwendet eine ähnliche Technik wie Quicksort: Teilmengen der Punkte werden jeweils partitioniert in diejenigen Punkte, die links von einer bestimmten Geraden liegen und diejenigen, die rechts der Geraden liegen. Diese Punktemengen werden dann rekursiv weiter behandelt.

Gegeben sei eine Gerade g durch zwei Ecken p₀ und p₁ des konvexen Hüllpolygons sowie die Menge R derjenigen Punkte, die rechts von g liegen (Bild 1).

In der Menge R wird der am weitesten von g entfernte Punkt q gesucht, dieser ist eine weitere Ecke des konvexen Hüllpolygons. Dann wird eine Gerade g₀ durch p₀ und q gelegt, und die Punktemenge R wird partitioniert in die Menge R₀ derjenigen Punkte, die rechts von g₀ liegen und die Menge L₀ derjenigen Punkte, die links von g₀ liegen.

Ferner wird eine Gerade g₁ durch q und p₁ gelegt, und L₀ wird partitioniert in die Menge R₁ derjenigen Punkte, die rechts von g₁ liegen und die Menge L₁ derjenigen Punkte, die links von g₁ liegen.

Die Punkte der Menge L₁ liegen im Inneren des konvexen Hüllpolygons. Mit den Geraden g₀ und g₁ und den zugehörigen Mengen R₀ und R₁ wird rekursiv weiter verfahren.

Um die Ausgangssituation herzustellen, wird der Punkt mit kleinster y-Koordinate bestimmt. Bei mehreren Punkten mit kleinster y-Koordinate wird von diesen der Punkt mit kleinster x-Koordinate gewählt. Dieser Punkt p₀ ist eine Ecke des konvexen Hüllpolygons. Als zweite Ecke p₁ wird ebenfalls p₀ genommen. Damit die Abstandsberechnung durch Flächenberechnung mithilfe der Funktion area2 aus der Klasse Point funktioniert, wird p₁ um ein sehr kleines Stück nach links verschoben.¹) Durch p₀ und p₁ wird eine waagerechte Gerade g gelegt. Alle Punkte liegen somit rechts von g.

Implementierung

Die folgende Klasse QuickHull implementiert den QuickHull-Algorithmus. Der Aufruf erfolgt mit

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.

In der Funktion quickhull wird zunächst der Punkt mit kleinster y-Koordinate gesucht und an die Position 0 im Array gebracht. Dann wird eine waagerechte Gerade durch die Punkte p₀ und p₀' erzeugt, wobei p₀' durch Verschiebung von p₀ nach links um ein sehr kleines Stück hervorgeht. Die rechts von der Geraden oder auf ihr liegenden Punkte (also alle Punkte), mit Ausnahme von p₀, bilden den Anfangsbereich von Punkten, von dem die Ecken des Hüllpolygons berechnet werden. Die geschieht rekursiv mit der Funktion computeHullPoints(g, lo, hi).

Zunächst wird im Indexbereich von lo bis hi mit der Funktion indexOfFurthestPoint der am weitesten rechts von der Geraden liegende Punkt gesucht. Wiederum wird dies realisiert durch Berechnung des Flächeninhalts des Dreiecks, das aus den beiden gegebenen Punkten der Geraden und dem jeweils untersuchten Punkt p_i gebildet wird. Alle Punkte p_i liegen rechts von oder auf der Geraden, daher ist der Flächeninhalt stets 0 oder negativ. Da die Grundlinie des Dreiecks konstant bleibt, ist der negative Flächeninhalt ein Maß für die Höhe des Dreiecks, also für den Abstand des Punktes.

Wenn alle Punkte auf einer waagerechten Linie liegen und somit alle Flächeninhalte 0 sind, wird als der "am weitesten rechts von der Geraden" liegende Punkt der am weitesten rechts von p₀ liegende Punkt genommen.

Von den beiden gegebenen Punkten der Geraden werden dann Verbindungsstrecken g₀ und g₁ zu dem entferntesten Punkt gezogen.

Die Funktion partition sortiert die Punkte des Arrays im Indexbereich zwischen lo und hi so, dass der Indexbereich zwischen lo und i-1 die Punkte enthält, die rechts von g liegen, und der Indexbereich zwischen i und hi die Punkte enthält, die links von oder auf g liegen. Als Rückgabewert liefert die Funktion die Position i.

Eine Besonderheit dieser Implementation besteht darin, dass die gefundenen Ecken des Hüllpolygons in der richtigen Reihenfolge an die Positionen 0, ..., h-1 des Arrays getauscht werden (so wie beim Graham-Scan- und beim Jarvis-March-Algorithmus). Dies geschieht durch jeweils drei Aufrufe der Funktion exchange.

Analyse

Die Analyse der Zeitkomplexität des Quickhull-Algorithmus gestaltet sich ähnlich wie bei Quicksort. Im besten Fall werden in jedem Rekursionsschritt (außer dem ersten) immer mindestens so viele Punkte ins Innere des bis dahin erzeugten Polygons verbannt, wie noch außerhalb verbleiben. Dann liegt die Komplexität in Θ(n log(n)). Im schlechtesten Fall besteht R₀ in jedem Rekursionsschritt jeweils aus allen Punkten von R außer dem entferntesten Punkt q. Dann beträgt die Komplexität Θ(n²). Im Durchschnitt liegt die Komplexität in Θ(n log(n)).

Literatur

[PSh 85]   F.P. Preparata, M.I. Shamos: Computational Geometry. Springer (1985)

[Web 1]   http://www.cs.yorku.ca/~aaw/Hang/quick_hull/QuickHull.html