¿Cuáles son la Definición, Algoritmos y Soluciones Prácticas para el Casco Cóncavo?

Question

Envoltura Convexa

Una envoltura convexa de una forma se define como:

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

Wikipedia lo visualiza de manera clara utilizando una analogía de una banda de goma, y existen algunos buenos algoritmos para computarlo.

Envoltura Concava

Una envoltura concava se visualiza usando la línea roja en la imagen a continuación (la línea azul visualiza la envoltura convexa). Intuitivamente, es un polígono que abarca todos los puntos, pero tiene menos (¿mínima?) área en comparación con la envoltura convexa. Como resultado, la longitud del perímetro del polígono es mayor.

Una envoltura concava puede ser la solución para algunos problemas del mundo real (por ejemplo, encontrar el límite razonable de una ciudad).

¿Existe una definición adecuada, algoritmo y solución práctica para el concepto de una Envoltura Concava?

El Wiki de Grass tiene algunas descripciones e imágenes, y existe una solución comercial en concavehull.com.

Answer 1

Como scw señala, quieres una implementación de α-shapes.

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.; , "On the shape of a set of points in the plane," Information Theory, IEEE Transactions on , vol.29, no.4, pp. 551- 559, jul 1983

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

PostGIS

Si estás utilizando el stack de PostGIS, la extensión opcional Driving Distance de pgRouting expone una implementación de forma alfa. Sin embargo, no estoy seguro si puedes variar el parámetro alfa.

A continuación se muestra un ejemplo de uso:

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 haya muchos módulos de Python que podrías utilizar. He escuchado cosas buenas sobre CGAL, una biblioteca de geometría computacional en C++. Existen envolturas de Python para partes de CGAL, incluida la exposición de la implementación de formas alfa de CGAL a Python.

Ten en cuenta que algunas partes de CGAL están bajo licencia QPL, lo que significa que si distribuyes tu programa vinculado a CGAL, es posible que necesites liberarlo bajo la licencia QPL. Está bien mantener tu código como propietario si no redistribuyes el código de tu programa o los binarios.

Answer 2

Esto parece ser una aplicación específica de formas alfa, que según mi lectura son una forma más general de este problema. R tiene el módulo alphahull, que tiene una excelente documentación sobre cómo calcular formas alfa. También puedes consultar este fondo detallado sobre formas alfa. Si solo quieres calcular envolventes convexas/concavas, echa un vistazo a lasboundary, parte de lastools, escala bien y puede manejar millones de puntos de entrada.

Finalmente, esta interesante aplicación de formas alfa por Flickr dio vueltas hace un tiempo, mostrando su utilidad para agrupar contenido de puntos generados por el usuario:

Answer 3

Hay una implementación de ST_ConcaveHull en la rama Trunk de PostGIS. http://postgis.net/docs/ST_ConcaveHull.html

Answer 4

He creado 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ímite vectorial en formato de archivo ESRI Shapefile o un archivo KML georreferenciado.

Aquí hay un ejemplo de ejecución:

C:\lastools\bin>lasboundary -i SerpentMound.las -o SerpentMound_boundary.shp
leyendo 3265110 puntos y calculando casco convexo para 3265110 puntos
creciendo hacia adentro hacia el casco cóncavo (con concavidad = 50)
emitir el casco cóncavo
el casco cóncavo tiene 1639 puntos

Algunas imágenes de resultados están aquí.

Answer 5

JTS (https://github.com/locationtech/jts) proporciona una implementación de Envoltura Convexa. Martin Davies también mencionó tener un algoritmo de Forma Alfa en proceso, por lo que tal vez quieras revisar el repositorio SVN para ver si ya está disponible si eso es lo que buscas.