Me perguntaram isso em um teste de entrevista. Fiz tudo bem no teste, mas não sabia o suficiente para responder a essa pergunta. Estou curioso para saber quais estruturas de dados posso usar para consultar os dados rapidamente.
Basicamente, a idéia é que haveria seções de estradas (linhas compostas de pontos) armazenadas em algum tipo de estrutura de dados. Deve ser rápido consultar quais seções (ou pontos) da estrada estão a uma certa distância de um ponto (raio).
Respostas:
A maneira típica de armazenar dados geográficos é com uma estrutura de dados espaciais, como uma árvore R (ou alguma variante, como uma árvore R +, uma árvore R *, etc.). É assim que os tipos de dados geográficos são normalmente implementados no GIS. RDBMS. (Eu sei que o SQL Server 2008 e o PostGIS da Microsoft usam árvores R para os tipos geográficos.) Eles atendem a todos os requisitos básicos que você descreveu e suportam trivialmente interseção, localização, distância e outros tipos de consulta.
Dependendo do tipo de dados, você também pode encontrar coisas como kD-trees, quad-trees, octrees, hierarquias de volume delimitadoras (incluindo árvores de caixas delimitadoras alinhadas ao eixo), etc. em uso comum. Na verdade, isso é muito mais comum em jogos 3D, pois o tamanho e a forma de um objeto são mais relevantes para as consultas de interseção. Eles são usados com menos frequência para GIS do que as árvores R.
fonte
Diferentes tipos de operações nos dados do mapa exigirão diferentes formatos de armazenamento para melhores resultados. Considere, por exemplo, as três tarefas a seguir:
As diferenças nos requisitos são suficientemente grandes para que, a menos que seja necessário acomodar alterações "vivas" no mapa, provavelmente seja melhor armazenar três cópias separadas dos dados - cada uma otimizada para uma das tarefas acima - do que tentar para criar um formato que possa lidar bem com as três tarefas.
fonte