Existe un algoritmo eficiente para generar un 2D casco cóncavo?
https://stackoverflow.com/questions/83593
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Disponer de un conjunto de (2D) de los puntos de un SIG archivo (un mapa de la ciudad), hay que generar el polígono que define el contorno' de ese mapa (su límite).Sus parámetros de entrada sería el conjunto de puntos y un máximo de longitud de la arista'.Entonces la salida de la correspondiente (probablemente no convexo) polígono.
La mejor solución que he encontrado hasta ahora era generar los triángulos de Delaunay y, a continuación, quitar los bordes externos que son más largos que la máxima longitud de la arista.Después de que todos los bordes externos son más cortos que eso, yo simplemente quitar los bordes internos y obtener el polígono quiero.El problema es que esto es muy lento y me pregunto si hay una manera mejor.
Otros consejos
Uno de los ex alumnos en nuestro laboratorio utiliza algunas técnicas son aplicables para su tesis de Doctorado.Creo que uno de ellos se llama "alfa formas" y se hace referencia en el siguiente artículo:
http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf
Que papel le da algunas referencias que usted puede seguir.
Los chicos aquí afirman haber desarrollado un k vecinos más cercanos método para determinar el casco cóncavo de un conjunto de puntos que se comporta "de forma casi lineal con el número de puntos".Lamentablemente su papel parece estar muy bien protegida y usted tendrá que pedir ellos por ello.
He aquí una buen conjunto de referencias que incluye lo anterior y podría llevar a encontrar un mejor enfoque.
La respuesta todavía puede ser interesante para alguien:Uno puede aplicar un variación de la marcha de la plaza de algoritmo, que se aplica (1) dentro del casco cóncavo, y (2) entonces (por ej.3) diferentes escalas que de mi dependen de la densidad media de puntos.Las escalas deben ser de tipo int múltiplos de uno a otro, tal se puede construir un grid puede utilizar para el muestreo eficiente.Esto permite encontrar rápidamente vacío muestras=plazas, las muestras que están completamente dentro de un "cluster/nube" de puntos, y aquellos, que están en medio.La última categoría, que luego puede ser utilizado para determinar fácilmente la poli-línea que representa una parte del casco cóncavo.
Todo es lineal en este enfoque, no la triangulación es necesario, no utilizar alfa formas y que es diferente a la comercial patentado que ofrece y como se describe aquí ( http://www.concavehull.com/ )
Una solución simple es caminar alrededor del borde del polígono.Dado que una corriente de borde de om el límite de la conexión de los puntos P0 y P1, el siguiente punto en el límite P2 será el punto con la menor posible, donde
H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength
A continuación, se establece
P0 <- P1
P1 <- P2
y repetir hasta llegar donde se comenzó.
Esto todavía es O(N^2) por lo que usted desea ordenar su pointlist un poco.Usted puede limitar el conjunto de puntos que usted necesita para tener en cuenta en cada iteración si se ordenan los puntos, por ejemplo, en su relación de la ciudad del centro de gravedad.
Buena pregunta!No he probado este, pero mi primera foto sería este método iterativo:
- Crear un conjunto de N ("no figura"), y añadir todos los puntos en su conjunto a N.
- Pick 3 puntos de N al azar para formar un polígono inicial P.Eliminarlos de N.
- Uso algunos de punto en el polígono algoritmo y mirar los puntos en N.Para cada punto en N, si ahora es contenida por P, quitar de N.Tan pronto como usted encontrar un punto en N que todavía no figuran en P, continúe con el paso 4.Si N se convierte en vacío, ya está hecho.
- Llame el punto que se encuentra A.Buscar la línea P más cercano a Una, y agrega en el centro de la misma.
- Volver al paso 3
Creo que funcionaría mientras se realiza bastante bien — una buena heurística para sus primeros 3 puntos podría ayudar.
Buena suerte!
Usted puede hacerlo en QGIS con este plug;https://github.com/detlevn/QGIS-ConcaveHull-Plugin
Dependiendo de cómo usted necesita para interactuar con sus datos, probablemente vale la pena mirar cómo se ha hecho aquí.
Los Mapas de Bing V8 interactivo SDK tiene un casco cóncavo opción dentro de la avanzada de la forma de las operaciones.
Dentro de ArcGIS 10.5.1, la extensión 3D Analyst tiene un Mínimo Volumen de Delimitación de la herramienta con la geometría de los tipos de casco cóncavo, esfera, sobre, o convex hull.Puede ser utilizado en cualquier nivel de licencia.
Hay un casco cóncavo algoritmo de aquí: https://github.com/mapbox/concaveman
Una rápida solución aproximada (también útil para convexo cascos) es encontrar el norte y el sur de los límites de cada pequeño elemento de este-oeste.
Basado en el nivel de detalle que desee crear una matriz de tamaño fijo de superior/inferior de los límites.Por cada punto que se calcula que E-W de la columna y, a continuación, actualizar la parte superior/inferior de los límites para esa columna.Después de procesar todos los puntos que usted puede interpolar la parte superior/inferior de puntos de las columnas que se perdió.
También vale la pena hacer una revisión rápida de antemano para muy largo y delgado formas y decidir si a bin NS o Ew.
Como un salvajemente adoptado referencia, PostGIS comienza con un convexhull y, a continuación, cuevas de ella, se puede ver aquí.
