algorithm - ¿Hay un algoritmo eficiente para generar un casco cóncavo 2D?
math geometry (10)
¡Buena pregunta! No lo he probado en absoluto, pero mi primer disparo sería este método iterativo:
- Cree un conjunto N ("no contenido") y agregue todos los puntos en su conjunto a N.
- Elija 3 puntos de N al azar para formar un polígono inicial P. Quítelos del N.
- Usa algún algoritmo de punto en el polígono y mira los puntos en N. Para cada punto en N, si ahora está contenido en P, quítalo de N. Tan pronto como encuentres un punto en N que todavía no está contenido en P , continúe con el paso 4. Si N se convierte en vacío, ha terminado.
- Llame al punto que encontró A. Encuentre la línea en P más cercana a A, y agregue A en medio de ella.
- Regresa al paso 3
Creo que funcionaría siempre que funcione lo suficientemente bien; una buena heurística para tus 3 puntos iniciales podría ser útil.
¡Buena suerte!
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 de 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.
Como una referencia adoptada salvajemente, PostGIS comienza con un convexhull y luego lo cuela, puedes verlo aquí.
El SDK interactivo Bing Maps V8 tiene una opción de casco cóncavo dentro de las operaciones de forma avanzada.
Dentro de ArcGIS 10.5.1, la extensión 3D Analyst tiene una herramienta de Volumen delimitador mínimo con los tipos de geometría de casco cóncavo, esfera, envolvente o casco convexo. Se puede usar en cualquier nivel de licencia.
Aquí hay un algoritmo de casco cóncavo: https://github.com/mapbox/concaveman
La respuesta puede seguir siendo interesante para alguien más: se puede aplicar una variación del algoritmo cuadrado de marcha , aplicado (1) dentro del casco cóncavo, y (2) luego encendido (por ejemplo, 3) diferentes escalas que dependen 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 triangulación, no usa formas alfa y es diferente de la oferta comercial / patentada como se describe aquí ( http://www.concavehull.com/ )
Los muchachos here afirman haber desarrollado un enfoque de vecinos más cercanos 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ás que pedírselo.
Aquí hay un buen conjunto de referencias que incluye lo anterior y puede llevarlo a encontrar un mejor enfoque.
Puedes 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 verificar cómo se hizo aquí.
Una solución aproximada rápida (también útil para cascos convexos) es encontrar los límites norte y sur para cada pequeño elemento este-oeste.
En función de 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 EW está 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 rápida de formas delgadas muy largas y decidir si va a bin NS o Ew.
Una solución simple es caminar alrededor del borde del polígono. Dado un borde actual om el límite que conecta los puntos P0 y P1, el siguiente punto en el límite P2 será el punto con la A más pequeña posible, donde
H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength
Luego estableces
P0 <- P1
P1 <- P2
y repite hasta que vuelvas al punto de partida.
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.
Uno de los antiguos alumnos de nuestro laboratorio utilizó algunas técnicas aplicables para su tesis doctoral. 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 proporciona algunas referencias adicionales que puedes seguir.