Konvexe Hülle von Punkten

Die konvexe Hülle ist das kleinste konvexe Polygon, das alle Punkte einer endlichen Menge enthält — der Umriss eines Gummibands, das um Nägel auf einem Brett gespannt wird. Vermesser, GIS-Analysten, Spieleentwickler und Studierende der algorithmischen Geometrie brauchen diesen Umriss aus ungeordneten Proben: GPS-Spuren, Gebäudegrundrisse, Sprite-Vertices oder Unterrichtswolken von (x, y)-Paaren. Dieses Werkzeug für die konvexe Hülle von Punkten führt den monotonen Ketten-Scan von Andrew aus: Es sortiert die Punkte nach horizontaler und dann vertikaler Koordinate, baut die untere und obere Kette in linearen Durchläufen und liefert die Extremvertices gegen den Uhrzeigersinn. Innenpunkte und kollineare Mittelkanten-Proben fallen automatisch weg. Sie können planare x/y-Paare oder geografische Lat/Lon-Punkte senden; der Geo-Modus berechnet weiterhin eine planare Hülle in der Längengrad–Breitengrad-Ebene, der üblichen lokalen Näherung für Hüllen im Stadt- und Standortmaßstab.

Was eine konvexe Hülle ist und wie die monotone Kette arbeitet

Gegeben eine endliche Punktmenge in der Ebene ist die konvexe Hülle die eindeutige kleinste konvexe Menge, die sie alle enthält. Ihr Rand ist ein konvexes Polygon, dessen Vertices eine Teilmenge der Eingabe sind: Jeder extreme Punkt, der «herausragt», erscheint auf der Hülle, und jeder Punkt, der als konvexe Kombination anderer schreibbar ist, liegt strikt innen oder auf einer Kante. Andrews monotone Kette (auch monotonen Ketten-Scan genannt) berechnet diesen Rand in O(n log n) Zeit, dominiert durch das Sortieren.

Nach dem Sortieren nach steigendem x (und nach y bei x-Gleichstand) läuft der Algorithmus von links nach rechts für die untere Hülle und hält stets eine strikte Linksdrehung an den letzten drei Stack-Vertices; dann läuft er von rechts nach links für die obere Hülle mit demselben Drehtest. Das Zusammenfügen beider Ketten ohne Duplizieren der gemeinsamen linkesten und rechtesten Endpunkte ergibt die volle Hülle gegen den Uhrzeigersinn, beginnend am linkesten (dann untersten) Extrem. Ein nicht-strikter Drehtest (Kreuzprodukt kleiner oder gleich null) entfernt kollineare Zwischenpunkte, sodass jede Kante maximal ist.

Entartete Mengen werden sauber behandelt: ein einziger eindeutiger Punkt liefert eine Ein-Vertex-Hülle; zwei verschiedene Punkte ein Zwei-Vertex-Segment; drei oder mehr kollineare nur die beiden Extreme. Dieses Verhalten entspricht den Lehrbuchdefinitionen der Extrempunkt-Hülle und hält nachgelagerte Polygonwerkzeuge frei von Nullflächen-«Dellen» durch Mittelkanten-Proben.

Eingabevertrag, Koordinatenmodi und Antwortfelder

Jeder Satz darf {x, y} für planare Arbeit, {lat, lon} für geografische Proben oder ein Zwei-Zahlen-Array sein. Im Auto-Modus wählen Lat/Lon-Schlüssel die geografische Etikettierung; x/y die planare. Der Geo-Modus prüft Breite in [−90, 90] und Länge in [−180, 180] und führt die Hülle weiterhin in der Lon–Lat-Ebene aus (x = longitude, y = latitude).

Optionale precision (0–15, Standard 10) setzt die Dezimalstellen der zurückgegebenen Koordinaten. Der Hüllenring ist offen: der erste Vertex wird am Ende nicht wiederholt. Kombinieren Sie diesen Endpunkt mit Flächen- oder Umfangsrechnern erst, wenn Sie einen geordneten Ring haben; die Hüllenausgabe ist bereits geordnet und bereit für diese Werkzeuge, wenn Sie die Hüllmetriken einer Punktwolke statt eines handdigitalisierten Polygons brauchen.

Wo ein konvexer Umriss hilft

Karten- und Logistikteams berechnen die konvexe Hülle von Lieferstopps, Asset-Pings oder Vermessungsmarken, um einen einfachen Außenrand ohne manuelles Digitalisieren zu zeichnen. Spiele- und CAD-Pipelines verkleinern Kollisionsproxys oder UI-Auswahlboxen auf die Hülle von Mesh- oder Sprite-Vertices, damit Überlappungstests günstig bleiben. Data-Science-Notebooks nutzen die Hülle als robusten Außenkontur für Streudiagramme und Anomalieprüfung, wenn eine Bounding Box zu lose und eine konkave Alpha-Form zu schwer ist.

Unterrichts- und Wettbewerbsplattformen brauchen ein deterministisches Orakel für Übungen «listen Sie die Extremepunkte der Reihe nach»; eine reine Parse-Fähigkeit liefert byte-stabile Koordinaten bei fester Genauigkeit, damit Bewerter nicht an Gleitkommarauschen scheitern. Fehlgeschlagene Validierung wird nicht abgerechnet. Halten Sie Wolken unter der Zehntausend-Punkte-Grenze, pinnen Sie Hüllenvertices in Tests, und Sie erhalten reproduzierbare Hüllen für GIS-ETL, Edge-Worker und Hausaufgaben, ohne eine eigene vollständige Geometriebibliothek aufzustellen.