Que estrutura de dados o Google utiliza para armazenar mapas offline?

Parei de trabalhar na minha tese para escrever uma resposta, pois esta pergunta despertou o meu interesse :)

Não tenho ideia de como o Google Maps armazena os seus mapas offline, mas conhecendo o Google, envolve um método tremendamente inteligente para comprimir esses dados. Não tenho a certeza se concordo com o seu argumento de que um "gráfico puro" não pode definir estradas. Vou dar o meu palpite completamente incerto sobre como se pode codificar dados de navegação.

>p>Tente imaginar o que é realmente uma estrada para fins de navegação. Ela se resume a uma série de waypoints geográficos conectados, com algum peso entre cada um deles. Este peso está correlacionado com um custo de viagem (distância combinada com uma velocidade estimada.) Cada segmento de estrada entre os pontos de passagem tem uma forma. Esta forma é basicamente apenas uma combinação de linhas rectas e curvas, mas nada que seja impossível de codificar.

P>Pode até combinar curvas e linhas entre waypoints de navegação com inter-waypoints, ou um waypoint invisível que existe para modelar a forma da estrada mas que não interage com o planeamento de rotas.

Uma curva pode ser representada pela função contínua de 2ª ordem:

[matemática]y = eixo^2 + bx + c[/math]

Não precisamos da constante c devido ao facto de a nossa função estar sempre a começar num waypoint conhecido. Portanto, precisamos apenas de armazenar 2 constantes para codificar uma curva!

Como para segmentos de estrada que são linhas rectas, não precisamos de armazenar nada! Já sabemos o ponto de partida e de chegada.

Quando você codifica suas estradas como funções (linha reta ou curva), você pode utilizar um gráfico vetorial como abordagem para desenhar uma estrada em qualquer nível de detalhe que desejar.

Vamos dizer que quando um mapa é baixado, o Google Maps tenta economizar o máximo de espaço possível, reduzindo faixas de endereço similares para uma única entidade. Você ainda obtém o bloco e o lado correto da rua, mas não a localização precisa. Isto poderia provavelmente reduzir o armazenamento denso do mapa da cidade por um fator de 3 ou mais quando você considera a quantidade de coisas que podem estar no mesmo quarteirão.

Você também precisaria codificar o número de faixas que cada rua tem, e a natureza de cada cruzamento em relação ao número de faixas de viragem, rotunda versus semáforo, e assim por diante.

Como para os próprios locais, não tenho certeza se há muito que pode ser feito para reduzir o tamanho do armazenamento. Você tem que armazenar seu nome, endereço e coordenadas globais. Você provavelmente pode codificar o tamanho e a forma do edifício renderizado na tela, já que a maioria dos edifícios são representados apenas como caixas brancas.

Você também precisa ter recursos de água no seu mapa! Você precisa de um método para rastrear qual espaço é água vs terreno. Uma maneira de fazer isso é com uma imagem binária. Você tem uma "máscara de água" que denota o valor 1 = terra e 0 = água para cada pixel. Você pode então usar alguma técnica de compressão de imagem para codificar os "blobs" de água. Técnicas de alisamento podem ajudar a renderizar a característica água para níveis menores de detalhe.

Então lá vai você. Este método codificaria muito bem estradas esparsas, retas no meio do nada, e estradas curvas desarticuladas com muitas pequenas características de água mal. Quanto menos complexa for a forma da estrada, menos dados precisam ser salvos. Estou curioso o suficiente para tentar montar um exemplo disso só para ver quantos dados poderiam ser salvos versus uma imagem detalhada de toda a área.