¿Cómo almaceno eficientemente todos los datos de OpenStreetMap de forma indexada?

8

Tengo un archivo PBF que contiene la siguiente información sobre un país:

  • Nodos, cada uno con su propia longitud, latitud y propiedades; Se utiliza para almacenar puntos en un espacio 2D.

  • Formas, cada una con sus propiedades, están conectadas a través de nodos; Se utiliza para almacenar carreteras, límites.

Si bien este archivo tiene solo 80 MB en su forma comprimida, es de 592 MB cuando se descomprime y se almacena en una base de datos.

Sí, y eso es solo para un país, Bélgica. Imagine almacenar Francia, Alemania e Italia junto.


Tomemos una sola carretera, por ejemplo, desde Amberes a través de Bruselas hasta Charleroi. Esto consistiría en una tonelada de nodos para almacenar todas las curvas en la carretera, pero ¿necesito todas estas curvas? Lo dudo.

Déjame decirte lo que quiero poder hacer:

  • Quiero ver el mapa en diferentes niveles de zoom; ciudades principales, ciudades menores y nivel de calle al menos.

  • Quiero poder obtener información de enrutamiento entre dos puntos.

  • Quiero poder calcular la carretera más cercana a mi ubicación GPS.

  • Busque una ubicación, mediante un índice en la base de datos.

Pero lo más importante, la base de datos no debe ser demasiado grande, ya que se almacenará en un dispositivo móvil .


Entonces, pensé en una combinación de dos técnicas:

  • Mosaicos de imagen para fines de visualización, para trabajar alrededor del almacenamiento / procesamiento de todos los nodos individuales.

  • Almacenar los puntos finales de las carreteras para la información de ruta, junto con la información sobre la carretera.

El problema con esto es que no puedo calcular la carretera más cercana a mi ubicación GPS con solo esta información; imagina que en una curva de una carretera, no puedo determinar si estoy en la carretera solo con los dos puntos finales. Estaba pensando en almacenar nodos intermedios entre puntos finales, pero creo que sería muy costoso generarlos. Además, determinar los puntos finales de las carreteras (que son como una división en T) probablemente no sea tan fácil, ya que necesito determinar si necesito almacenar el punto medio en la parte superior de esa división en T o no.

Entonces, la visualización es fácil usando mosaicos de imágenes; pero no puedo encontrar una manera fácil de enrutar y encontrar la ubicación del GPS, ¿qué tipo de técnica de almacenamiento debería estar buscando? Me parece un poco incómodo que un 80 MBarchivo se convierta en una base de datos 592 MB, quiero reducir ese tamaño lo más posible ...

¿Qué puedo hacer para hacer esto de la manera más eficiente posible? En cuanto a disco y CPU. Estoy apuntando a un WP7 ...

Tamara Wijsman
fuente
cuánto de los 580 MB son datos de nodo / vía y cuánto es el índice para tener acceso rápido a los datos
k3b

Respuestas:

4

Me parece que el problema principal es solo incluir nodos que agreguen información significativa sobre una carretera.

es decir, sin su requisito de GPS, podría almacenar nodos en uniones y terminaciones (que creo que llama nodos de inicio / finalización). Obviamente incluyendo peso / costos, etc.

Una forma en que puedo pensar en abordar esto es primero, agregar todos los nodos de inicio / fin. Este es el mínimo necesario. Obviamente esto no tiene en cuenta las carreteras sinuosas.

Luego, para cada camino (definido como finalización de cruce o cruce a cruce) haga lo siguiente:

  1. Realice un bucle a través de todos los nodos intermedios y calcule la distancia mínima de cada nodo a la carretera según lo definido por los nodos incluidos hasta ahora (para comenzar solo con el inicio y el final).
  2. Si la suma de lo anterior es mayor de lo (some constant threshold * number of intermediate nodes)que necesitamos agregar nodos intermedios. Si no, salga del bucle.
    • Para agregar nodos intermedios, encuentre el nodo que tenía la mayor distancia desde la representación actual de la carretera y agréguelo.
George Duckett
fuente
Eso tiene más sentido, ahora solo me pregunto cuál sería un buen umbral. Parece complicado implementar todo eso, aunque puedo comenzar desde la base de datos de 582 MB que ya tengo en lugar de comenzar desde el archivo comprimido de 80 MB. Dejará la pregunta abierta para ver qué otras ideas aparecen ... :)
Tamara Wijsman
Supongo que tendría que equilibrar el umbral entre incluir más nodos (tamaño más grande) e incluir menos nodos (menos preciso). Supongamos que el primer paso es poder generar una base de datos más pequeña que contenga solo uniones y puntos finales.
George Duckett
Está atascado al tener que tener los datos entre los nodos, incluida la ruta real. Hay costos entre nodos, pero pueden cambiar entre intersecciones. Los límites de velocidad y la cantidad de carriles no solo cambian en las intersecciones. Se requiere conocer la ruta exacta para calcular la carretera más cercana. Las líneas de conexión entre los nodos además de la ruta real necesitarán todos los metadatos para ese segmento. Estos metadatos serán necesarios para el enrutamiento y las instrucciones.
mhoran_psprep
Para encontrar la ruta, probablemente pueda evitar reducir el número de nodos, por ejemplo, si una carretera (entre cruces) tiene varios nodos, donde hay cambios en el límite de velocidad que no importan, ya que una vez que está en eso carretera tienes que continuar hasta el próximo cruce. Solo tenga cuidado al reducir los nodos para tener en cuenta diferentes límites de velocidad y longitudes de esos límites de velocidad. Lo mismo ocurre con el número de carriles, solo tendría que reducirlo a un peso de borde apropiado.
George Duckett
También depende de la definición de 'cruce', el significado que reduciría más, pero sería menos exacto, simplemente sería donde se unen 2 o más caminos. Una alternativa podría ser donde una propiedad de la carretera cambió (es decir, Menor-> Mayor, 30km-> 40km, etc.).
George Duckett