Cálculo de diagramas de Voronoi para polígonos

Question

Existe una gran variedad de buenos algoritmos para generar los polígonos de Voronoi o su complemento, la triangulación de Delaunay para un conjunto de puntos.

Mi pregunta es simplemente, ¿Existe un algoritmo para generar el diagrama de Voronoi para un conjunto de polígonos de entrada? ¿en lugar de puntos?

Una técnica que he explorado consiste en dividir mis polígonos en conjuntos de vértices y crear los diagramas de Voronoi para ellos, combinando después las formas resultantes para cada conjunto de vértices pertenecientes a un polígono de entrada concreto. Sin embargo, los resultados no son del todo precisos. ¿Alguien tiene una técnica alternativa?

EDITAR:

Aquí está un ejemplo dibujado a mano super áspera de lo que estoy buscando. Tengo un conjunto de polígonos con huecos. Estoy tratando de crear polígonos de salida sin espacios entre ellos. En última instancia, quiero usar esto para decir si dos polígonos cercanos pueden ser considerados "adyacentes" entre sí, incluso si no se tocan.

Answer 1

He publicado un mini paquete python para hacerlo - diagrama de voronoi para polígonos . Cabe señalar de antemano que este paquete depende de v1.8.dev0 de bien formado que aún está en desarrollo. En otras palabras, no puede ser instalado por pip automáticamente. Tienes que instalarlo de la siguiente manera:

pip install git+https://github.com/Toblerity/Shapely .

Answer 2

Puede buscar publicaciones sobre "Diagrama de Voronoi de segmentos" o también sobre "Eje medial". CGAL ofrece Diagramas de Voronoi de segmentos.

Answer 3

Me gusta la respuesta que menciona "Diagramas de Voronoi de segmentos", pero al final me resultó difícil de aplicar en mi flujo de trabajo particular. Encontré que debido a que mis geometrías eran bastante detalladas (es decir, tenían un gran número de vértices en comparación con su área) pude calcular el diagrama de voronoi para los vértices de todos los polígonos de entrada utilizando ST_VoronoiPolygons en PostGIS. Luego intersecté esos polígonos de voronoi con las geometrías de entrada y los uní en consecuencia. Los polígonos resultantes eran lo suficientemente buenos como para decirme qué polígonos eran adyacentes (es decir, era posible lanzar un rayo desde al menos algún punto del Polígono A al Polígono B sin chocar con ningún Polígono C) sin que los polígonos se tocaran realmente. Obviamente, este método tiene algunas limitaciones; si sus geometrías no son lo suficientemente detalladas, los resultados serán menos precisos. En mi caso, fue suficientemente bueno.

Answer 4

La forma más fácil que encontré es usar PostGIS para crear buffers y luego usar ST_ApproximateMedialAxis. Es (ligeramente) aproximado, pero funciona muy bien en la mayoría de los casos. Permite resultados mucho mejores que usar buffer y luego usar el centroide de los polígonos para generar un Diagrama de Voronoi con el que recortarlo.

En la práctica, el tamaño del búfer debe ser lo suficientemente grande como para que los búferes generados se solapen entre sí. A continuación, ST_Union disolverá los búferes y usted cortará la capa de búfer disuelta resultante recortándola con la original. El resultado es un gran búfer disuelto con agujeros. Es este buffer el que necesita ser procesado por ST_ApproximateMedialAxis.

Finalmente, los polígonos que no tocan a los originales necesitan ser borrados con ST_Touches, que también es muy bueno para coger atributos del conjunto original de polígonos:

ST_VoronoiPolygons no produce el resultado esperado en mi situación:

Answer 5

¿Es necesario utilizar el teselado de Voronoi, o simplemente se busca un medio para rellenar los huecos entre polígonos? ¿Trabaja con algún SIG en particular? Se lo pregunto porque es posible que utilice algo como Asignación euclidiana en ArcGIS para obtener un resultado adecuado. La herramienta genera un ráster, pero se puede volver a convertir en polígonos si es necesario.