Gibt es einen effizienten Algorithmus zur Erzeugung einer konkaven 2D-Hülle?
Mit einer Menge von (2D) Punkten aus einer GIS-Datei (einer Stadtkarte) muss ich das Polygon generieren, das die Kontur für diese Karte (deren Rand) definiert. Seine Eingabeparameter wären die festgelegten Punkte und eine 'maximale Kantenlänge'. Es würde dann das entsprechende (wahrscheinlich nicht konvexe) Polygon ausgeben.
Die beste Lösung, die ich bisher gefunden habe, war, die Delaunay-Dreiecke zu erzeugen und dann die äußeren Kanten zu entfernen, die länger sind als die maximale Kantenlänge. Nachdem alle Außenkanten kürzer sind, entferne ich einfach die Innenkanten und bekomme das gewünschte Polygon. Das Problem ist, das ist sehr zeitaufwändig und ich frage mich, ob es einen besseren Weg gibt.
Einer der ehemaligen Studenten in unserem Labor verwendete einige anwendbare Techniken für seine Doktorarbeit. Ich glaube, dass eine von ihnen "Alpha-Formen" genannt wird und im folgenden Artikel referenziert wird:
http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf
Dieses Papier enthält einige weitere Hinweise, denen Sie folgen können.
Die Antwort mag für jemanden noch interessant sein: Man kann eine Variation des Marschquadratalgorithmus anwenden, die (1) innerhalb der konkaven Hülle angewendet wird, und (2) dann auf (zB 3) verschiedene Skalen das hängt von der durchschnittlichen Punktdichte ab. Die Skalen müssen ein Vielfaches von einander sein, z. B. erstellen Sie ein Raster, das Sie für eine effiziente Probenahme verwenden können. Dies ermöglicht das schnelle Auffinden leerer Samples = Quadrate, Samples, die sich vollständig in einem "Cluster/Cloud" von Punkten befinden, und solche, die dazwischen liegen. Die letztere Kategorie kann dann verwendet werden, um die Poly-Linie, die einen Teil der konkaven Hülle darstellt, leicht zu bestimmen.
Bei diesem Ansatz ist alles linear, es wird keine Triangulation benötigt, es werden keine Alpha-Formen verwendet und es unterscheidet sich von dem hier beschriebenen kommerziellen/patentierten Angebot ( http://www.concavehull.com/ ).
Die Jungs hier behaupten, einen k nächsten Nachbarn-Ansatz entwickelt zu haben, um die konkave Hülle einer Menge von Punkten zu bestimmen, die sich "fast linear nach der Anzahl der Punkte" verhält. Leider scheint ihre Zeitung sehr gut bewacht zu sein und Sie müssen sie danach fragen.
Hier ist eine gute Menge an Referenzen die das Obige beinhaltet und möglicherweise dazu führen kann, dass Sie einen besseren Ansatz finden.
Das interaktive SDK von Bing Maps V8 verfügt über eine Option für die konkave Hülle innerhalb der erweiterten Formoperationen.
In ArcGIS 10.5.1 verfügt die Erweiterung 3D Analyst über ein Werkzeug für das minimale Begrenzungsvolumen mit den Geometrietypen der konkaven Hülle, Kugel, Hüllkurve oder konvexen Hülle. Es kann auf jeder Lizenzstufe verwendet werden.
Es gibt hier einen konkaven Rumpfalgorithmus: https://github.com/mapbox/concaveman
Eine einfache Lösung besteht darin, um den Rand des Polygons herumzugehen. Bei einer aktuellen Kante om der Grenzverbindungspunkte P0 und P1 ist der nächste Punkt an der Grenze P2 der Punkt mit dem kleinsten möglichen A, wobei
H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength
Dann hast du eingestellt
P0 <- P1
P1 <- P2
und wiederholen, bis Sie wieder da sind, wo Sie angefangen haben.
Dies ist immer noch O (N ^ 2), also möchten Sie Ihre Punkteliste ein wenig sortieren. Sie können die Menge der Punkte einschränken, die Sie bei jeder Iteration berücksichtigen müssen, wenn Sie Punkte nach ihrer Ausrichtung vom Schwerpunkt der Stadt sortieren.
Mit diesem Plug-In können Sie dies in QGIS tun; https://github.com/detlevn/QGIS-ConcaveHull-Plugin
Je nachdem, wie Sie es benötigen, um mit Ihren Daten zu interagieren, lohnt es sich vielleicht, herauszufinden, wie es hier gemacht wurde.
Gute Frage! Ich habe das noch nicht ausprobiert, aber mein erster Schuss wäre diese iterative Methode:
- Erstellen Sie eine Menge N ("nicht enthalten") und fügen Sie alle Punkte in Ihrer Gruppe zu N hinzu.
- Wählen Sie zufällig 3 Punkte von N aus, um ein anfängliches Polygon P zu bilden. Entfernen Sie sie von N.
- Verwenden Sie einen Punkt-in-Polygon-Algorithmus und sehen Sie sich die Punkte in N an. Wenn Sie nun jeden Punkt in N von P enthalten, entfernen Sie ihn von N. Sobald Sie einen Punkt in N gefunden haben, der noch steht nicht in P enthalten, fahren Sie mit Schritt 4 fort. Wenn N leer wird, sind Sie fertig.
- Nennen Sie den gefundenen Punkt A. Suchen Sie die Linie in P, die A am nächsten liegt, und fügen Sie A in der Mitte hinzu.
- Gehen Sie zurück zu Schritt 3
Ich denke, es würde funktionieren, solange es gut genug ist - eine gute Heuristik für die ersten 3 Punkte könnte hilfreich sein.
Viel Glück!
PostGIS beginnt mit einer konvexen Referenz und beginnt mit einem Convexhull.
Eine schnelle Annäherung (auch nützlich für konvexe Hüllen) ist das Finden der Nord- und Südgrenze für jedes kleine Element von Ost nach West.
Erstellen Sie je nach gewünschtem Detail ein Array mit oberen/unteren Grenzen mit fester Größe . Berechnen Sie für jeden Punkt, in welcher E-W-Spalte es sich befindet, und aktualisieren Sie dann die oberen/unteren Grenzen für diese Spalte. Nachdem Sie alle Punkte bearbeitet haben, können Sie die oberen/unteren Punkte der fehlenden Spalten interpolieren.
Es lohnt sich, vorab eine kurze Überprüfung auf sehr lange, dünne Formen durchzuführen und zu entscheiden, ob bin NS oder Ew.