La elegancia del Diagrama de Voronoi
Desde que mi compañero Paco me contó el enfoque uno de sus trabajos de investigación he querido llevarlo a la práctica en una clase con QGIS.
En este trabajo, los autores usan el Diagrama de Voronoi como herramienta para diseñar una solución óptima del trazado de la Línea 2 del Metro de Sevilla.
La Línea 2 estaba pensada para cruzar Sevilla de Oeste a Este, atravesando el centro histórico de la ciudad y creando una vía de comunicación entre dos puntos estratégicos de movilidad: la estación de autobuses de Plaza de Armas y la estación de trenes de Santa de Justa.
El inconveniente de realizar el trazado a través del Casco Antiguo es que debe ser soterrado --la estrechez de la calles no permitiría un trazado en superficie-- y, además, debe alejarse de las edificaciones de interés histórico. ¿Cómo diseñarlo de forma óptima? Pues ellos usan el Diagrama de Voronoi para localizar el trazado por el Casco Antiguo. Ahora verás cómo.
Primero, vamos a considerar el centroide de cada una de la edificaciones que queremos proteger, en este ejemplo, yo he tomado una capa de Monumentos Históricos que nos proporciona de forma abierta el IECA. Estos puntos no coinciden exactamente con los del artículo, pero ilustran la forma de proceder. Para estos puntos, trazamos el Diagrama de Voronoi.
¿Qué es el Diagrama de Voronoi? Es una teselación del plano (o del espacio, aunque aquí nos quedamos con el plano) en regiones a partir de un conjunto de puntos generadores, de forma que cada punto generador es rodeado por los puntos del plano que son más cercanos a él que a los restantes generadores. Seguro que lo entiendes mejor viendo la imagen.
Este diagrama que ves, lo puedes pensar como una red --vértices y aristas--, por la que nos podemos mover. Observa que cada arista de esta red se sitúa en la mediatriz entre dos generadores vecinos. Si nos movemos por estas aristas, garantizamos afectar de la misma manera a la pareja de generadores que comparten las aristas.
Pero si queremos mantener una distancia de seguridad con los edificios, debemos rechazar pasar por aquellas aristas que se aproximan demasiado a los generadores. En el artículo, los autores establecen una distancia de protección de 80 metros alrededor de cada centroide.
Vamos a ello... Construimos un buffer de 80 metros para cada centroide.
Eliminamos del diagrama las aristas que no respetan esa distancia de 80 metros. En este caso, primero he convertido la capa poligonal del diagrama de Voronoi a líneas y, después, he hecho la diferencia con la capa de buffers de los centroides. He dejado los trocitos de las aristas, me gustaba más el efecto, aunque habría que borrar la arista completa.
Seguimos teniendo una red, ahora se trata de unir por el camino más corto las dos estaciones o dos puntos de las inmediaciones de estas estaciones. Para ello, usamos el Algoritmo de Dijkstra, tenemos diferentes herramientas en QGIS que lo implementan. Y así obtenemos nuestra solución óptima, la forma más corta de cruzar el Casco Antiguo, de forma segura, conectando esos dos puntos de alta movilidad.
En realidad, la propuesta para la Línea 2 tenía una estación en la Plaza del Duque y otra en la Plaza Cristo de Burgos, por tanto, nuestro camino corto debe pasar por esos dos nodos. Así que imponemos esa condición y obtenemos una nueva solución con esas condiciones. Esta es un poco más costosa, pero cumple todas las condiciones.
Para terminar la práctica, consideramos ahora el Diagrama de Voronoi de los polígonos de los edificios, no solo de sus centroides, y repetimos el mismo proceso. En este caso, no podemos mantener la zona de seguridad de 80 metros sobre el polígono, no obtenemos solución, pero con 50 metros funciona muy bien, como puedes ver.
La última versión que recuerdo del trazado de la Línea 2 por el Casco Antiguo no era exactamente igual a la solución de este ejercicio, pero se parecía bastante. Ahora parece que la idea para esta línea 2 es muy diferente, según he podido leer.
Esta entrada no ha sido más que una excusa para jugar un poco con algunas herramientas de QGIS y compartir contigo la elegancia del Diagrama de Voronoi, que lo mismo nos sirve para detectar un foco de infección como para definir el trazado de una línea de metro.
Gracias Paco.