Me preguntaron esto en una prueba de entrevista. Me fue bien en el examen, pero no sabía lo suficiente como para responder a esta pregunta. Tengo curiosidad por saber qué estructuras de datos puedo usar para consultar los datos rápidamente.
Básicamente, la idea es que habría secciones de carretera (líneas, formadas por puntos) almacenadas en algún tipo de estructura de datos. Debería ser rápido consultar qué secciones (o puntos) de la carretera están dentro de una cierta distancia desde un punto (radio).
Respuestas:
La forma típica de almacenar datos geográficos es con una estructura de datos espaciales como un árbol R (o alguna variante, como un árbol R +, un árbol R *, etc.) Así es como los tipos de datos geográficos se implementan normalmente en GIS RDBMS. (Sé que tanto SQL Server 2008 como PostGIS de Microsoft usan árboles R para los tipos geográficos). Cumplen con todos los requisitos básicos que ha descrito y admiten trivialmente intersección, ubicación, distancia y otros tipos de consultas.
Dependiendo del tipo de datos, también puede encontrar cosas como árboles kD, árboles cuádruples, octreos, jerarquías de volúmenes delimitadores (incluidos árboles de recuadros delimitadores alineados con ejes), etc. de uso común. En realidad, esto es mucho más común en los juegos 3D, ya que el tamaño y la forma de un objeto es más relevante para las consultas de intersección. Se usan con menos frecuencia para los SIG que los árboles R.
fuente
Los diferentes tipos de operaciones sobre los datos del mapa requerirán diferentes formatos de almacenamiento para obtener resultados óptimos. Considere, por ejemplo, las siguientes tres tareas:
Las diferencias en los requisitos son lo suficientemente grandes como para que, a menos que uno necesite acomodar cambios "en vivo" en el mapa, probablemente sea mejor almacenar tres copias separadas de los datos, cada una optimizada para una de las tareas anteriores, que intentar para llegar a un formato que pueda manejar bien las tres tareas.
fuente