Convex Hull
Eine Convex Hull ist das kleinste konvexe Polygon, das eine Menge von Punkten vollständig umschließt, vergleichbar mit einem Gummiband, das um die äußersten Punkte gespannt wird. In GIS wird sie zur Abgrenzung von Artenverbreitungsgebieten, zur Definition von Untersuchungsgebietsgrenzen und zur Berechnung von räumlichen Ausdehnungsmaßen verwendet.
Überblick
Die Convex Hull einer Punktmenge in der Ebene ist das kleinste konvexe Polygon, bei dem jeder Punkt der Menge auf dem Rand oder im Inneren des Polygons liegt. Anschaulich lässt sich dies mit Nägeln vergleichen, die in ein Brett geschlagen wurden: Die Convex Hull entspricht der Form, die entsteht, wenn ein straff gespanntes Gummiband um alle Nägel gelegt wird. Jeder Eckpunkt der Convex Hull ist ein Punkt aus der ursprünglichen Menge, und das Polygon weist keine nach innen gerichteten Winkel auf.
Algorithmen
Mehrere effiziente Algorithmen berechnen die Convex Hull. Der Graham-Scan sortiert Punkte nach ihrem Polarwinkel und verarbeitet sie in dieser Reihenfolge, wodurch eine Laufzeit von O(n log n) erreicht wird. Der Jarvis-March (Gift Wrapping) wählt iterativ den jeweils nächsten Randpunkt aus und läuft in O(nh), wobei h die Anzahl der Randpunkte bezeichnet. Divide-and-Conquer-Algorithmen teilen die Punktmenge auf, berechnen Teil-Hüllen und führen diese anschließend zusammen. Der Quickhull-Algorithmus unterteilt Punkte relativ zu extremen Kanten und verarbeitet die entstehenden Teilmengen rekursiv. Die meisten GISGISGeographic Information Systems (GIS) enable users to analyze and visualize spatial data to uncover patterns, relation...-Programme bieten integrierte Werkzeuge zur Berechnung der Convex Hull, die diese Algorithmen im Hintergrund anwenden.
Anwendungen
Ökologen berechnen Convex Hulls, um das Streifgebiet oder die geografische Ausdehnung einer Art anhand von Beobachtungspunkten zu schätzen. In der Naturschutzbiologie gelten Minimum Convex Polygons als Standardmethode zur Angabe von Artenverbreitungsgebieten. Logistikanalysten definieren damit das Einzugsgebiet einer Lieferflotte oder eines Kundenstamms. Stadtplaner berechnen den räumlichen Fußabdruck von Einrichtungsnetzwerken. In der computergestützten Geometrie dient die Convex Hull als Vorverarbeitungsschritt für komplexere Operationen, darunter die Delaunay-Triangulation und die Kollisionserkennung.
Einschränkungen
Convex Hulls können die tatsächliche Ausdehnung einer Punktmenge überschätzen, da sie keine Konkavitäten abbilden können. Ein weit verstreuter Cluster mit konkaver Verteilung wird von einem konvexen Polygon umschlossen, das große leere Flächen einschließt. Für eine engere Grenzschätzung werden daher Concave-Hull-Algorithmen bevorzugt.
Bereit?
Sehen Sie Mapular
in Aktion.
Buchen Sie eine kostenlose 30-minütige Demo. Wir zeigen Ihnen genau, wie die Plattform für Ihren Anwendungsfall funktioniert. Kein generisches Foliendeck, keine Verpflichtung.