¿Cuál es una buena estructura de datos para mapear una red de carreteras?

Uno pensaría una gráfica. Y eso probablemente sea el adecuado para muchas aplicaciones

Pero … las aplicaciones más comunes, que realmente hacen un seguimiento de las redes de carreteras, son los SIG (Sistemas de Información Geográfica) y los sistemas de navegación, que necesitan (y siguen) muchos más detalles, como la ruta específica que sigue una carretera. Los gráficos no son tan útiles. En general, los archivos GIS se almacenan como “archivos de forma” de ESRI o en una geodatabase como Oracle Spatial o PostGIS (Postgres con extensiones geoespaciales). Esto es importante porque los datos sin procesar, por ejemplo, de los departamentos de carreteras, tienden a estar en formatos SIG.


Si está buscando una herramienta, hay una serie de buenos sistemas SIG flotando: comerciales (por ejemplo, productos ESRI), de código abierto (consulte MapTools.org) e intermedios (por ejemplo, Google Maps).

También hay amplias bases de datos de redes de carreteras que se pueden usar con estas herramientas. (¡Construir la base de datos es la parte difícil de cualquier tipo de aplicación de mapeo!).

El punto de partida para muchos productos de mapeo son los archivos TIGER, de la oficina del censo: TIGER Products – Geography – US Census Bureau (también puede encontrar información de formato allí). Otras fuentes primarias tienden a ser departamentos GIS estatales y locales que apoyan departamentos de carreteras. En estos días, Google y otros servicios de mapeo también desarrollan sus propios conjuntos de datos de mapeo. Eche un vistazo al sitio para desarrolladores de Google Maps para ver algunos conjuntos de datos, API y formatos de datos adicionales. Consulte también el sitio web de ESRI (ESRI ArcInfo es el principal producto comercial utilizado por los departamentos de SIG).


En estos días, encontrará que una gran cantidad de aplicaciones (por ejemplo, planificadores de viajes para sistemas de tránsito) se crean sobre las API de Google Maps (o, en algunos casos, Bing Maps). El material comercial y militar está construido sobre los productos de ESRI.

Lo que puede hacer es comenzar con Google Maps u OpenStreetMap (código abierto equivalente a Google Maps: menos restricciones, pero no una información clara o herramientas poderosas). Si comienza con uno de estos, ya sea la versión GUI o el uso de las API, “Encontrar (ing) rutas más cortas y dibujar (ing) el mapa para un rectángulo dado” se vuelve bastante trivial.

Usaría dos estructuras de datos reticulados: un gráfico para las conexiones y un árbol cuádruple para la geometría.

El gráfico es bastante obvio: es un conjunto de nodos con enlaces entre ellos. A menudo se representa mediante una matriz de conexión: dos nodos están conectados si A [x, y] no es cero. La distancia entre los nodos sería un buen valor para poner allí.

Un árbol cuádruple es, como es de esperar, un árbol donde cada nodo tiene hasta cuatro hijos; comienza con un nodo que representa un área cuadrada y la subdivide si algún cuadrante contiene algo diferente.

A2A

Puede usar rutas hechas de segmentos de línea y beziers de segundo o tercer grado. Conozco una compañía que también usa clotoides.

Entonces echa un vistazo

Manual de SpatiaLite

Quadtree – Wikipedia

Orden de Morton:

Curva de orden Z – Wikipedia