Näherung einer konkaven Hülle aus Koordinaten

Diese Näherung einer konkaven Hülle beginnt mit dieser verlässlichen Außengrenze und verfeinert lange Kanten mit bislang ungenutzten inneren Punkten, bis der gewünschte Schwellenwert erreicht ist oder keine gültige Einfügung mehr möglich ist. Das deterministische Ergebnis enthält die geordnete Grenze, Kantenlängen, Umfang, Fläche sowie die Anzahl der nicht verkürzbaren Kanten. So können Sie die Näherung prüfen, statt sie irrtümlich als exakte geometrische Lösung zu verstehen.

Wählen Sie Koordinaten und Schwellenwert sinnvoll

Geben Sie mindestens drei ebene Punkte als numerische x- und y-Koordinaten sowie einen positiven Schwellenwert für die Kantenlänge an. Die Koordinaten können projizierte Kartenpositionen, Zeichnungseinheiten, Messwerte oder ein anderes zweidimensionales kartesisches System darstellen. Sie müssen denselben Maßstab verwenden: Mischen Sie keine Längengrade mit Entfernungen in Metern, wenn der Schwellenwert eine physikalische Bedeutung behalten soll. Ein kleinerer Wert fordert den Algorithmus auf, den verfügbaren Punkten genauer zu folgen, während ein größerer Wert mehr von der konvexen Kontur erhält. Der Schwellenwert ist ein Ziel und keine Garantie, da eine dünn besetzte Punktmenge möglicherweise keinen sicheren inneren Punkt zum Teilen einer bestimmten Kante enthält. Doppelte Koordinaten werden ignoriert. Es müssen mindestens drei eindeutige, nicht kollineare Punkte verbleiben, weil eine Gerade kein Polygon bilden kann. Projizieren Sie Breiten- und Längengrade angemessen, bevor Sie einen als Entfernung angegebenen Schwellenwert verwenden. Das Werkzeug rechnet in der Ebene und verwendet kein kugel- oder ellipsoidförmiges Erdmodell. Beginnen Sie mit einem Wert nahe dem Abstand, den Sie als bedeutsame Lücke ansehen, und vergleichen Sie anschließend die zurückgegebene Grenze mit den ursprünglichen Punkten.

So funktioniert die Verfeinerung der Grenze

Der Algorithmus berechnet zunächst mit dem Monotone-Chain-Verfahren eine deterministische konvexe Hülle. Danach untersucht er alle Grenzkanten oberhalb des angegebenen Schwellenwerts, beginnend mit der längsten. Für jede Kante sucht er ungenutzte Punkte, die innerhalb des aktuellen Polygons liegen und die Kante durch zwei kürzere Abschnitte ersetzen können, ohne einen anderen Grenzabschnitt zu schneiden. Gewählt wird der Kandidat, dessen längerer Ersatzabschnitt am kürzesten ist. Bei Gleichstand entscheiden stabil die Gesamtlänge und anschließend die ursprüngliche Eingabereihenfolge. Nach einer Einfügung beginnt die Auswahl erneut, da sich das Polygon verändert hat. Die Verfeinerung endet, sobald alle Kanten das Ziel erfüllen oder kein verbleibender Punkt eine lange Kante sicher verbessern kann. Diese Konstruktion bevorzugt ein vorhersehbares, nachvollziehbares Ergebnis und behauptet nicht, sämtliche konkurrierenden Definitionen einer exakten konkaven Hülle zu lösen. Sie erfindet keine Eckpunkte, verschiebt keine Koordinaten, nutzt keine Zufallsstichprobe und ruft keinen entfernten Dienst auf. Die zurückgegebene Hülle ist eine offene, geordnete Liste von Eckpunkten; der letzte Punkt ist mit dem ersten verbunden. Die Kantenlängen folgen derselben zyklischen Reihenfolge.

Prüfen Sie die Grenzen vor der weiteren Nutzung

Beachten Sie unresolved_long_edges immer dann, wenn der Schwellenwert betrieblich wichtig ist. Der Wert null bedeutet, dass jede zurückgegebene Kante das Ziel erfüllt. Ein positiver Wert zeigt, dass die vorhandene Punktgeometrie den Wert nicht erreichen konnte, ohne eine Kreuzung, eine Bewegung nach außen oder einen Ersatz zu erzeugen, der die Kante nicht verkürzt. Das ist eine nützliche Angabe und kein verborgener Fehler. Die Näherung kann außerdem von Alpha-Shapes, Hüllen auf Grundlage nächster Nachbarn, Triangulationsfiltern oder speziellen Küstenlinienverfahren abweichen. Vergleichen Sie Methoden, wenn die Topologie rechtliche, wissenschaftliche oder sicherheitsbezogene Folgen hat. Fläche und Umfang gehören zum zurückgegebenen ebenen Polygon und verwenden das von Ihnen gelieferte Koordinatensystem; sie sind keine geodätischen Messungen. Zeichnen Sie die geordnete Hülle über den Quellpunkten, um zu prüfen, ob der Wert die gewünschten Gruppen und Einbuchtungen erfasst. Bleibt die Grenze zu weit, ergänzen Sie repräsentative Punkte oder senken Sie den Schwellenwert; wird sie zu detailliert, erhöhen Sie ihn. Die Fähigkeit akzeptiert höchstens 500 Elemente, damit wiederholte Schnittprüfungen begrenzt und sowohl im Browser als auch bei deterministischer API-Automatisierung praktikabel bleiben.