Que sont la définition, les algorithmes et les solutions pratiques pour une coque concave? [fermé]

116

Enveloppe convexe

Une coque convexe d'une forme est définie comme:

En mathématiques, l'enveloppe convexe ou l'enveloppe convexe d'un ensemble de points X dans un espace vectoriel réel V est l'ensemble convexe minimal contenant X ( Wikipedia )

Wikipedia le visualise bien en utilisant une analogie avec un élastique, et il existe de bons algorithmes pour le calculer .

Coque concave

Une coque concave est visualisée à l'aide de la ligne rouge dans l'image ci-dessous (la ligne bleue représente la coque convexe). Intuitivement, il s’agit d’un polygone qui englobe tous les points, mais a une superficie inférieure (minimale?) À celle de la coque convexe. En conséquence, la longueur de la limite du polygone est plus longue.

Une coque concave peut être la solution à certains problèmes du monde réel (par exemple, trouver la limite raisonnable d'une ville).

entrez la description de l'image ici

Je n'ai pas réussi à trouver une définition, un algorithme et une solution pratique appropriés pour la notion de coque concave. Le wiki Grass a quelques descriptions et images , et concavehull.com propose une solution commerciale .

Des idées, des algorithmes et des liens?

Adam Matan
la source
Dans quel contexte souhaitez-vous générer des coques / formes alpha concaves? Dans PostGIS, ArcMap, une carte Web, votre propre logiciel?
Mark
PostGIS et mes propres scripts Python.
Adam Matan
Existe-t-il une version compatible avec C ++ Linux de l’implémentation de l’algorithme de coque concave?
Sylv255
Si vous avez une nouvelle question, posez-la en cliquant sur le bouton Poser une question . Incluez un lien vers cette question si cela permet de fournir un contexte. - De l'avis
Evil Genius
La bibliothèque d'algorithmes de géométrie computationnelle (CGAL) est une bibliothèque C ++ avec formes alpha. Il a un téléchargement Linux et est sous licence GPL / LGPL pour la version> = 4.0.
klewis

Réponses:

57

Comme le fait remarquer scw , vous souhaitez une implémentation des formes α .

Les formes alpha peuvent être considérées comme une généralisation de la coque convexe. Ils ont été décrits pour la première fois en 1981 dans:

Edelsbrunner, H .; Kirkpatrick, D .; Seidel, R .; , "Sur la forme d'un ensemble de points dans le plan", Théorie de l'information, Transactions IEEE, vol.29, n ° 4, p. 551-559, juillet 1983.

Des implémentations open source existent pour les environnements qui vous intéressent:

PostGIS

Si vous utilisez la pile PostGIS, l' extension facultative Distance de conduite de pgRouting expose une implémentation de forme alpha. Je ne sais pas si vous pouvez modifier le paramètre alpha, cependant.

L'utilisation est ci-dessous:

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

Il y a probablement beaucoup de modules python que vous pourriez utiliser. J'ai entendu de bonnes choses à propos de CGAL , une bibliothèque de géométrie de calcul C ++. Des wrappers Python existent pour certaines parties de CGAL, notamment pour exposer l' implémentation de la forme alpha de CGAL à Python .

Sachez que certaines parties de CGAL sont sous licence QPL, ce qui signifie que si vous distribuez votre programme lié à CGAL, vous devrez peut-être le publier sous QPL. Il est bon de garder votre code propriétaire si vous ne redistribuez pas votre code de programme ou vos fichiers binaires.

fmark
la source
Je ne parviens pas à compiler les wrappers python de CGAL - il semble que ceux-ci ne soient plus pris en charge depuis longtemps et ne fonctionnent plus avec une version récente de CGAL.
conradlee
2
@fmark: Le deuxième lien que vous avez posté semble être mort.
Radek
1
@fmark Les liens PostGIS semblent être morts ..
radek
29

Cela semble être une application spécifique des formes alpha , qui sont de ma lecture une forme plus générale de ce problème. R possède le module alphahull , qui possède une excellente documentation sur le calcul des formes alpha . Vérifiez également ce fond détaillé sur les formes alpha. Si vous voulez seulement calculer des coques convexes / concaves, jetez un œil à lasboundary , une partie de lastools , elle s’adapte bien et peut gérer des millions de points d’entrée.

Enfin, cette application intéressante de formes alpha de Flickr a fait le tour il y a quelque temps, montrant son utilité pour l'agrégation de contenu en points généré par l'utilisateur:

coque alpha du texas à partir de flickr

scw
la source
1
OMG la source est écrite en FORTRAN :-)
Adam Matan
Il y a le paquetage clustr écrit en C ++ si cela vous convient mieux; mais soyez prudent avec les licences sur CGAL: github.com/straup/Clustr
scw
2
Bel exemple du monde réel.
DavidF
20

Il y a une implémentation de ST_ConcaveHull dans le coffre PostGIS. http://postgis.net/docs/ST_ConcaveHull.html

Nicklas Avén
la source
1
Je pense que cela apparaît pour la première fois dans la version 2.0 de PostGis
Adrian
19

J'ai créé un outil très efficace, appelé [lasboundary] [1,2], qui calcule une coque concave pour LIDAR au format LAS / LAZ / SHP / ASCII et stocke le résultat sous la forme d'un polygone de frontière vectorielle au format ESRI Shapefile ou d'un fichier géo. fichier KML référencé.

Voici un exemple d'exécution:

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

Quelques images de résultats sont ici .

Martin Isenburg
la source
10

Voici une fonction R qui implémente le modèle Alpha Hull. La sortie est un objet polygone sp. Veuillez voir l'exemple dans l'en-tête. Il nécessite les packages sp, alphahull et maptools.

** Mise à jour (01-15-2018) De nombreux changements ont été apportés aux objets résultants générés par le paquet alphahull. En tant que tel, je devais réécrire la fonction. J'ai ajouté une fonction convexHull au paquet spatialEco. Cependant, en raison de restrictions de licence dans le package alphahull, cette fonction est uniquement disponible dans la version de développement sur GitHub. La version de développement peut être installée à l'aide de:

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

Voici un exemple d'utilisation des fonctions

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

Convertissez le SpatialLinesDataFrame résultant en SpatialPolygonsDataFrame

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

Tester plusieurs valeurs alpha

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

divers paramètres alpha

Jeffrey Evans
la source
+1 Pouvez-vous expliquer en quoi cela diffère du paquet de formes alpha ?
whuber
3
La sortie de l'objet alphahull est stockée sous forme de matrice et doit être contrainte à un objet sp utilisable. Je considérerais cela comme une fonction "d'assistance" permettant de créer un polygone pouvant être exporté au format SIG. Cette fonction utilise le package alphahull pour créer l'objet matrice de coque, crée un objet sp, puis décompose l'emplacement du polygone pour en faire un objet polygone de données unique. Rien ne s'affiche dans l'aide du package, mais il se peut qu'il existe une nouvelle contrainte implémentée sur un objet de la classe sp que je ne connais pas. Si tel est le cas, veuillez me le faire savoir afin que je puisse désactiver cette fonction.
Jeffrey Evans
Quel est le langage de programmation?
Adam Matan
Merci @JeffreyEvans J'ai réussi à faire en sorte que cela fonctionne. Pourriez-vous éventuellement expliquer les paramètres? J'ai jeté un coup d'œil au papier jstatsoft lié, mais c'est assez impénétrable.
geotheory
9

JTS ( http://tsusiatsoftware.net/jts/main.html ) fournit une implémentation Convex Hull. Martin Davies a également mentionné la mise en place d'un algorithme Alpha Shape. Vous voudrez peut-être vérifier le référentiel SVN pour voir s'il est déjà entré si c'est ce que vous voulez.

Ian Turton
la source
Toujours pas de mise en œuvre coque concave / formes alpha à partir de Juin 2012 pour autant que je peux dire.
blah238
Toujours rien en mai 2013.
Crescent Fresh
JTS est-il en vie? La dernière version date du 19 décembre 2006. vividsolutions.com/jts/JTSHome.htm
angelcervera
essayez le lien dans la réponse
Ian Turton
JTS est maintenant sur Github et sa version 1.15 est la suivante: github.com/locationtech/jts Bien que, pour autant que je sache , il ne semble pas encore y avoir d'implémentation Alpha Shapes.
Colin Woodbury
7

Voici un programme écrit en C qui calcule les coques convexes, les formes alpha, les triangluations de Delauney et les volumes de Voronoï:

  • Hull - Ken Clarkson (2002)

Un autre algorithme de coque convexe avec des implémentations C et Java est ici:

blah238
la source
7

Pour ajouter aux réponses précédentes de ce message, au moins à partir de QGIS 2.6, un algorithme de coque concave est présent.

Paramètres
Couche de point d'entrée [vecteur: point]
mettre la description du paramètre ici

Seuil (0-1, où 1 est équivalent à Convex Hull) [nombre]
mettez la description du paramètre ici
Par défaut: 0.3

Allow trous [boolean]
met la description du paramètre ici
Par défaut: True

Fractionner la géométrie en plusieurs parties en géométries à une seule pièce [booléen]
Par défaut: False

Sorties coque concave [vecteur]
mettre la description de sortie ici

Console usage
processing.runalg ('qgis: concavehull', entrée, alpha, holes, no_multigeometry, sortie)

Esri dispose également d’un outil Géométrie de limite minimale (Gestion des données).

Ce qui vous permet de choisir le type de géométrie, qui inclut une coque convexe

entrez la description de l'image ici

pourquoizar
la source
3

Pour aider avec la "bonne définition" partie de votre question; vous avez peut-être regardé https://en.wikipedia.org/wiki/Convex_hull et obtenu ce qui pourrait bien être considéré comme une définition "correcte", mais l'a trouvée manquante; une définition plus "utile" est peut-être:

Pour chaque point à l'intérieur d'une coque convexe, une ligne droite jusqu'à un point ne se trouvant pas à l'intérieur de la coque ne coupera la coque qu'une fois.

Ceci est utile car, à partir d'un point, vous pouvez construire une ligne à travers celle-ci et tester pour cette ligne construite les segments intersectant la coque.

  • Pas d'intersection le point n'est pas dans la coque.
  • Une intersection, le point est sur la coque.
  • Deux intersections le point est dans la coque
  • Une ligne droite ne peut pas croiser une coque convexe plus de deux fois
utilisateur29206
la source
2
l'opération porte sur des coques concaves et non sur des coques convexes
winwaed