Suite

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

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


Enveloppe convexe

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

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

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 visualise la coque convexe). Intuitivement, il s'agit d'un polygone qui embrasse tous les points, mais a une surface moindre (minimale ?) par rapport à l'enveloppe 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).

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 contient des descriptions et des images, et il existe une solution commerciale sur concavehull.com.

Des idées, des algorithmes et des liens ?


Comme scw le souligne, vous voulez une implémentation des formes .

Les formes alpha peuvent être considérées comme une généralisation de l'enveloppe 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 l'avion," Théorie de l'information, IEEE Transactions on , vol.29, n°4, pp. 551-559, juillet 1983

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

PostSIG

Si vous utilisez la pile PostGIS, l'extension facultative Driving Distance de pgRouting expose une implémentation de forme alpha. Cependant, je ne sais pas si vous pouvez faire varier le paramètre alpha.

L'utilisation est ci-dessous:

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

Python

Il existe probablement de nombreux modules python que vous pourriez utiliser. J'ai entendu de bonnes choses à propos de CGAL, une bibliothèque de géométrie computationnelle C++. Des wrappers Python existent pour certaines parties de CGAL, y compris l'exposition de 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. C'est bien de garder votre code propriétaire si vous ne redistribuez pas le code de votre programme ou les binaires.


Voici ce que vous recherchez.

Vous pouvez télécharger et tester le programme : (en java, sous licence GPL)

L'article présentant l'algorithme est là :

Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008) Génération efficace de polygones simples pour caractériser la forme d'un ensemble de points dans le plan. Reconnaissance de modèle v41, 3224-3236


Cela semble être une application spécifique des formes alpha, qui sont d'après ma lecture une forme plus générale de ce problème. R a le module alphahull, qui possède une excellente documentation sur le calcul des formes alpha. Vérifiez également ce contexte détaillé sur les formes alpha. Si vous souhaitez uniquement calculer des coques convexes/concaves, consultez lasboundary, qui fait partie de lastools, il s'adapte bien et peut gérer des millions de points d'entrée.

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


Il existe une implémentation de ST_ConcaveHull dans le tronc PostGIS. http://postgis.net/docs/ST_ConcaveHull.html


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

Voici un exemple d'exécution :

C:lastoolsin>lasboundary -i SerpentMound.las -o SerpentMound_boundary.shp lisant 3265110 points et calculant la coque convexe pour 3265110 points croissant vers l'intérieur vers la coque concave (avec concavité = 50) produisant la coque concave coque concave a 1639 points

Quelques photos de résultats sont ici.


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

**Mise à jour (15/01/2018) De nombreuses modifications ont été apportées aux objets résultants produits par le package alphahull. En tant que tel, j'avais besoin de réécrire la fonction. J'ai ajouté une fonction convexHull au package spatialEco. Cependant, en raison de restrictions de licence dans le package alphahull, cette fonction n'est disponible que dans la version de développement sur GitHub. La version de développement peut être installée en utilisant :

bibliothèque(devtools) install_github("jeffreyevans/spatialEco")

Voici un exemple d'utilisation des fonctions

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

Convertir 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) titre( coller0("alpha=", a)) }


À propos de l'implémentation de R Alpha-Shapes, il y a un article sur "Converting Alpha-Shapes into SP Objects"

Il est basé sur alphahull, sp et spgrass6 http://casoilresource.lawr.ucdavis.edu/drupal/node/919


JTS (https://github.com/locationtech/jts) fournit une implémentation de coque convexe. Martin Davies a également mentionné avoir un algorithme Alpha Shape en préparation, vous voudrez peut-être vérifier le référentiel SVN pour voir s'il y est déjà si c'est ce que vous voulez.


En parlant de JTS, vous pouvez utiliser Geoscript pour manipuler la bibliothèque JTS. http://geoscriptblog.blogspot.com/2010/06/unwrapped-jts-with-python.html pour un article sur l'enveloppe convexe. Les implémentations GeoScript sont disponibles en JavaScript, Python, Scala et Groovy. Le site officiel : http://geoscript.org


Voici un programme écrit en C qui calcule les enveloppes convexes, les formes alpha, les triangulations de Delauney et les volumes de Voronoi :

  • Coque - Ken Clarkson (2002)

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

  • Coque convexe (2D) - Géométrie computationnelle en C, Joseph O'Rourke (1998)

Pour ajouter aux réponses précédentes pour ce post, au moins à partir de QGIS 2.6 a un algorithme de coque concave

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

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

Autoriser les trous [booléen]
mettre la description du paramètre ici
Par défaut : vrai

Diviser la géométrie en plusieurs parties en géométries en plusieurs parties [booléen]
Par défaut : Faux

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

Utilisation de la console
processing.runalg('qgis:concavehull', entrée, alpha, trous, no_multigeometry, sortie)

Esri dispose également d'un outil Géométrie limite minimale (gestion des données)

Ce qui vous permet de choisir le type de géométrie, qui comprend l'enveloppe convexe


Un nouvel Addon pour GRASS GIS 7 est disponible : v.concave.hull. Voir aussi http://grasswiki.osgeo.org/wiki/Create_concave_hull


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

Pour tous point à l'intérieur d'une enveloppe convexe, une ligne droite à quelconque le point qui n'est pas à l'intérieur de la coque n'intersectera la coque qu'une seule fois.

Ceci est utile car étant donné un point, vous pouvez construire une ligne à travers celui-ci et tester cette ligne construite qui coupe les segments de 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 couper une enveloppe convexe plus de deux fois

Voir la vidéo: Algorithmique 114 - Un algorithme cest quoi?