Was sind Definitionen, Algorithmen und praktische Lösungen für konkave Hüllen? [geschlossen]

116

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

Bildbeschreibung hier eingeben

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?

Adam Matan
quelle
In welchem ​​Kontext möchten Sie konkave Rümpfe / Alpha-Formen erzeugen? In PostGIS, ArcMap, einer Webkarte, Ihrer eigenen Software?
Markieren Sie den
Sowohl PostGIS als auch meine eigenen Python-Skripte.
Adam Matan
Gibt es eine C ++ Linux-kompatible Version der Implementierung des Konkavhüllen-Algorithmus?
Sylv255
Wenn Sie eine neue Frage haben, fragen Sie es bitte durch Klicken Frage stellen Taste. Fügen Sie einen Link zu dieser Frage hinzu, wenn dies zur Bereitstellung des Kontexts beiträgt. - Aus der Bewertung
Evil Genius
Computational Geometry Algorithms Library (CGAL) ist eine C ++ - Bibliothek mit Alpha-Formen. Es hat einen Linux-Download und ist als GPL / LGPL für Version> = 4.0 lizenziert.
Klewis

Antworten:

57

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.

fmark
quelle
Ich kann die Python-Wrapper von CGAL nicht zum Kompilieren bringen - anscheinend wurden diese seit einiger Zeit nicht mehr unterstützt und funktionieren nicht mehr mit einer neueren Version von CGAL.
Conradlee
2
@ fmark: Der zweite Link, den Sie gepostet haben, scheint tot zu sein.
Radek
1
@ fmark PostGIS-Links scheinen tot zu sein ..
radek
29

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:

Alpha Rumpf von Texas von flickr

scw
quelle
1
OMG die Quelle ist in FORTRAN geschrieben :-)
Adam Matan
Es gibt das Clustr-Paket, das in C ++ geschrieben ist, falls es Ihnen besser passt. Aber seien Sie vorsichtig mit der Lizenzierung auf CGAL: github.com/straup/Clustr
scw
2
Schönes Beispiel aus der Praxis.
DavidF
20

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

Nicklas Avén
quelle
1
Ich denke, dies erscheint zuerst in der Version 2.0 von PostGis
Adrian
19

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 .

Martin Isenburg
quelle
10

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

ThomasG77
quelle
10

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

verschiedene vollständige Alpha-Parameter

Jeffrey Evans
quelle
+1 Können Sie erklären, wie sich dies vom Alpha Shapes-Paket unterscheidet ?
whuber
3
Die Ausgabe des Alphahull-Objekts wird als Matrix gespeichert und muss in ein verwendbares sp-Objekt umgewandelt werden. Ich würde dies als "Hilfsfunktion" betrachten, um ein Polygon zu erstellen, das in ein GIS-Format exportiert werden kann. Diese Funktion erstellt mithilfe des Alphahull-Pakets das Rumpfmatrixobjekt, erstellt ein sp-Objekt und zerlegt dann den Polygonschlitz, sodass es sich um ein einteiliges Polygon-Datenrahmenobjekt handelt. In der Pakethilfe wird nichts angezeigt, es kann jedoch vorkommen, dass ein systemeigener Zwang auf ein SP-Klassenobjekt angewendet wird, das mir nicht bekannt ist. Wenn dies der Fall ist, teilen Sie mir dies bitte mit, damit ich diese Funktion deaktivieren kann.
Jeffrey Evans
Was ist die Programmiersprache?
Adam Matan
Danke @JeffreyEvans Ich habe es geschafft, das zum Laufen zu bringen. Könnten Sie möglicherweise die Parameter erklären? Ich habe mir das verlinkte jstatsoft-Papier angesehen, aber es ist ziemlich undurchdringlich.
Geotheorie
9

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.

Ian Turton
quelle
Soweit ich das beurteilen kann, gibt es ab Juni 2012 noch keine Implementierung für konkave Rumpf- / Alpha-Formen.
blah238
Immer noch nichts im Mai 2013.
Crescent Fresh
Ist JTS am Leben? Letzte Version ist vom 19. Dezember 2006. vividsolutions.com/jts/JTSHome.htm
angelcervera
Versuchen Sie den Link in der Antwort
Ian Turton
JTS ist jetzt auf Github und nähert sich Version 1.15: github.com/locationtech/jts Obwohl, soweit ich das beurteilen kann, scheint es immer noch keine Alpha Shapes-Implementierung zu geben.
Colin Woodbury
7

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:

blah238
quelle
7

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

Bildbeschreibung hier eingeben

Whyzar
quelle
3

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
user29206
quelle
2
der op fragt nach konkaven und nicht nach konvexen
rümpfen