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 realen Vektorraum V die minimale konvexe Menge, die X enthält ( Wikipedia )

Wikipedia visualisiert es mit einer Gummibandanalogie und es gibt einige gute Algorithmen, um es zu berechnen .

Konkaver Rumpf

Ein konkaver Rumpf wird mit der roten Linie im Bild unten dargestellt (die blaue Linie zeigt den konvexen Rumpf an). Intuitiv ist es ein Polygon, das alle Punkte umfasst, aber im Vergleich zur konvexen Hülle weniger (minimale?) Fläche hat. Infolgedessen ist die Grenzlänge des Polygons länger.

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

Es ist mir nicht gelungen, eine geeignete Definition, einen Algorithmus und eine praktische Lösung für den Begriff der konkaven Hülle zu finden. Das Grass-Wiki enthält einige Beschreibungen und Bilder . Unter concavehull.com gibt es eine kommerzielle Lösung .

Irgendwelche Ideen, Algorithmen und Links?

Wie scw hervorhebt , 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 .; "Über die Form einer Menge von Punkten in der Ebene", Information Theory, IEEE Transactions on, Bd. 29, Nr. 4, S. 551-559, Juli 1983

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

PostGIS

Wenn Sie den PostGIS - Stack verwenden, pgRouting ‚s optional Driving Entfernung Erweiterung setzt eine Alpha - Form - Implementierung. Ich bin mir jedoch nicht sicher, ob Sie den Alpha-Parameter variieren können.

Verbrauch 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 gute Dinge über CGAL gehört , eine C ++ - Bibliothek für rechnergestützte Geometrie. Es gibt Python-Wrapper 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 mit CGAL verknüpftes Programm vertreiben, müssen Sie es möglicherweise unter der QPL veröffentlichen. Es ist in Ordnung, Ihren Code geschützt zu lassen, 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 mit dem Algorithmus ist da:

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

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

Schließlich hat diese interessante Anwendung von Alpha-Formen von Flickr vor einiger Zeit die Runde gemacht und ihr Hilfsprogramm zum Aggregieren von benutzergenerierten Punktinhalten gezeigt:

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

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

Hier ist ein Beispiellauf:

C:\lastools\bin>lasboundary -i SerpentMound.las -o SerpentMound_boundary.shp
reading 3265110 points and computing convex hull for 3265110 points
growing inward towards concave hull (with concavity = 50)
outputting the concave hull
concave hull has 1639 points

Einige Ergebnisbilder sind hier .

Informationen zur R-Implementierung von Alpha-Shapes finden Sie in einem Artikel zum Thema "Konvertieren von Alpha-Shapes in SP-Objekte".

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

Hier ist eine R-Funktion, die das Alpha-Hull-Modell implementiert. Die Ausgabe ist ein sp-Polygon-Objekt. Bitte beachten Sie das Beispiel in der Kopfzeile. Es erfordert die Pakete sp, alphahull und maptools.

** Update (01-15-2018) Es wurden zahlreiche Änderungen an den resultierenden Objekten vorgenommen, die vom alphahull-Paket erstellt 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:

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

Hier ist ein Beispiel für die Verwendung der Funktionen

library(sp)
library(spatialEco)
data(meuse)
 coordinates(meuse) = ~x+y
a <- convexHull(meuse, alpha=100000)
  plot(a)
    points(meuse, pch=19)

Konvertieren Sie den resultierenden SpatialLinesDataFrame in SpatialPolygonsDataFrame

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

Testen Sie mehrere Alpha-Werte

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))      
   }

JTS ( http://tsusiatsoftware.net/jts/main.html ) bietet eine Convex-Hull-Implementierung. Martin Davies erwähnte auch, dass ein Alpha-Shape-Algorithmus in Arbeit ist, sodass Sie möglicherweise das SVN-Repository überprüfen möchten, um festzustellen, ob es sich noch in dem befindet, was Sie möchten.

Wenn Sie über JTS sprechen, können Sie Geoscript zum Bearbeiten der JTS-Bibliothek verwenden. 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-Triangluationen und Voronoi-Volumina berechnet:

• Rumpf - Ken Clarkson (2002)

Ein weiterer konvexer Rumpfalgorithmus mit C- und Java- Implementierungen ist hier:

• Konvexe Hülle (2D) - Computergestützte Geometrie in C , Joseph O'Rourke (1998)

Zumindest ab QGIS 2.6 gibt es einen konkaven Rumpf-Algorithmus, um die vorherigen Antworten für diesen Beitrag zu ergänzen

Parameter
Eingabepunktebene [Vektor: Punkt]
Geben Sie hier die Beschreibung des Parameters ein

Schwellenwert (0-1, wobei 1 gleichbedeutend mit der konvexen Hülle ist) [Zahl]
Parameterbeschreibung hier
einfügen Standard: 0,3

Allow holes [boolean]
Parameterbeschreibung hier
einfügen Standard: True

Mehrteilige Geometrie in Einzelteilgeometrien aufteilen [Boolescher Wert]
Standard: Falsch

Ausgänge Konkaver Rumpf [Vektor]
Geben Sie hier die Beschreibung des Ausgangs ein

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

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

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

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

Hilfe bei der "richtigen Definition" Ihrer Frage; Möglicherweise haben Sie unter https://en.wikipedia.org/wiki/Convex_hull nachgeschlagen und herausgefunden, was als "richtige" Definition angesehen werden kann, aber es fehlt. Daher ist möglicherweise eine "nützlichere" Definition:

Für jeden Punkt in einem konvexen Rumpf schneidet eine gerade Linie zu einem Punkt, der nicht im Rumpf liegt, den Rumpf nur einmal.

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

• Kein Schnittpunkt der Punkt liegt nicht im Rumpf.
• Eine Kreuzung ist der Punkt auf dem Rumpf.
• An zwei Kreuzungen liegt der Punkt innerhalb des Rumpfes
• Eine gerade Linie kann eine konvexe Hülle nicht mehr als zweimal schneiden