¿Qué son la definición, los algoritmos y las soluciones prácticas para el casco cóncavo? [cerrado]

114

Casco convexo

Un casco convexo de una forma se define como:

  

En matemáticas, el casco convexo o la envoltura convexa para un conjunto de puntos X en un espacio vectorial real V es el conjunto convexo mínimo que contiene X ( Wikipedia )

Wikipedia lo visualiza bien usando una analogía de banda de goma, y hay algunos buenos algoritmos para calcularlo .

Casco cóncavo

Un casco cóncavo se visualiza usando la línea roja en la imagen de abajo (la línea azul visualiza el casco convexo). Intuitivamente, es un polígono que abarca todos los puntos, pero tiene menos área (¿mínimo?) En comparación con el casco convexo. Como resultado, la longitud del límite del polígono es más larga.

Un casco cóncavo puede ser la solución para algunos problemas del mundo real (por ejemplo, encontrar el límite razonable de una ciudad).

Nohepodidoencontrarunadefiniciónadecuada,unalgoritmoyunasoluciónprácticaparalanocióndeuncascocóncavo.El Grass Wiki tiene algunas descripciones e imágenes , y hay una solución comercial en concavehull.com .

¿Alguna idea, algoritmos y enlaces?

    
pregunta Adam Matan 16.08.2010 - 08:05

13 respuestas

57

Como scw señala hacia fuera , desea una implementación de α-shapes .

Las formas alfa pueden considerarse una generalización del casco convexo. Fueron descritos por primera vez en 1981 en:

  

Edelsbrunner, H .; Kirkpatrick, D .;   Seidel, R .; , "Sobre la forma de un conjunto   de puntos en el plano, "Información   Teoría, Transacciones IEEE en,   vol.29, no.4, pp. 551 a 559, julio de 1983

Existen implementaciones de código abierto para los entornos en los que está interesado:

PostGIS

Si está utilizando la pila PostGIS, pgRouting es opcional Extensión de distancia de conducción expone una implementación de forma alfa. No estoy seguro si puedes variar el parámetro alfa, sin embargo.

El uso está abajo:

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

Probablemente hay muchos módulos de python que podrías usar. He escuchado cosas buenas sobre CGAL , una biblioteca de geometría computacional de C ++. envoltorios de Python existen para partes de CGAL, incluida la exposición de CGAL Implementación de la forma alfa a Python .

Tenga en cuenta que algunas partes de CGAL están autorizadas por QPL, lo que significa que si distribuye su programa, vinculado a CGAL, es posible que deba publicarlo en virtud de QPL. Está bien mantener su código de propiedad si no redistribuye el código de su programa o los binarios.

    
respondido por el fmark 17.08.2010 - 09:38
41

Aquí es lo que está buscando.

Puedes descargar y probar el programa: (en java, bajo licencia GPL)

Eldocumentoquepresentaelalgoritmoestáahí:

Duckham, M., Kulik, L., Worboys, MF, Galton, A. (2008) Generación eficiente de polígonos simples para caracterizar la forma de un conjunto de puntos en el plano. Reconocimiento de patrones v41, 3224-3236

    
respondido por el julien 16.08.2010 - 12:47
29

Esto parece ser una aplicación específica de formas alfa , que Son de mi lectura una forma más general de este problema. R tiene el módulo alfahull , que tiene excelente documentación sobre cómo calcular formas alfa . También puedes ver este fondo detallado sobre formas alfa. Si solo desea calcular cascos convexos / cóncavos, visite lasboundary , parte de lastools , se escala bien y puede manejar millones de puntos de entrada.

Finalmente, esta aplicación interesante de formas alfa de Flickr hizo las rondas hace un tiempo, mostrando su utilidad para agregar contenido de puntos generado por el usuario:

    
respondido por el scw 16.08.2010 - 09:39
20

Hay una implementación de ST_ConcaveHull en el troncal PostGIS. enlace

    
respondido por el Nicklas Avén 11.10.2010 - 17:44
19

Creé una herramienta altamente eficiente, llamada [lasboundary] [1,2], que calcula un casco cóncavo para LIDAR en formato LAS / LAZ / SHP / ASCII y almacena el resultado como un polígono de límites vectoriales en formato ESRI Shapefile o un archivo KML geo-referenciado.

Aquí hay un ejemplo de ejecución:

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

Algunas imágenes de resultados son aquí .

    
respondido por el Martin Isenburg 29.08.2011 - 11:34
10

Sobre la implementación de R en Alpha-Shapes, hay un artículo sobre "Convertir Alpha-Shapes en objetos SP"

Se basa en alphahull, sp y spgrass6 enlace

    
respondido por el ThomasG77 17.08.2010 - 14:04
10

Aquí hay una función R que implementa el modelo Alpha Hull. La salida es un objeto polígono sp. Por favor vea el ejemplo en el encabezado. Requiere los paquetes sp, alphahull y maptools.

** Actualización (01-15-2018) Ha habido numerosos cambios en los objetos resultantes producidos por el paquete alphahull. Como tal, necesitaba reescribir la función. Agregué una función convexHull al paquete spatialEco. Sin embargo, debido a las restricciones de licencia en el paquete alphahull, esta función solo está disponible en la versión de desarrollo en GitHub. La versión de desarrollo se puede instalar usando:

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

Aquí hay un ejemplo del uso de funciones

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

Convierta el SpatialLinesDataFrame resultante en SpatialPolygonsDataFrame

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

Prueba múltiples valores alfa

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

    
respondido por el Jeffrey Evans 14.08.2012 - 20:46
9

JTS ( enlace ) proporciona una implementación de Casco Convexo. Martin Davies también mencionó el hecho de tener un algoritmo de forma alfa en las obras, por lo que es posible que desee verificar el repositorio de SVN para ver si aún está disponible, si eso es lo que desea.

    
respondido por el Ian Turton 16.08.2010 - 18:49
9

Hablando sobre JTS, puedes usar Geoscript para manipular la biblioteca JTS. enlace para un artículo sobre el casco convexo. Las implementaciones de GeoScript están disponibles en JavaScript, Python, Scala y Groovy. El sitio web oficial: enlace

    
respondido por el ThomasG77 20.08.2010 - 10:58
7

Aquí hay un programa escrito en C que calcula cascos convexos, formas alfa, triangluaciones de Delauney y volúmenes de Voronoi:

Otro algoritmo de casco convexo con C y Java implementaciones está aquí:

respondido por el blah238 05.06.2012 - 07:13
7

Para agregar a las respuestas anteriores de esta publicación, al menos a partir de QGIS 2.6 tiene algoritmo de casco cóncavo

  

Parámetros
  Capa de punto de entrada [vector: punto]
      poner la descripción del parámetro aquí

     

Umbral (0-1, donde 1 es equivalente con casco convexo) [número]
      poner la descripción del parámetro aquí
      Predeterminado: 0.3

     

Permitir agujeros [booleano]
      poner la descripción del parámetro aquí
      Predeterminado: Verdadero

     

Dividir geometría multiparte en geometrías simples [booleano]       
      Predeterminado: Falso

     

Salidas   Casco cóncavo [vector]
      poner la descripción de salida aquí

     

Uso de la consola
  processing.runalg ('qgis: concavehull', input, alpha, holes, no_multigeometry, output)

Además, Esri tiene una herramienta Geometría de delimitación mínima (Gestión de datos)

Lo que le permite elegir el tipo de geometría, que incluye el casco convexo

    
respondido por el whyzar 13.02.2017 - 23:14
6

Hay un nuevo complemento para GRASS GIS 7 disponible: v. concave.hull . Ver también enlace

    
respondido por el markusN 25.02.2013 - 18:14
3

Para ayudar con la parte de "definición adecuada" de su pregunta; puedes haber mirado enlace y obtuve lo que bien podría considerarse una definición "adecuada", pero me pareció deficiente, por lo que quizás sea más "útil" definición es:

Para cada punto dentro de un casco convexo, una línea recta hacia cualquier punto que no esté dentro del casco solo intersecará el casco una vez.

Esto es útil porque dado un punto, puedes construir una línea a través de ella y probar la línea construida que interseca los segmentos del casco.

  • Sin intersección, el punto no está en el casco.
  • En una intersección, el punto está en el casco.
  • Dos intersecciones: el punto está dentro del casco
  • Una línea recta no puede intersecar un casco convexo más de dos veces
respondido por el user29206 15.04.2014 - 02:09

Lea otras preguntas en las etiquetas