Como o Mapsake criou seu atlas de viagens offline.

Uma coordenada ainda não é um lugar.

Uma foto de viagem pode conter uma latitude e uma longitude com uma precisão impressionante. Esses dois números nem sempre indicam se a câmera estava no Japão, na província de Kyoto, em Kyoto ou no Aeroporto Internacional de Kansai a caminho de casa. Mapsake precisa dessa hierarquia antes que um ponto possa se tornar um registro de viagem útil.

O componente que responde a essas perguntas é um diretório geográfico: um diretório estruturado de locais geográficos nomeados. O Mapsake inclui seu diretório geográfico dentro do aplicativo, juntamente com as linhas de limite usadas para desenhar e testar países e regiões de primeiro nível. A pesquisa, a marcação manual, a importação de fotos, as histórias de locais, as estatísticas do Passport, as conquistas e até mesmo algumas visualizações de amigos dependem disso.

Seria mais fácil enviar cada coordenada para um geocodificador web. Isso também tornaria uma grande importação de fotos mais lenta, dependente da rede, mais difícil de reproduzir e menos privada. A abordagem offline exigiu mais engenharia inicialmente, mas deu ao Mapsake um vocabulário geográfico estável que funciona da mesma forma em um avião, em casa e anos após um conjunto de dados de origem mudar.

Esta é a história de como essa camada foi construída, onde os pontos e as linhas não coincidem e por que "cidade mais próxima" é apenas o começo de uma resposta correta.

Quatro conjuntos de dados abertos, quatro empregos diferentes

Nenhuma fonte única contém tudo o que o Mapsake precisa, por isso, o processo de compilação combina quatro tipos de dados abertos:

• GeoNames fornece países, regiões administrativas de primeiro nível, lugares habitados, identificadores estáveis, nomes alternativos, coordenadas e população.
• Nossos aeroportos fornece aeroportos, códigos IATA e ICAO, nomes, municípios e coordenadas.
• Natural Earth fornece a geometria das fronteiras do país (admin-1) e pontos de etiqueta de mapa úteis.
• Uma camada pequena e de propriedade da Mapsake registra decisões relacionadas ao produto, como o número de países suportados, aliases e correções que não podem ser inferidas com segurança de uma fonte genérica.

Cada fonte é boa em algo diferente. GeoNames sabe que uma cidade pertence a uma região e a um país, mas uma coordenada de cidade é um ponto, não uma fronteira. Natural Earth sabe onde um polígono é desenhado, mas seus identificadores de recursos nem sempre correspondem perfeitamente ao GeoNames. OurAirports sabe que KLAX e LAX se referem ao mesmo aeroporto, mas não é uma hierarquia de todos os lugares ao redor do aeroporto.

O script de compilação baixa e armazena em cache os arquivos de origem, os normaliza, valida as relações e gera dois artefatos compilados: um banco de dados SQLite somente leitura e uma geometria GeoJSON simplificada. O aplicativo fornece esses resultados. Ele não baixa um banco de dados mundial na primeira execução nem depende da disponibilidade dos sites de origem durante uma viagem.

O compromisso com os artefatos gerados também torna a versão reproduzível. Uma versão enviada tem um mundo geográfico conhecido. Atualizar as fontes é uma alteração de código intencional que pode ser testada e revisada, e não uma alteração invisível do lado do servidor que altera o mapa de alguém da noite para o dia.

Um banco de dados SQLite deliberadamente simples.

O primeiro Gazetteer continha 252 países, 3,861 regiões, 33,744 cidades e 4,564 aeroportos, em aproximadamente 14 MB. Ele utilizou a biblioteca SQLite já fornecida pelo sistema operacional e uma pequena camada local em vez de adicionar um framework de banco de dados maior.

O esquema é intencionalmente direto. Os continentes contêm países. Os países contêm regiões. As regiões contêm cidades. Os aeroportos têm códigos de país e coordenadas. Os identificadores de origem estáveis se tornam os identificadores armazenados com uma marca Mapsake: ISO alpha-2 para um país, um código de administrador GeoNames para uma região, um ID GeoNames para uma cidade e um código IATA para um aeroporto.

Mapsake também desnormaliza o nome legível por humanos e a genealogia em cada marca salva. Essa duplicação é útil. Um registro de viagem pessoal deve permanecer legível se um gazetteer posterior renomear um local, remover um registro ou não estiver disponível durante uma exportação. O identificador serve para correspondência; o instantâneo mantém os dados do usuário autocontidos.

O SQLite é adequado para essa carga de trabalho porque o banco de dados é gerado uma vez e consultado muitas vezes. Ele suporta índices, transações durante a compilação e pesquisa de texto completo sem um processo de serviço. O aplicativo abre o arquivo incluído apenas para leitura, portanto, não há risco de migração para os dados de referência e não há possibilidade de que uma gravação interrompida o corrompa.

A pesquisa é mais do que 'contém(texto)'

A marcação manual começa com um único campo de pesquisa que abrange continentes, países, regiões, cidades e aeroportos. Uma pesquisa por "san" deve encontrar cidades relevantes antes de registros obscuros; "LAX" deve encontrar o aeroporto; e um nome digitado sem seus acentos deve funcionar.

O script de compilação cria uma tabela FTS5 com nomes de exibição, nomes alternativos selecionados, códigos, ascendência, coordenadas, tipo e um valor de importância. O tokenizador Unicode remove os diacríticos para correspondência. No momento da consulta, o Mapsake normaliza maiúsculas e minúsculas e diacríticos, remove caracteres que poderiam se tornar sintaxe de texto completo, adiciona uma correspondência de prefixo a cada token e classifica os nomes exatos antes dos prefixos e correspondências gerais.

A importância resolve os empates restantes. Continentes e países não devem desaparecer abaixo de vilas com nomes semelhantes. A população de uma cidade dá um peso razoável aos locais importantes. Aeroportos grandes são classificados acima de aeroportos pequenos quando a correspondência de texto é, de outra forma, comparável.

Os nomes alternativos são intencionalmente limitados. O GeoNames pode fornecer uma lista muito longa e multilíngue para um local popular. Copiar cada ortografia no índice do dispositivo adicionaria ruído e tamanho. O construtor mantém um conjunto limitado e desduplicado de variantes úteis e preserva o nome de exibição original separadamente de seu formulário de pesquisa dobrado.

Os resultados da pesquisa exibem o mesmo modelo GazetteerPlace usado para a navegação hierárquica. Um usuário pode pesquisar diretamente ou navegar por continente, país, região e cidade sem criar dois sistemas geográficos que possam ser diferentes.

Linhas respondem a uma pergunta diferente de pontos.

O primeiro resolvedor de fotos escolheu a cidade mais próxima e herdou o país e a região dessa cidade. Em áreas densamente povoadas, isso geralmente parece perfeito. Perto de uma fronteira, pode estar errado de uma maneira que é difícil de notar.

Imagine uma foto tirada logo dentro de Montana, quando o lugar habitado mais próximo no banco de dados está do outro lado da fronteira, no Dakota do Norte. O cálculo da cidade mais próxima está funcionando corretamente, mas o resultado não é o local administrativo onde a foto foi tirada. O mesmo problema ocorre nas fronteiras internacionais, perto de enclaves e através da água, onde uma costa esparsa não tem um ponto habitado próximo.

A geometria da fronteira responde à pergunta se contém em vez de proximidade. O Mapsake decodifica os polígonos de países e administrações da Natural Earth-1, verifica quais anéis contêm a coordenada e usa esse resultado para proteger a atribuição de país e região. Em seguida, pode pesquisar a cidade mais próxima restrita ao país ou região do polígono.

Isso cria uma divisão de trabalho útil:

1. O confinamento por polígono estabelece a área administrativa.
2. A hierarquia do gazetteer fornece IDs e nomes estáveis.
3. Uma pesquisa de cidade próxima restrita fornece uma localização útil sem ultrapassar a linha que foi estabelecida.
4. Uma verificação de aeroporto próximo adiciona um aeroporto apenas dentro de uma distância deliberadamente limitada.

Nem os dados da linha nem o diretório de locais são suficientes por si só. Juntos, transformam uma coordenada em uma cadeia verificável.

A auditoria admin-1 revelou incompatibilidades sistêmicas.

Os polígonos de países e os polígonos de regiões vieram de diferentes camadas da Natural Earth, e os identificadores da camada de regiões nem sempre correspondiam aos da GeoNames. Alguns erros eram óbvios, enquanto outros produziam preenchimentos plausíveis, mas incorretos.

Durante uma conversão inicial, a geometria de New Brunswick foi atribuída a Quebec. Outros recursos não tinham um código, tinham um código de um sistema vizinho ou representavam uma unidade administrativa de forma diferente do diretório. Um olhar visual para o mapa do mundo não conseguia encontrar todos esses erros de forma confiável.

O mecanismo de substituição trata as cidades como uma fonte de oráculo. Para cada polígono candidato, ele pergunta a qual região do Gazetteer pertencem as cidades que realmente estão dentro dele. Os códigos Natural Earth existentes são validados em vez de serem usados cegamente. Os recursos que não passam na validação podem ser realocados espacialmente, divididos ou excluídos. A saída gerada usa então os IDs de região exatos que já estão presentes no SQLite.

Isso é uma forma prática de teste entre conjuntos de dados. Um polígono que afirma ser uma região deve conter uma amostra convincente de cidades que afirmam ser a mesma região. Quando as duas fontes não concordam, o sistema gera evidências em vez de escolher silenciosamente o valor que foi carregado primeiro.

A mesma auditoria encontrou casos especiais, como dependências habitadas incluídas na geometria de um país. O Mapsake corrige um pequeno número desses casos para que uma foto possa ser resolvida para o mesmo país que o Gazetteer e as configurações de contagem de países entendem.

Linhas mais nítidas sem enviar o mundo no tamanho original.

A primeira versão utilizou a camada de países de 1:110 milhões da Natural Earth. Era compacta e rápida, mas as linhas costeiras ficaram visivelmente grosseiras quando o Mapsake adicionou mapas mais detalhados, histórias de lugares e vistas regionais.

O mapa foi posteriormente movido para a camada 1:10 milhões. Essa fonte é muito mais detalhada, portanto, incluir e renderizar sem alterações aumentaria o armazenamento, o tempo de decodificação, a construção da sobreposição e o trabalho de recoloração. O processo de compilação simplifica cada anel usando Douglas-Peucker com uma tolerância de aproximadamente 0.004 graus, e então arredonda as coordenadas para uma precisão estável.

O arquivo de país resultante tem aproximadamente 6.5 MB. Ele mantém detalhes úteis da costa nos níveis de zoom que o Mapsake exibe, removendo os vértices que cairiam efetivamente nos mesmos pixels. A geometria Admin-1 passa por um caminho semelhante de validação e simplificação.

A simplificação tem uma restrição de correção: um polígono menor deve tomar as mesmas decisões para as coordenadas reais das fotos. Os conjuntos de dados de referência posteriores colocam intencionalmente pontos ao redor das bordas e comparam a detecção de impacto otimizada com uma referência fixa. Linhas mais rápidas são úteis apenas se ainda responderem à mesma pergunta de contenção.

Expandindo de 34,000 para 234,000 cidades.

O primeiro banco de dados utilizou cidades do GeoNames com populações acima de 15,000. Isso manteve o pacote compacto, mas deixou viagens em áreas rurais, pequenas ilhas, cidades de caminhada e muitos locais residenciais com um rótulo desnecessariamente distante.

Mapsake posteriormente adotou GeoNames. cidades500, abrangendo lugares habitados com aproximadamente 500 pessoas, além de sedes administrativas. A tabela de cidades cresceu em aproximadamente sete vezes, para cerca de 234,000 registros, e o banco de dados incluído cresceu de aproximadamente 14 MB para aproximadamente 69 MB.

Essa troca foi feita após a remoção do App Clip. O limite de download do Clip havia sido a razão mais forte para restringir o banco de dados. Depois que o aplicativo principal foi o único consumidor, uma melhor cobertura foi mais valiosa do que preservar um limite artificial para pequenas cidades.

O índice de texto completo continua seletivo em relação aos nomes alternativos de locais menores, e a navegação por região ainda limita o que é renderizado de cada vez. Os dados podem ser amplos sem exigir que cada tela materialize toda a tabela.

A cobertura é mais importante onde um geocodificador de rede seria menos confiável. Uma pequena cidade em uma viagem remota não deve ser rotulada como uma cidade a horas de distância simplesmente porque o conjunto de dados compacto a omitiu.

A busca pela cidade mais próxima se tornou um problema de desempenho compartilhado.

A consulta original da cidade mais próxima ampliava uma caixa de latitude e longitude, solicitava ao SQLite que calculasse uma distância ponderada para cada candidato, criava uma classificação temporária e retornava a linha mais próxima. Isso era fácil de entender e suficientemente preciso, mas uma biblioteca de fotos 82,000 transformou um pequeno custo por consulta em segundos de trabalho repetitivo durante as importações, as memórias, a derivação do mapa e Constellations.

A primeira melhoria adicionou uma sonda estreita de 0.4 grau antes de usar opções mais amplas. Localizações densas geralmente encontravam uma cidade de um conjunto de candidatos muito menor. A memorização e um cache persistente de células geográficas também impediram que fotos próximas repetissem o mesmo trabalho.

A melhoria mais significativa carrega as coordenadas numéricas das cidades 234,000 em um índice na memória ordenado por latitude. Uma pesquisa binária encontra a fatia dentro da janela de latitude atual, um loop limitado verifica a longitude e a distância ponderada, e apenas a linha vencedora é recuperada do SQLite. Um pequeno cache de registros mantém os vencedores repetidos baratos.

O comportamento de ajuste automático não mudou. A função otimizada ainda escolhe a cidade mais próxima dentro da primeira área de pesquisa não vazia, incluindo uma resolução determinística de empates. Uma cópia de referência do antigo código SQL verifica centenas de coordenadas próximas das fronteiras para uma equivalência de ID exata.

No simulador, o tempo médio para a derivação da cidade mais próxima caiu de 2.11 segundos para 5.2 milissegundos. Em um iPhone físico, o tempo caiu de 3.06 segundos para 6.35 milissegundos. Esses ganhos permitiram várias funcionalidades porque o diretório geográfico é uma infraestrutura compartilhada em vez de um detalhe de implementação privado da tela de importação.

Polígonos sobrepostos encontraram um bug de correção.

O mecanismo de verificação de desempenho detectou um bug que existia antes da otimização. Alguns polígonos admin-1 se sobrepõem intencionalmente, especialmente as regiões de capitais dentro de uma região circundante. Berlim e Brandemburgo, Seul e Gyeonggi, e a cidade de Kiev e sua oblast são exemplos.

O teste de colisão original aceitava o polígono correspondente que aparecia primeiro em um dicionário Swift. A ordem de iteração de um dicionário muda entre os processos, portanto, a mesma coordenada pode adquirir uma região diferente após reiniciar o aplicativo.

Mapsake agora classifica os candidatos sobrepostos pela área do polígono e permite que o recurso mais pequeno e específico vença. A implementação de referência segue a mesma regra. Uma foto de referência 82,000 deve produzir zero diferenças entre os caminhos de derivação a frio e a quente antes que uma otimização da geometria seja aceita.

Este bug é um bom lembrete de que "dentro de um polígono" nem sempre é uma pergunta de sim ou não. Os dados geográficos contêm enclaves, capitais aninhados, cruzamentos de antimeridianos, multipolígonos, buracos, fronteiras disputadas e convenções de origem. Uma política determinística é tão importante quanto o algoritmo de ponto dentro do polígono.

O modo offline é uma funcionalidade de privacidade e uma funcionalidade do produto.

A importação de fotos da Mapsake pode processar uma grande biblioteca sem enviar suas coordenadas para um serviço de geocodificação de terceiros. Isso protege locais de viagem e residenciais confidenciais, elimina a cobrança por solicitação, evita a limitação de taxa e torna o progresso previsível.

Isso também mantém a edição coerente. Busca manual, importação de fotos, cartões do Passport, conquistas, instantâneos de Amigos, correspondência de carimbos e histórias de lugares usam a mesma linguagem porque compartilham IDs de lugar estáveis. Um aeroporto importado de um registro de voo pode ser deduplicado com o mesmo aeroporto detectado perto de uma foto. Uma cidade encontrada na busca pode corresponder à cidade usada pelo Then & Now.

Este pacote não é tratado como perfeito ou permanente. Os atributos de origem são visíveis no aplicativo. Os scripts de compilação são mantidos junto com o código. As correções conhecidas são explícitas. Os elementos de referência protegem o comportamento em coordenadas difíceis. A atualização do mundo geográfico é um evento de lançamento com consequências verificáveis.

O que eu manteria se o reconstruísse

As opções mais duráveis não eram algoritmos individuais. Eram os limites das responsabilidades:

• Use pontos para nomes, identidades estáveis, pesquisa e hierarquia.
• Use linhas e polígonos para o contorno.
• Gere um artefato de produto somente leitura em vez de analisar quatro formatos de origem em um telefone.
• Salve um instantâneo legível com os dados do usuário, mantendo o ID de origem para correspondência.
• Faça com que o caminho de acesso offline habitual seja determinístico antes de acelerá-lo.
• Mantenha uma implementação de referência lenta por tempo suficiente para provar que a saída otimizada é equivalente.

O gazetteer começou como um recurso de pesquisa inicial. Tornou-se um dos sistemas fundamentais da Mapsake, porque quase todos os recursos mais avançados precisam responder à mesma pergunta simples: qual é este lugar?

Para obter a resposta correta, é preciso aceitar que a geografia não é um único banco de dados ou uma consulta inteligente. É um acordo cuidadoso entre nomes, pontos, linhas, regras do produto e o roteiro que uma pessoa espera reconhecer.

• Veja como o Mapsake cria um mapa de viagens a partir de fotos.
• Explore as importações de histórico de viagens suportadas.
• Saiba mais sobre o modelo de privacidade local do Mapsake.