navigation - vehicular - Proyecto de navegación de mapas. ¿Cómo se almacenan/representan generalmente los datos viales?
tdpa sct 2017 (6)
No sé detalles sobre las unidades del sistema de navegación, pero en el mundo GIS 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 aquí, y el estándar de formato basado en la base de datos está aquí .
He utilizado con éxito este modelo de almacenamiento para la visualización de carreteras y el cálculo de rutas, utilizando 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, consulte OpenStreetMap
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.
Esta es una pregunta de dos partes:
1.) ¿Cómo se almacenan los datos del mapa? - Cuando tienes 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 / Rutas - Al hacer una ruta básica en este mapa de datos (a la Garmin) es mi suposición correcta 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 estos datos de mapas disponibles públicamente en los EE. UU., Pero no estoy seguro de cómo se representan y si son lo suficientemente detallados para que pueda crear mi gráfico dirigido.
Si alguien tiene alguna información, la agradecería. Cuanto más detallado sea el conocimiento, mejor.
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 a 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.
Mohammed: Bien, no entre en detalles allí 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 sobre ella ahora: Wikipedia está bien para una introducción.
Lo que normalmente sucede es que en los datos SIG, 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 esos metadatos no están disponibles, podría inferir de qué caminos 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...
Todas las respuestas anteriores se refieren a sistemas GIS. 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 cambio, los PND almacenan la información más o menos como supuso 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 viales 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 de viaje estimado (o en el caso de TomTom , tiempo real medido).
Sin embargo, las redes de carreteras son típicamente hierá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 adelante 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ó.
Si desea ver 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 la wiki de openstreetmap.org . 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ó una publicación interesante sobre sus elecciones para representar los datos vectoriales que también le pueden interesar.
Si desea ver a Gosmore en acción, es el sitio web de enrutamiento de yournavigation.org basado en datos de openstreetmap.
Para mejorar la velocidad de dibujo a costa de más almacenamiento y resolución limitada, muchas aplicaciones usarán un formato de ráster georeferenciado como GeoTiff .
Dado el comentario bastante insistente de Zich a continuación que
"¡Los datos están en vector en todos los sistemas de navegación sin excepción!"
Pensé que agregaría 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 sistema de navegación Mars Rover 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 datos DEM basados en ráster en los que la altura de GPS de bajo costo puede ser extremadamente inexacta.