Umfang einer konvexen Hülle berechnen

Er gibt sowohl den Umfang als auch die Eckpunkte der Hülle zurück, sodass Sie das Ergebnis prüfen, zeichnen oder weiterverarbeiten können. Doppelte und innen liegende Punkte vergrößern den Wert nicht. Die Berechnung ist deterministisch, benötigt keinen Netzwerkzugriff und verarbeitet bis zu 100,000 Punkte pro Anfrage.

Geben Sie kartesische Punkte in einem einheitlichen System an

Übermitteln Sie die Punkte als Datensätze mit endlichen numerischen Koordinaten x und y. Alle Punkte müssen dasselbe kartesische Koordinatensystem und dieselbe Einheit verwenden. Liegen die Koordinaten in Metern vor, wird auch der Umfang in Metern ausgegeben; bei Pixeln lautet die Ergebniseinheit Pixel. Der Rechner projiziert weder Breiten- und Längengrade noch berücksichtigt er die Erdkrümmung. Wandeln Sie geografische Daten deshalb zunächst in ein geeignetes projiziertes Koordinatensystem um, wenn Sie eine physische Entfernung benötigen. Die Eingabereihenfolge spielt keine Rolle, da der Algorithmus die Koordinaten vor dem Aufbau der Begrenzung sortiert. Wiederholte Koordinaten sind zulässig und werden geometrisch entfernt; die Antwort nennt dennoch sowohl die ursprüngliche als auch die eindeutige Punktzahl. Mindestens ein Punkt ist erforderlich, höchstens 100,000 Datensätze sind erlaubt. Durch Beibehaltung der ursprünglichen Genauigkeit vermeiden Sie vorzeitiges Runden. Die Hülle beginnt am lexikografisch kleinsten Randpunkt und verläuft gegen den Uhrzeigersinn, sodass ihre Darstellung stabil und reproduzierbar ist.

So werden Begrenzung und Umfang ermittelt

Der Rechner verwendet Andrews Monotone-Chain-Verfahren. Nach Sortierung und Deduplizierung baut er eine untere und eine obere Kette auf. Ein Orientierungstest mit dem Kreuzprodukt entfernt den mittleren Punkt, sobald drei aufeinanderfolgende Kandidaten keine Linksdrehung bilden. Dadurch entfallen streng innen liegende Punkte ebenso wie Zwischenpunkte auf einer geraden Randkante; erhalten bleiben nur die zur Beschreibung der Kante erforderlichen Extrempunkte. Anschließend werden beide Ketten verbunden, ohne ihre Endpunkte doppelt aufzunehmen. Für den Umfang wird die euklidische Entfernung von jedem Eckpunkt zum nächsten addiert, einschließlich der schließenden Kante vom letzten zurück zum ersten. Die Sortierung bestimmt die Laufzeit und führt zu einer Zeitkomplexität von O(n log n); der anschließende Aufbau ist linear. Bei genau einem eindeutigen Punkt beträgt der Umfang null. Bei zwei eindeutigen Punkten oder einer vollständig kollinearen Menge enthält die Hülle die beiden äußersten Punkte. Nach der Konvention einer geschlossenen Begrenzung wird die Strecke in beiden Richtungen gezählt, sodass das Doppelte des Endpunktabstands entsteht.

Lesen und verwenden Sie das Ergebnis richtig

Das Feld perimeter enthält die gesamte Randlänge in derselben Einheit wie die Eingabekoordinaten. Das Array hull führt die beibehaltenen Randpunkte in Umlaufrichtung auf, ohne den ersten Punkt am Ende zu wiederholen. Zusätzlich enthält die Antwort input_points, unique_points und hull_points. Diese Angaben verdeutlichen, weshalb innere, wiederholte oder kollineare Punkte nicht in der Begrenzung erscheinen. Zum Zeichnen des Polygons verbinden Sie benachbarte zurückgegebene Punkte und schließen den letzten ausdrücklich mit dem ersten. Da JavaScript-Gleitkommaarithmetik eingesetzt wird, können irrationale Entfernungen die übliche kleine binäre Näherung enthalten; runden Sie erst bei der Darstellung. Das Werkzeug eignet sich für Lagepläne, Bildkoordinaten, lokale Ingenieurraster und projizierte Kartendaten. Es berechnet keinen sphärischen oder ellipsoidischen geodätischen Umfang, korrigiert keine falschen Koordinatenbezüge und bewahrt kollineare Punkte nicht allein zur Anzeige. API-Anfragen kosten $0.002; die Browserausführung verwendet dieselbe reine Berechnungslogik und liefert daher kanalübergreifend konsistente Ergebnisse.