Map-Navigation Project, ¿cómo se almacenan/representan generalmente los datos de carreteras?

Question

Los sistemas de navegación como Garmin y TomTom siempre me han fascinado. He querido implementar pequeñas aplicaciones de mapas/navegación para probar varios algoritmos de navegación y ampliar mi conocimiento de ellos.

Ésta es una pregunta de dos partes:

1.) ¿Cómo se almacenan los datos del mapa? - Cuando tiene una red de carreteras, ¿cómo se almacenan generalmente estos datos? ¿Qué partes de los datos se retienen para reproducir un mapa más adelante? ¿Cada camino se almacena como una serie de puntos donde cambia de dirección? ¿En qué tipo de formatos de archivo se almacenan estos datos? ¿Hay bibliotecas disponibles públicamente para analizar fácilmente estos archivos? ¿Alguien tiene detalles sobre cómo se almacenan/representan los datos de mapas/carreteras? Sería muy útil.

2.) Navegación/Pathing - Al realizar una ruta básica en este mapa, los datos (a la Garmin) es mi suposición correcta de que se convierte en un gráfico dirigido? ¿Cada intersección de carreteras es un vértice con el borde pondera la distancia entre vértices? Esto es lo que estaba pensando hacer, así que podría probar algunos algoritmos de ruta básicos bien conocidos y ver lo que obtengo.

He visto this datos de mapas públicamente disponibles en los EE. UU., Pero no estoy seguro de cómo se representa y si es lo suficientemente detallado como para poder construir mi gráfico dirigido fuera de él.

Si alguien tiene alguna información, la agradecería. Cuanto más detallado sea el conocimiento, mejor.

Answer 1

No sé detalles sobre las unidades del sistema de navegación, pero en el mundo SIG estándar, los datos del mapa se almacenan básicamente como una colección de polígonos, líneas y puntos, cada uno descrito por sus coordenadas (y la proyección utilizada y algunos otros parámetros). Por ejemplo, uno de los formatos más comunes, shapefiles, se describe here, y el estándar de formato basado en la base de datos es here.

He utilizado con éxito este modelo de almacenamiento para la visualización de carreteras y el cálculo de rutas, usando PostgreSQL, PostGIS y PGRouting. Los cálculos se realizan utilizando los algoritmos de gráficos habituales y los datos almacenados en el formato común se almacenan también como un gráfico para permitir su aplicación. No puedo extrapolar esa experiencia a un dispositivo integrado, ya que probablemente lo hagan de forma muy diferente dada su capacidad informática limitada. Es muy probable que precalculen muchas cosas.

Para un enfoque algo diferente al almacenamiento, compruebe OpenStreetMap

Answer 2

Para mejorar la velocidad de dibujo a costa de mayor capacidad de almacenamiento y la resolución limitada, muchas aplicaciones utilizan un formato raster georreferenciado como GeoTiff.

Dado el comentario bastante insistente por debajo de ese Zich

"Los datos se encuentran en el vector en todos los sistemas de navegación sin excepción!"

Pensé en agregar un poco a lo anterior. En primer lugar, definiría un sistema de navegación como un sistema que le ayuda a llegar a donde quiere ir en función de su ubicación actual, generalmente al costar varias rutas alternativas posibles y recomendar la más económica. Las posibles rutas pueden ser dictadas por el modo de transporte, los autos permanecen en las carreteras, por ejemplo, mientras que los caminantes no lo hacen. El costo de las rutas también puede variar según el modo de transporte y según los requisitos del usuario.Es posible que los automóviles deseen tomar la ruta más rápida según la velocidad de la ruta, los camiones que quieran la ruta más eficiente en combustible, los senderistas quieran la ruta directa más segura, los barcos o los aviones deseen una ruta que evite los sistemas meteorológicos peligrosos y minimice el costo del combustible y el tiempo .

En el nivel más simple, un mapa y una brújula es un sistema de navegación. Reemplace el mapa con una pantalla pequeña, un mapa raster escalable y un GPS, y aún tiene un sistema de navegación. La mayoría de los sistemas de navegación marítima de nivel bajo a medio aún funcionan de esta manera, con gráficos que representan la costa y el fondo marino y el GPS para darte la ubicación y el eco de la profundidad.

En el extremo más avanzado del espectro, los sistemas autónomos de navegación robótica como el Mars Rover navigation system generan modelos DTM sobre la marcha como base para la navegación de corto alcance y los DEM recopilados por satélite para una navegación de mayor alcance.

Sugerir que todos los sistemas de navegación funcionan como dispositivos Garmin o Tom Tom de consumo es una presunción bastante ingenua. FWIW, muchos dispositivos Garmin modernos también incluyen raster based DEM data donde la altura del GPS de bajo costo puede ser muy impreciso.

Answer 3

La forma exacta en que se almacena depende del formato; hay montones de diferentes formatos GIS. GDAL es una excelente biblioteca gratuita para leer (casi) todos.

Normalmente, las carreteras se almacenarán en el archivo como una "capa de líneas", es decir, un conjunto de polilíneas con metadatos adjuntos. Entonces cada camino tendrá una serie de vértices, y dependiendo de la calidad de sus datos, con suerte tendrá información tal como si son de ida o no, estimados de velocidad y algún tipo de identificación de conexión.

Sí, normalmente se convierten en un gráfico dirigido para resolver. Los pesos de los bordes pueden ser la distancia o, más útil, el tiempo necesario para recorrer ese borde.

Resolver rápidamente es una compensación entre la precomputación y el espacio de almacenamiento (un dispositivo integrado puede necesitar una opción diferente aquí para una PC). Hay algunos algoritmos muy interesantes para hacer eso.

Answer 4

Mohammed: Bien, no entre en muchos detalles porque la pregunta original parecía bastante cómoda en ese aspecto. Si no está familiarizado con la teoría de grafos, probablemente sea una buena idea leer un poco ahora: Wikipedia está bien para una introducción.

Lo que normalmente ocurre es que en los datos de GIS las carreteras se almacenan como polilíneas con metadatos adjuntos. Eso está bien para mostrarlos en pantalla, etc., pero para poder navegarlos, necesita saber cuáles están conectados entre sí. Por lo tanto, en los metadatos normalmente hay una identificación de nodo para cada extremo de la carretera, por lo que puede decir "este es el segmento de carretera 457, va del nodo 332 al nodo 667". Entonces, cuando lee los datos GIS, crea una representación de este como un conjunto de nodos conectados por arcos (es decir, un gráfico).

Si los metadatos no están disponibles, podría inferir de qué carreteras tienen las mismas coordenadas de inicio/final (este es el caso con algunos datos GIS no tan maravillosos). El bit "dirigido" solo significa que las carreteras tienen dirección: algunas pueden viajar en cualquier dirección, pero otras solo son de sentido único.

El algoritmo típico para encontrar una ruta a través de un dígrafo es el algoritmo de Dijkstra; varios derivados se usan en la práctica. Básicamente, eso implica pasar de un nodo a otro a lo largo de los arcos del gráfico, por lo que necesita las estructuras de datos adecuadas para ello.

Espero que ayude ...

Answer 5

Las respuestas anteriores se refieren a todos los Sytems SIG.No es así como funcionan los dispositivos portátiles de navegación (PND). Son demasiado simples para ejecutar software SIG de escritorio/estado de trabajo.

En su lugar, los PND almacenan información casi como se suponía que era Simucal. Las carreteras se dividen en segmentos. Esto mantiene el modelo mucho más simple. Dentro de un segmento, los atributos como la velocidad máxima no cambian.

Para fines de planificación, los segmentos de camino actúan como los bordes en un gráfico. Para cada nodo, ambos nodos entrantes y salientes se almacenan. La planificación se realiza utilizando un algoritmo A * modificado. Los pesos de los bordes generalmente no son distancias, sino tiempo estimado de viaje (o en el caso de TomTom s, tiempo real medido).

Las redes de carreteras son típicamente jerárquicas, y la A * normal es lenta. Al viajar de una ciudad a otra, A * pasará una cantidad excesiva de tiempo arrastrándose por la ciudad de inicio. Sin embargo, nosotros los humanos sabemos que es mejor usar carreteras cuando se recorren distancias más largas. Para eso están hechos. Los PND también prefieren autopistas. Y como las carreteras son mucho más raras, esto ahorra mucha memoria.

Otra optimización es la búsqueda hacia delante y hacia atrás; planifica desde ambos lados hacia algún punto medio. La gran ventaja de esto es que si toma un giro incorrecto, puede buscar nuevamente desde un nuevo punto de inicio. El árbol de búsqueda hacia atrás no se modifica ya que su destino no se movió.

Answer 6

Si desea obtener algún código para tener una idea acerca de cómo funcionan las aplicaciones de enrutamiento, intente echar un vistazo a algunas de las aplicaciones de enrutamiento vinculadas desde openstreetmap.org wiki. Navit y Gosmore son de código abierto y bastante fáciles de configurar en particular.

Nic Roets, el desarrollador de la aplicación Gosmore, escribió un interesting post sobre sus elecciones para representar los datos vectoriales que también le pueden interesar.

Si desea echar un vistazo a Gosmore en acción, es el servidor del sitio web de enrutamiento yournavigation.org basado en datos de openstreetmap.