¿Cuál es la definición, los algoritmos y las soluciones prácticas para el casco cóncavo?

Question

Casco convexo

Un casco convexo de una forma se define como:

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

Wikipedia lo visualiza muy bien utilizando una analogía con una banda elástica, y hay algunos buenos algoritmos para calcularlo .

Casco cóncavo

Un casco cóncavo se visualiza mediante la línea roja de la imagen inferior (la línea azul visualiza el casco convexo). Intuitivamente, se trata de un polígono que abarca todos los puntos, pero que tiene un área menor (¿mínima?) en comparación con el casco convexo. En consecuencia, la longitud del límite del polígono es mayor.

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

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

¿Alguna idea, algoritmos y enlaces?

Answer 1

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

Las formas alfa pueden considerarse 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", Information Theory, IEEE Transactions on , vol.29, no.4, pp. 551- 559, Jul 1983

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

PostGIS

Si está utilizando la pila PostGIS, pgRouting de la empresa, que es opcional Ampliación de la distancia de conducción expone una implementación de la forma alfa. Sin embargo, no estoy seguro de si se puede variar el parámetro alfa.

El uso es el siguiente:

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 utilizar. He oído hablar bien de CGAL una biblioteca de geometría computacional en C++. Envoltorios de Python existen para partes de CGAL, incluyendo la exposición de los implementación de la forma alfa a Python .

Ten en cuenta que partes de CGAL están licenciadas bajo la QPL, lo que significa que si distribuyes tu programa, enlazado a CGAL, puedes necesitar liberarlo bajo la QPL. Está bien mantener su código propietario si no redistribuye su código de programa o binarios.

Answer 2

Esto parece ser una aplicación específica de formas alfa que son, según mi lectura, una forma más general de este problema. R tiene el módulo alphahull que tiene excelente documentación sobre el cálculo de las formas alfa . También puedes ver esto antecedentes detallados en las formas alfa. Si sólo quiere calcular cascos convexos/cóncavos, consulte lasboundary , parte de lastools Se adapta bien y puede manejar millones de puntos de entrada.

Por último, este interesante aplicación de las formas alfa por Flickr se han dado a conocer hace un tiempo, mostrando su utilidad para la agregación de contenidos puntuales generados por los usuarios:

Answer 3

Hay una implementación de ST_ConcaveHull en el trunk de PostGIS. http://postgis.net/docs/ST_ConcaveHull.html

Answer 4

He creado una herramienta muy eficaz, 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 georreferenciado.

Este es 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 los resultados son aquí .

Answer 5

STC ( https://github.com/locationtech/jts ) proporciona una implementación de Convex Hull. Martin Davies también mencionó que tiene un algoritmo de forma alfa en las obras, por lo que es posible que desee comprobar el repositorio SVN para ver si está en todavía si eso es lo que quieres.