Benutzer:Jakob.westhoff/QuickHull
QuickHull ist ein Algorithmus zur Berechnung der Konvexen Hülle einer beliebigen Punktemenge im zwei- und dreidimensionalen Raum. Die Konvexe Hülle einer Menge von Punkten wird beschrieben durch einen geschlossenen Polygonzug welcher die Verbindung aller äußeren Punkte der Menge darstellt, und somit alle Punkte der Menge einschließt. Eine häufig verwendete intuitive Erklärung dieser Hülle ist ein Gummiband, welches sich um die Punktemenge spannt. Dieses bildet, wenn es straff auf allen äußeren Punkten aufliegt die Konvexe Hülle der Punktemenge.
Namensgebung und Enstehung
BearbeitenDer Name QuickHull leitet sich aus der Ähnlichkeit zu Quicksort, einem Algorithmus zum sortieren beliebiger Mengen, ab. Er findet zum ersten mal Erwähnung im Buch Computational geometry von Franco Preparata und Michael Shamos [1], in dem die beiden Autoren den hier beschriebenen Algorithmus vorstellen, welcher die Ideen anderer Autoren aufgreift. [2] [3] [4]
Algorithmus
BearbeitenDie algorithmische Idee zu QuickHull kommt aus dem Teile und Herrsche Prinzip, welches in der Informatik häufig zum Einsatz kommt. Es beschreibt die Vorgehensweise das gegebene Problem in kleinere Probleme zu unterteilen und diese dann durch Anwendung desgleichen Algorithmus rekursiv zu lösen. Es wird versucht eine geschickte Aufteilung zu wählen, so dass durch diese bereits eine große Anzahl von ungültigen Lösungsmengen herrausfällt. Algorithmen, welche nach diesem Prinzip entworfen wurden können meist einfach und gut lesbar implementiert werden, da sie eine verständliche rekursive Struktur besitzen.
Beispiel
Bearbeiten
Der Algorithmus operiert auf einer beliebigen Menge von Punkten. Es bestehen keinerlei besondere Anforderungen an die Anordnung oder Anzahl der Punkte. Eine symmetrische Anordnung der Punkte besitzt jedoch eine höhere Wahrscheinlichkeit den Algorithmus seine Best Case (bester Fall) Laufzeitschranke von überschreiten zu lassen und deutlich langsamer zu sein.
Zunächst muss eine initiale Unterteilungsgerade bestimmt werden. Hierfür werden die beiden Extremalpunkte der X-Achse genutzt. Also diejenigen Punkte der Eingabemenge, welche am weitesten links und am weitesten rechts liegen. Diese Punkte können bereits dem Polygonzug der Konvexen Hülle hinzugefügt werden, da sie als Extrempunkte garantiert Bestandteil dessen sind.
Die beiden gefundenen Punkte bilden eine Gerade, welche die Punktmenge in zwei Bereiche teilt. Alle Punkte links von der Geraden repräsentieren eine Menge und alle Punkte rechts von der Gerade die andere. Rechts und links ergeben sich in diesem Zusammenhang aus dem Winkel zwischem dem Richtungsvektor der Trennungsgeraden und dem Vektor definiert durch den Anfangspunkt der Geraden und den zu überprüfenden Punkt. Ist dieser Winkel kleiner als 180°, dann wird der Punkt als rechts von der Geraden betrachtet, bei Winkeln größer 180° als links von ihr.
Die beiden durch diese Gerade getrennten Punktmengen werden nun rekursiv mit dem QuickHull Algorithmus weiter verarbeitet. In diesem Beispiel wird lediglich der linke Teil der Punktemenge weiter betrachtet. Alle gemachten Aussagen treffen äquivalent auch auf den rechten Teil zu.
Innerhalb der betrachteten Punktmenge wird jener Punkt bestimmt, der die maximale Distanz von der Geraden besitzt. Dieser ist offensichtlich ebenfalls ein Bestandteil des gesuchten Polygonzugs. Zusammen mit dem Start- und Endpunkt der Geraden ensteht ein Dreieck.
Das Dreieck setzt sich zusammen aus drei Punkten, von denen alle Bestandteil des Konvexen-Hülle-Polygons sind. Aus diesem Grund können alle Punkte im inneren dieses Dreiecks nicht Bestandteil dieses Polygons sein, da sie ja bereits in seinem Inneren liegen. Alle Punkte innerhalb dieses Dreickes können also bei weiteren rekursiven Aufrufen des Algorithmus ignoriert werden.
Die sich als Seiten des Dreiecks ergebenden Geraden werden nun als erneute Trenngeraden der Punktemenge betrachtet. Alle Punkte links von dem Dreieck repräsentieren eine Menge, alle Punkte rechts von dem Dreieck die andere.
Diese rekursive Aufteilung und Bestimmung weiterer Punkte wird so lange wiederholt, bis nur noch der Start- und Endpunkt der Trenngeraden Bestandteil der zu betrachtenden Punktmenge sind, denn in diesem Fall ist klar, dass diese Gerade ein Segment des gesuchten Polygonzugs darstellt.
Literatur
Bearbeiten- ↑ Franco P. Preparata and Michael Ian Shamos: Computational Geometry - An Introduction. Springer-Verlag, 1985, 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6.
- ↑ William F. Eddy: A New convex Hull Algorithm for Planar Sets. In: ACM Transactions on Mathematical Software. 3. Jahrgang, 1977, S. 393–403.
- ↑ Alex Bykat: Convex Hull of a Finite Set of Points in Two Dimensions. In: Information Processing Letters. 7. Jahrgang, 1978, S. 296–298.
- ↑ P. J. Green: Constructing the Convex Hull of a Set of Points in the Plane. In: Computer Journal. 22. Jahrgang, 1979, S. 262–266.
[[Kategorie:Algorithmus]][[Kategorie:Programmierung]]