Concave Hull
Eine Concave Hull ist eine eng anliegende Begrenzung um eine Menge von Punkten, die der Form der Punktverteilung folgt, einschließlich ihrer Einbuchtungen. Im Gegensatz zur konvexen Hülle kann sie unregelmäßige, nicht konvexe Grenzen darstellen, die die tatsächliche räumliche Ausdehnung der Daten besser widerspiegeln.
Überblick
Eine Concave Hull (auch Alpha Shape oder Chi Shape genannt) ist ein Polygon, das eine Menge von Punkten enger umschließt als eine konvexe Hülle, indem es der Grenze erlaubt, sich dort nach innen zu wölben, wo die Punktverteilung zurückweicht. Während eine konvexe Hülle stets die kleinste konvexe Einhüllung erzeugt, verzichtet eine Concave Hull auf Konvexität, um die tatsächliche Form der Punktwolke besser abzubilden.
Algorithmen und Parameter
Mehrere Algorithmen erzeugen Concave Hulls. Alpha Shapes, 1983 von Edelsbrunner eingeführt, verwenden einen Parameter Alpha zur Steuerung des Detailgrads: Kleinere Alpha-Werte erzeugen engere, detailliertere Grenzen, während größere Werte sich der konvexen Hülle annähern. Der k-nächste-Nachbarn-Algorithmus konstruiert die Grenze, indem jeder Punkt mit seinen k nächstgelegenen Nachbarn verbunden wird, wobei k die Konkavität steuert. Chi Shapes verwenden einen Längenschwellenwert, um lange Kanten der Delaunay-Triangulation zu entfernen. Die Wahl des Parameters bestimmt den Kompromiss zwischen Enge der Anpassung und Einfachheit der Grenzlinie.
Anwendungen
Ökologen nutzen Concave Hulls, um Aktionsräume von Arten zu definieren, die den tatsächlichen Formen des Habitats folgen, statt der übermäßig vereinfachten konvexen Polygone. Stadtanalysten grenzen die tatsächliche Ausdehnung bebauter Gebiete anhand von Gebäudepunktdaten ab. Bei Such- und Rettungseinsätzen werden wahrscheinliche Suchgebiete aus Daten zur zuletzt bekannten Position definiert. Einzelhandelsanalysten umreißen Einzugsgebiete von Kunden, die tatsächliche räumliche Muster widerspiegeln. Kartografen erzeugen glatte Grenzdarstellungen für beschriftete Regionen auf Karten.
Vorteile und Grenzen
Concave Hulls erzeugen Grenzen, die die räumliche Ausdehnung unregelmäßig verteilter Daten genauer darstellen und dabei die Überschätzung vermeiden, die konvexen Hüllen innewohnt. Allerdings reagieren die Ergebnisse empfindlich auf den gewählten Konkavitätsparameter, und es gibt keine universell korrekte Einstellung. Die Grenze kann in mehrere Polygone zerfallen, wenn die Punktverteilung Lücken aufweist, und die Berechnung ist aufwendiger als bei konvexen Hüllen.
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.