Mehr

Was sind Definition, Algorithmen und praktische Lösungen für den konkaven Rumpf?


Konvexer Rumpf

Eine konvexe Hülle einer Form ist definiert als:

In der Mathematik ist die konvexe Hülle oder konvexe Hülle für eine Menge von Punkten X in einem reellen Vektorraum V die minimale konvexe Menge, die X enthält (Wikipedia)

Wikipedia visualisiert es schön mit einer Gummiband-Analogie, und es gibt einige gute Algorithmen, um es zu berechnen.

Konkaver Rumpf

Eine konkave Hülle wird mit der roten Linie im Bild unten visualisiert (die blaue Linie visualisiert die konvexe Hülle). Intuitiv ist es ein Polygon, das alle Punkte umfasst, aber im Vergleich zur konvexen Hülle weniger (minimal?) Fläche hat. Als Ergebnis ist die Begrenzungslänge des Polygons länger.

Ein konkaver Rumpf kann die Lösung für einige reale Probleme sein (z. B. das Finden der vernünftigen Grenze einer Stadt).

Ich habe es versäumt, eine geeignete Definition, einen Algorithmus und eine praktische Lösung für den Begriff eines konkaven Rumpfes zu finden. Das Grass-Wiki enthält einige Beschreibungen und Bilder, und es gibt eine kommerzielle Lösung in concavehull.com.

Irgendwelche Ideen, Algorithmen und Links?


Wie scw betont, möchten Sie eine Implementierung von α-Formen.

Alpha-Formen können als Verallgemeinerung der konvexen Hülle angesehen werden. Sie wurden erstmals 1981 beschrieben in:

Edelsbrunner, H.; Kirkpatrick, D.; Seidel, R.; , "On the shape of a set of points in the plane", Information Theory, IEEE Transactions on, Bd. 29, Nr. 4, S. 551-559, Juli 1983

Für die Umgebungen, an denen Sie interessiert sind, gibt es Open-Source-Implementierungen:

PostGIS

Wenn Sie den PostGIS-Stack verwenden, stellt die optionale Driving Distance-Erweiterung von pgRouting eine Alpha-Shape-Implementierung bereit. Ich bin mir jedoch nicht sicher, ob Sie den Alpha-Parameter ändern können.

Die Verwendung ist unten:

SELECT the_geom AS alpha_shape FROM points_as_polygon( 'SELECT id, ST_X(your_geom) AS x, ST_Y(your_geom) AS y FROM your_table');

Python

Es gibt wahrscheinlich viele Python-Module, die Sie verwenden könnten. Ich habe Gutes über CGAL gehört, eine C++-Bibliothek für rechnerische Geometrie. Python-Wrapper existieren für Teile von CGAL, einschließlich der Bereitstellung der Alpha-Shape-Implementierung von CGAL für Python.

Beachten Sie, dass Teile von CGAL unter der QPL lizenziert sind. Wenn Sie also Ihr Programm, das mit CGAL verlinkt ist, vertreiben, müssen Sie es möglicherweise unter der QPL veröffentlichen. Es ist in Ordnung, Ihren Code proprietär zu halten, wenn Sie Ihren Programmcode oder Ihre Binärdateien nicht weitergeben.


Hier ist, was Sie suchen.

Sie können das Programm herunterladen und testen: (in Java, unter GPL-Lizenz)

Das Papier, das den Algorithmus vorstellt, ist da:

Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008)Effiziente Erzeugung einfacher Polygone zur Charakterisierung der Form einer Menge von Punkten in der Ebene. Mustererkennung v41, 3224-3236


Dies scheint eine spezifische Anwendung von Alpha-Formen zu sein, die nach meiner Lektüre eine allgemeinere Form dieses Problems sind. R verfügt über das Alphahull-Modul, das eine hervorragende Dokumentation zur Berechnung von Alpha-Formen bietet. Überprüfen Sie auch diesen detaillierten Hintergrund zu Alpha-Formen. Wenn Sie nur konvexe/konkave Hüllen berechnen möchten, sehen Sie sich lasboundary an, ein Teil von lastools, es skaliert gut und kann Millionen von Eingabepunkten verarbeiten.

Schließlich machte diese interessante Anwendung von Alpha-Formen von Flickr vor einiger Zeit die Runde und zeigte ihren Nutzen für die Aggregation von benutzergenerierten Punktinhalten:


Es gibt eine Implementierung von ST_ConcaveHull im PostGIS-Trunk. http://postgis.net/docs/ST_ConcaveHull.html


Ich habe ein hocheffizientes Tool namens . erstellt lasboundary (1,2), das eine konkave Hülle für LIDAR im LAS/LAZ/SHP/ASCII-Format berechnet und das Ergebnis als Vektorbegrenzungspolygon im ESRI-Shapefile-Format oder als georeferenzierte KML-Datei speichert.

Hier ein Beispiellauf:

C:lastoolsin>lasboundary -i SerpentMound.las -o SerpentMound_boundary.shp Lesen von 3265110 Punkten und Berechnen der konvexen Hülle für 3265110 Punkte, die nach innen zur konkaven Hülle hin wachsen (mit Konkavität = 50) Ausgabe der konkaven Hülle Konkave Hülle hat 1639 Punkte

Einige Ergebnisbilder gibt es hier.


Hier ist eine R-Funktion, die das Alpha-Hull-Modell implementiert. Die Ausgabe ist ein sp-Polygonobjekt. Sehen Sie sich das Beispiel in der Kopfzeile an. Es erfordert die Pakete sp, alphahull und maptools.

**Update (15.01.2018) Es gab zahlreiche Änderungen an den resultierenden Objekten, die vom alphahull-Paket erzeugt wurden. Daher musste ich die Funktion neu schreiben. Ich habe dem SpatialEco-Paket eine convexHull-Funktion hinzugefügt. Aufgrund von Lizenzbeschränkungen im alphahull-Paket ist diese Funktion jedoch nur in der Entwicklungsversion auf GitHub verfügbar. Die Entwicklungsversion kann installiert werden mit:

Bibliothek(devtools) install_github("jeffreyevans/spatialEco")

Hier ist ein Beispiel für die Verwendung der Funktionen

Bibliothek(sp) Bibliothek(spatialEco) Daten(Maas) Koordinaten(Maas) = ​​~x+y a <- convexHull(mause, alpha=10000) Plot(a) Punkte(Maas, pch=19)

Konvertieren Sie den resultierenden SpatialLinesDataFrame in SpatialPolygonsDataFrame

Bibliothek(sf) a <- sf::st_as_sf(a) a <- sf::st_polygonize(a) class( a <- as(a, "Spatial") ) plot(a)

Testen Sie mehrere Alphawerte

par(mfcol=c(2,2)) for (a in c(500, 1500, 5000, 100000)) { ch <-convexHull(meuse, alpha = a) plot(ch) points(meuse, pch=19) title(paste0("alpha=", a))}


Über die R-Implementierung von Alpha-Shapes gibt es einen Artikel über "Konvertieren von Alpha-Shapes in SP-Objekte"

Es basiert auf alphahull, sp und spgrass6 http://casoilresource.lawr.ucdavis.edu/drupal/node/919


JTS (https://github.com/locationtech/jts) bietet eine Convex Hull-Implementierung. Martin Davies erwähnte auch, dass ein Alpha-Shape-Algorithmus in Arbeit ist, sodass Sie vielleicht das SVN-Repository überprüfen möchten, um zu sehen, ob es noch vorhanden ist, wenn Sie dies wünschen.


Apropos JTS, Sie können Geoscript verwenden, um die JTS-Bibliothek zu manipulieren. http://geoscriptblog.blogspot.com/2010/06/unwrapped-jts-with-python.html für einen Artikel über konvexe Hülle. GeoScript-Implementierungen sind in JavaScript, Python, Scala und Groovy verfügbar. Die offizielle Website: http://geoscript.org


Hier ist ein in C geschriebenes Programm, das konvexe Hüllen, Alpha-Formen, Delauney-Triangulationen und Voronoi-Volumen berechnet:

  • Rumpf - Ken Clarkson (2002)

Ein weiterer konvexer Hüllen-Algorithmus mit C- und Java-Implementierungen ist hier:

  • Konvexer Rumpf (2D) - Computergeometrie in C, Joseph O'Rourke (1998)

Um zu früheren Antworten für diesen Beitrag hinzuzufügen, verfügt zumindest QGIS 2.6 über einen konkaven Rumpfalgorithmus

Parameter
Eingabepunktebene [Vektor: Punkt]
Parameterbeschreibung hier einfügen

Schwellenwert (0-1, wobei 1 gleichbedeutend mit konvexem Rumpf ist) [Zahl]
Parameterbeschreibung hier einfügen
Standard: 0,3

Löcher zulassen [boolean]
Parameterbeschreibung hier einfügen
Standard: Wahr

Splitten Sie Multipart-Geometrie in Singlepart-Geometrien [boolean]
Standard: Falsch

Ausgänge Konkave Hülle [Vektor]
Ausgabebeschreibung hier einfügen

Konsolennutzung
Processing.runalg('qgis:concavehull', Eingabe, Alpha, Löcher, no_multigeometry, Ausgabe)

Außerdem verfügt Esri über ein Tool zur minimalen Begrenzungsgeometrie (Datenverwaltung)

Dadurch können Sie den Geometrietyp auswählen, der eine konvexe Hülle enthält


Es ist ein neues Addon für GRASS GIS 7 verfügbar: v.concave.hull. Siehe auch http://grasswiki.osgeo.org/wiki/Create_concave_hull


Um bei der "richtigen Definition" Ihrer Frage zu helfen; Sie haben sich vielleicht https://en.wikipedia.org/wiki/Convex_hull angesehen und eine "richtige" Definition erhalten, die jedoch fehlt, daher ist vielleicht eine "nützlichere" Definition:

Zum jeder Punkt innerhalb einer konvexen Hülle, eine gerade Linie zu irgendein Punkt, der sich nicht innerhalb des Rumpfes befindet, schneidet den Rumpf nur einmal.

Dies ist nützlich, da Sie bei einem gegebenen Punkt eine Linie durch ihn konstruieren und auf diese konstruierte Linie testen können, die Segmente des Rumpfes schneidet.

  • Kein Schnittpunkt der Punkt liegt nicht im Rumpf.
  • Ein Schnittpunkt ist der Punkt auf dem Rumpf.
  • Zwei Schnittpunkte, der Punkt liegt innerhalb der Hülle
  • Eine gerade Linie kann eine konvexe Hülle nicht mehr als zweimal schneiden