¿Existe un algoritmo eficiente para generar un casco cóncavo 2D?

Question

Al tener un conjunto de puntos (2D) de un archivo GIS (un mapa de la ciudad), necesito generar el polígono que define el 'contorno' para ese mapa (su límite). Sus parámetros de entrada serían los puntos establecidos y una 'longitud de borde máxima'. Luego emitiría el polígono correspondiente (probablemente no convexo).

La mejor solución que encontré hasta ahora fue generar los triángulos Delaunay y luego eliminar los bordes externos que son más largos que la longitud máxima del borde. Después de que todos los bordes externos son más cortos que eso, simplemente elimino los bordes internos y obtengo el polígono que quiero. El problema es que esto consume mucho tiempo y me pregunto si hay una mejor manera.

Answer 1

This artículo discute el generación eficiente de polígonos simples para caracterizar la forma de un conjunto de puntos en el plano y proporciona el algoritmo. También hay un applet de Java que utiliza el mismo algoritmo here.

Answer 2

Uno de los antiguos alumnos de nuestro laboratorio utilizó algunas técnicas aplicables para su tesis de doctorado. Creo que uno de ellos se llama "formas alfa" y se hace referencia en el siguiente documento:

http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf

Ese documento da algunas referencias adicionales que puede seguir.

Answer 3

Una solución rápida aproximada (también útil para cascos convexos) es encontrar los límites norte y sur para cada pequeño elemento este-oeste.

Según la cantidad de detalles que desee, cree una matriz de tamaño fijo de límites superiores/inferiores. Para cada punto, calcule en qué columna E-W se encuentra y luego actualice los límites superior/inferior para esa columna. Después de que haya procesado todos los puntos, puede interpolar los puntos superiores/inferiores para aquellas columnas que fallaron.

También vale la pena hacer una comprobación previa de formas delgadas muy largas y decidir si va a bin NS o Ew.

Answer 4

¡Buena pregunta! No he probado esto en absoluto, pero mi primer disparo sería este método iterativo:

1. crear un conjunto de N ("no contenida"), y añadir todos los puntos en su conjunto a N.
2. Elija 3 puntos de N al azar para formar un polígono inicial P. Quítelos de N.
3. Use some point-in-polygon algorithm y mire los puntos en N. Para cada punto en N, si ahora está contenido en P, quítelo de N. Tan pronto como encuentre un punto en N que todavía no está contenido en P, continúe con el paso 4. Si N queda vacío, ya está listo.
4. Llame al punto que encontró A. Encuentre la línea en P más cercana a A, y agregue A en el centro de ella.
5. vuelva al paso 3

Creo que sería trabajar con tal de que se realiza bien bastante - una buena heurística para sus primeros 3 puntos podrían ayudar.

¡Buena suerte!

Answer 5

Los muchachos here afirman haber desarrollado un enfoque de k vecinos más próximos para determinar el casco cóncavo de un conjunto de puntos que se comporta "casi linealmente en el número de puntos". Lamentablemente, su artículo parece estar muy bien guardado y tendrá que pedirle them.

Aquí hay un good set of references que incluye lo anterior y puede llevarlo a encontrar un mejor enfoque.

Answer 6

Una solución simple es caminar alrededor del borde del polígono.Dado un borde corriente om la frontera que une los puntos P0 y P1, el siguiente punto de la P2 límite será el punto con el más pequeño Un posible, donde

H01 = bearing from P0 to P1 
H12 = bearing from P1 to P2 
A = fmod(H12-H01+360, 360) 
|P2-P1| <= MaxEdgeLength 

continuación, establece

P0 <- P1 
P1 <- P2 

y repita hasta que vuelvas al lugar donde comenzaste.

Esto sigue siendo O (N^2) por lo que querrá ordenar su lista de puntos un poco. Puede limitar el conjunto de puntos que debe tener en cuenta en cada iteración si ordena puntos, por ejemplo, su orientación desde el centroide de la ciudad.

Answer 7

La respuesta todavía puede ser interesante para alguien más: Se puede aplicar una variación del algoritmo cuadrado marchando, aplicada (1) dentro del casco cóncava, y (2) a continuación, en (por ejemplo, 3) diferentes escalas que mi depende de la densidad promedio de puntos. Las escalas deben ser múltiplos enteros entre sí, de modo que construya una grilla que pueda usar para un muestreo eficiente. Esto permite encontrar rápidamente muestras vacías = cuadrados, muestras que están completamente dentro de un "clúster/nube" de puntos, y aquellos que están en el medio. La última categoría se puede usar para determinar fácilmente la línea de polietileno que representa una parte del casco cóncavo.

Todo es lineal en este enfoque, no se necesita la triangulación, que no utiliza las formas alfa y es diferente de la oferta comercial/patentado como se describe aquí (http://www.concavehull.com/)

Answer 8

Puede hacerlo en QGIS con este complemento; https://github.com/detlevn/QGIS-ConcaveHull-Plugin

Dependiendo de cómo lo necesite para interactuar con sus datos, probablemente valga la pena comprobar cómo se hizo aquí.

Answer 9

Como una referencia adoptada salvajemente, PostGIS comienza con un convexhull y luego lo cuela, puedes verlo aquí.

https://github.com/postgis/postgis/blob/380583da73227ca1a52da0e0b3413b92ae69af9d/postgis/postgis.sql.in#L5819

Answer 10

El SDK de Bing Maps interactiva V8 tiene una opción casco cóncava dentro de las operaciones de forma avanzada.

https://www.bing.com/mapspreview/sdkrelease/mapcontrol/isdk/advancedshapeoperations?toWww=1&redig=D53FACBB1A00423195C53D841EA0D14E#JS

Dentro ArcGIS 10.5.1, la extensión 3D Analyst tiene una herramienta Volumen delimitador mínimo con los tipos de geometría de casco cóncava, esfera, sobre, o casco convexo. Se puede usar en cualquier nivel de licencia.

Existe un algoritmo casco cóncava aquí: https://github.com/mapbox/concaveman