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


116

Casco convexo

Un casco convexo de una forma se define como:

En matemáticas, el casco convexo o 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 muy bien usando una analogía de banda elástica, y hay algunos buenos algoritmos para calcularlo .

Casco Cóncavo

Se visualiza un casco cóncavo utilizando la línea roja en la imagen a continuación (la línea azul visualiza el casco convexo). Intuitivamente, es un polígono que abarca todos los puntos, pero tiene menos (¿mínimo?) Área 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).

ingrese la descripción de la imagen aquí

No he podido encontrar una definición adecuada, un algoritmo y una solución práctica para la noción de un casco cóncavo. El Wiki hierba tiene algunas descripciones e imágenes , y no hay una solución comercial en concavehull.com .

¿Alguna idea, algoritmos y enlaces?


¿En qué contexto desea generar cascos cóncavos / formas alfa? En PostGIS, ArcMap, un mapa web, ¿su propio software?
fmark

Tanto PostGIS como mis propios scripts de Python.
Adam Matan

¿Existe una versión de implementación compatible con Linux C ++ del algoritmo de casco cóncavo?
Sylv255

Si tiene una nueva pregunta, hágala haciendo clic en el botón Hacer pregunta . Incluya un enlace a esta pregunta si ayuda a proporcionar contexto. - De la opinión
Evil Genius

La Biblioteca de Algoritmos de Geometría Computacional (CGAL) es una biblioteca C ++ con formas alfa. Tiene una descarga de Linux y tiene licencia como GPL / LGPL para la versión> = 4.0.
klewis

Respuestas:


57

Como señala scw , desea una implementación de formas α .

Las formas alfa se pueden considerar una generalización del casco convexo. Se describieron por primera vez en 1981 en:

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

Existen implementaciones de código abierto para los entornos que le interesan:

PostGIS

Si está utilizando la pila PostGIS, la extensión opcional de Distancia de conducción de pgRouting expone una implementación de forma alfa. Sin embargo, no estoy seguro de si puede variar el parámetro alfa.

El uso está debajo:

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');

Pitón

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

Tenga en cuenta que algunas partes de CGAL tienen licencia bajo QPL, lo que significa que si distribuye su programa, vinculado a CGAL, es posible que deba liberarlo bajo QPL. Está bien mantener su código de propiedad si no redistribuye su código de programa o binarios.


No puedo hacer que se compilen los envoltorios de Python de CGAL --- parece que estos no han sido compatibles por un tiempo y ya no funcionan con una versión reciente de CGAL.
conradlee

2
@fmark: el segundo enlace que publicaste parece estar muerto.
radek

1
enlaces @fmark PostGIS parecen estar muerto ..
Radek


29

Esta parece ser una aplicación específica de formas alfa , que son, desde mi lectura, una forma más general de este problema. R tiene el módulo alphahull , que tiene una excelente documentación sobre el cálculo de formas alfa . También revise este fondo detallado sobre formas alfa. Si solo desea calcular cascos convexos / cóncavos, vea el límite de las láminas , parte de lastools , se escala bien y puede manejar millones de puntos de entrada.

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

casco alfa de texas desde flickr


1
OMG la fuente está escrita en FORTRAN :-)
Adam Matan

Existe el paquete clustr escrito en C ++ si eso le conviene mejor; pero tenga cuidado con las licencias en CGAL: github.com/straup/Clustr
scw

2
Buen ejemplo del mundo real.
DavidF


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 contorno vectorial en formato ESRI Shapefile o un geo de archivo KML 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 fotos de resultados están aquí .



10

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

** Actualización (15-01-2018) Se han producido 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 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)

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

varios parámetros alfa de ahull


+1 ¿Podría explicar cómo esto difiere del paquete de formas alfa ?
whuber

3
La salida del objeto alphahull se almacena como una matriz y debe ser forzada a un objeto sp utilizable. Consideraría que esta es una función "auxiliar" para crear un polígono que se pueda exportar a un formato SIG. Esta función utiliza el paquete alphahull para crear el objeto de matriz de casco, crea un objeto sp y luego explota la ranura de polígono para que sea un objeto de marco de datos de polígono de una sola parte. No aparece nada en la ayuda del paquete, pero puede haber una coacción nativa recientemente implementada para un objeto de clase sp que no conozco. Si este es el caso, hágamelo saber para que pueda retirar esta función.
Jeffrey Evans el

¿Cuál es el lenguaje de programación?
Adam Matan

Gracias @JeffreyEvans. He logrado que esto funcione. ¿Podrías explicar los parámetros? He echado un vistazo al documento jstatsoft vinculado, pero es bastante impenetrable.
geotheory

9

JTS ( http://tsusiatsoftware.net/jts/main.html ) proporciona una implementación de casco convexo. Martin Davies también mencionó que se está trabajando en un algoritmo de forma alfa, por lo que es posible que desee verificar el repositorio SVN para ver si todavía está dentro, si eso es lo que desea.


Aún no hay implementación de formas cóncavas / alfa cóncavas a partir de junio de 2012, por lo que puedo decir.
blah238

Todavía nada en mayo de 2013.
Crescent Fresh

¿JTS está vivo? La última versión es del 19 de diciembre de 2006. vividsolutions.com/jts/JTSHome.htm
angelcervera

pruebe el enlace en la respuesta
Ian Turton

JTS ahora está en Github, y es la versión de enfoque 1.15: github.com/locationtech/jts Aunque, por lo que puedo decir, todavía no parece haber una implementación de Alpha Shapes.
Colin Woodbury


7

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

  • Casco - Ken Clarkson (2002)

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


7

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

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

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

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

Dividir la geometría de varias partes en geometrías de una sola parte [booleano]
Valor 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 límite mínimo (gestión de datos)

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

ingrese la descripción de la imagen aquí



3

Para ayudar con la parte de "definición adecuada" de su pregunta; es posible que haya mirado https://en.wikipedia.org/wiki/Convex_hull y haya obtenido lo que bien podría considerarse una definición "adecuada", pero la encontró faltante, por lo que quizás una definición más "útil" sea:

Para cada punto dentro de un casco convexo, una línea recta a cualquier punto que no esté dentro del casco solo se cruza con el casco una vez.

Esto es útil porque dado un punto puede construir una línea a través de él y probar esa línea construida que intersecta segmentos del casco.

  • Sin intersección, el punto no está en el casco.
  • Una intersección el punto está en el casco.
  • Dos intersecciones, el punto está dentro del casco
  • Una línea recta no puede cruzar un casco convexo más de dos veces

2
el operador está preguntando sobre cascos cóncavos y no cascos convexos
winwaed