Formato do algoritmo de polilinha codificada

Mantenha tudo organizado com as coleções Salve e categorize o conteúdo com base nas suas preferências.

A codificação de polilinhas é um algoritmo de compactação com perdas que permite armazenar uma série de coordenadas como uma única string. Coordenadas de pontos são codificadas usando valores com sinal. Se você tiver apenas alguns pontos estáticos, use o utilitário de codificação de polilinha interativa.

O processo de codificação converte um valor binário em uma série de códigos de caracteres para caracteres ASCII usando o conhecido esquema de codificação base64: para garantir a exibição adequada desses caracteres, os valores codificados são somados com 63 (o caractere ASCII '?') antes de convertê-los em ASCII. O algoritmo também verifica outros códigos de caractere de um determinado ponto, verificando a parte menos significativa de cada grupo de bytes. Se esse bit estiver definido como 1, o ponto ainda não estará totalmente formado e será necessário acompanhar outros dados.

Além disso, para economizar espaço, os pontos incluem apenas o deslocamento do ponto anterior (exceto para o primeiro ponto). Todos os pontos são codificados em Base64 como números inteiros com sinal, já que as latitudes e longitudes são valores assinados. O formato de codificação em uma polilinha precisa representar duas coordenadas que representam a latitude e a longitude com uma precisão razoável. Considerando uma longitude máxima de +/- 180 graus a uma precisão de 5 casas decimais (180.00000 a -180.00000), surge a necessidade de um valor inteiro binário assinado de 32 bits.

A barra invertida é interpretada como um caractere de escape em literais de string. Qualquer saída desse utilitário precisa converter os caracteres de barra invertida em barras invertidas duplas em literais de string.

Os passos para codificar um valor com sinal estão especificados abaixo.

  1. Veja o valor inicial assinado:
    -179.9832104
  2. Use o valor decimal e multiplique-o por 1e5, arredondando o resultado:
    -17998321
  3. Converta o valor decimal para binário. Observe que um valor negativo precisa ser calculado usando o complemento de dois e três invertendo o valor binário e adicionando um ao resultado:
  4. Desloque o valor binário um pouco para a esquerda:
    11111101 11011010 10111100 00011110
  5. Se o valor decimal original for negativo, inverta esta codificação:
    00000010 00100101 01000011 11100001
  6. Divida o valor binário em blocos de 5 bits (a partir do lado direito):
    00001 00010 01010 10000 11111 00001
  7. Coloque os blocos de 5 bits em ordem inversa:
    00001 11111 10000 01010 00010 00001
  8. OU cada valor com 0x20 se houver outra parte de bits:
    100001 111111 110000 101010 100010 000001
  9. Converta cada valor em decimal:
    33 63 48 42 34 1
  10. Adicione 63 a cada valor:
    96 126 111 105 97 64
  11. Converta cada valor para o equivalente em ASCII:
    `~oia@

A tabela abaixo mostra alguns exemplos de pontos codificados, mostrando as codificações como uma série de deslocamentos de pontos anteriores.

Exemplo

Pontos: (38.5, -120.2), (40.7, -120.95), (43.252, -126.453)

Latitude Longitude Latitude em E5 Longitude em E5 Mudança na latitude Mudança na longitude Latitude codificada Longitude codificada Ponto codificado
38.5 -120.2 3850000 -12020000 +3850000 -12020000 _p~iF ~ps|U _p~iF~ps|U
40.7 -120.95 4070000 -12095000 +220000 -75000 _ulL nnqC _ulLnnqC
43.252 -126.453 4325200 -12645300 +255200 -550300 _mqN vxq`@ _mqNvxq`@

Polilinha codificada: _p~iF~ps|U_ulLnnqC_mqNvxq`@