Gibt es einen effizienten Algorithmus, um einen 2D-konkaven Rumpf zu generieren?
https://stackoverflow.com/questions/83593
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
eine Reihe von (2D) Punkten aus einer GIS-Datei (Stadtplan) Mit, ich brauche das Polygon zu erzeugen, die die ‚Kontur‘ definiert für diese Karte (seine Grenze). Seine Eingangsparameter wären die Punkte gesetzt und eine ‚maximale Kantenlänge‘. Es wäre dann geben die entsprechenden (wahrscheinlich nicht-konvex) Polygon.
Die beste Lösung, die ich bisher gefunden war, die Delaunay Dreiecken zu erzeugen und dann die äußeren Kanten entfernen, die länger als die maximale Kantenlänge sind. Nachdem alle Außenkanten als die kürzer sind, entferne ich einfach die inneren Kanten und bekommen das Polygon ich will. Das Problem ist, das ist sehr zeitaufwendig und ich frage mich, ob es ein besserer Weg.
Andere Tipps
Einer der ehemaligen Studenten in unserem Labor verwendet, um einige anwendbaren Techniken für seine Doktorarbeit. Ich glaube, einer von ihnen ist „alpha Formen“ genannt und wird im folgenden Papier verwiesen:
http://www.cis.rit.edu/ Menschen / Fakultät / Kerekes / pdfs / AIPR_2007_Gurram.pdf
Das Papier einige weitere Hinweise gibt können Sie folgen.
Die Jungs hier Anspruch ak nächsten Nachbarn Ansatz entwickelt haben, um festzustellen, die konkave Hülle einer Menge von Punkten, die „nahezu linear von der Anzahl der Punkte“ verhält. Leider ihr Papier scheint sehr gut bewacht werden, und Sie werden sie für sie.
Hier ist ein guter Satz von Referenzen , dass die oben enthält und Sie könnten einen besseren Ansatz.
finden führenDie Antwort kann noch für jemanden anderen interessant sein: Man kann eine Variation des Marsch-Square-Algorithmus anwenden , angewandt (1) innerhalb des konkaven Rumpfes, und (2) dann auf (zB 3) verschiedene Waage , dass mein auf der durchschnittlichen Dichte von Punkten ab. Die Waagen müssen int Vielfache voneinander sein, wie Sie ein Gitter bauen Sie für eine effiziente Probenahme verwenden können. Dies ermöglicht es, schnell leer Proben = Quadrate, Proben, die vollständig innerhalb einer „cluster / Wolke“ von Punkten, und diejenigen, die in zwischen finden. Letztere Kategorie dann verwendet werden, kann leicht die poly-line zu bestimmen, die einen Teil des konkaven Rumpf darstellt.
Alles ist linear in diesem Ansatz keine Triangulation benötigt wird, ist es nicht alpha Formen nicht verwendet und es unterscheidet sich von der kommerziellen / patentierte Angebot wie hier beschrieben ( http://www.concavehull.com/ )
Eine einfache Lösung ist um den Rand des Polygons zu gehen. einen aktuellen Rand om die Grenze gegeben Punkte P0 und P1, der nächste Punkt auf der Grenze P2 wird der Punkt mit dem kleinstmöglichen A, wobei
VerbindungsH01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength
Dann Sie
P0 <- P1
P1 <- P2
und wiederholen, bis Sie wieder bekommen, wo Sie begonnen haben.
Dies ist immer noch O (N ^ 2), so wollen Sie Ihre Punktliste ein wenig sortieren. Sie können die Menge der Punkte begrenzen Sie bei jeder Iteration beachten müssen, wenn Sie sortieren auf Punkte, sagen, ihre Lager von der Stadt Schwerpunkt.
Gute Frage! Ich habe das gar 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 Ihrem Set zu N.
- Pick 3 Punkte von N zufällig ein anfängliches Polygon P. sie von N entfernen zu bilden.
- Verwenden Sie einige Point-in-Polygon-Algorithmus und für jeden an den Punkten in N. aussehen Punkt in N, wenn sie jetzt von P enthalten ist, entfernen Sie es von N. Sobald Sie einen Punkt in N finden, die noch nicht in P enthalten ist, weiter zu Schritt 4. wenn N leer wird, du bist fertig.
- Rufen Sie den Punkt, den Sie A. die Zeile in P am nächsten A finden gefunden, und fügen Sie A in der Mitte.
- Gehen Sie zurück zu Schritt 3
ich denke, es würde funktionieren, solange es gut genug führt -. Eine gute Heuristik für Ihre ersten 3 Punkte könnte helfen
Viel Glück!
Sie können es in QGIS tun mit diesem Plug-in; https://github.com/detlevn/QGIS-ConcaveHull-Plugin
Je nachdem, wie Sie es brauchen mit Ihren Daten zu interagieren, wahrscheinlich lohnt sich, wie es hier geschehen ist.
Die Bing Maps V8 interaktive SDK hat eine konkave Rumpf Option innerhalb der erweiterten Form Operationen.
in ArcGIS 10.5.1, die 3D-Analyst-Erweiterung hat ein minimalen Bounding Volume Werkzeug mit den Geometrietypen konkaven Rumpf, Kugel, einen Umschlag oder einem konvexen Hülle. Es kann in jeder Lizenzstufe verwendet werden.
Es ist ein konkaver Rumpf Algorithmus hier: https://github.com/mapbox/concaveman
Eine schnelle Näherungslösung (auch für konvexe Hüllen) ist es, die Nord und Süd Grenzen für jedes kleine Element Ost-West zu finden.
Auf der Grundlage, wie viele Details Sie möchten, erstellen Sie eine feste Größe Array von oberen / unteren Grenzen. Für jeden Punkt berechnen, die E-W Spalte es in ist, und dann die oberen / unteren Grenzen für diese Spalte aktualisieren. Nachdem Sie alle Punkte verarbeitet können Sie die oberen / unteren Punkte für diese Spalten, die interpoliert werden vermisst.
Es lohnt sich auch eine schnelle Überprüfung vorher sehr lange dünne Formen zu tun und zu entscheiden, ob zu bin NS oder Ew.
Als wild angenommen Referenz, PostGIS beginnt mit einem Konvexe Hülle und dann Höhlen es in, können Sie es hier sehen kann.
