Formato do algoritmo de polilinhas codificadas

A codificação de polilinha é um algoritmo de compactação com perda que permite armazenar uma série de coordenadas como uma única string. Coordenadas de pontos são codificadas usando valores com sinal. Se você tem apenas alguns pontos estáticos, também convém usar o utilitário interativo de codificação de polilinhas.

O processo de codificação converte um valor binário em uma série de códigos 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 caracteres para um determinado ponto, verificando o bit menos significativo de cada grupo de bytes. Se esse bit estiver definido como 1, o ponto ainda não está totalmente formado e outros dados precisarão ser seguidos.

Além disso, para economizar espaço, os pontos incluem apenas o deslocamento em relação ao ponto anterior (exceto, é claro, 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 com sinal. O formato de codificação dentro de 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 para uma precisão de cinco casas decimais (180.00000 a -180.00000), isso resulta na necessidade de um valor inteiro binário assinado de 32 bits.

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

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

1. Use o valor com sinal inicial:
   -179.9832104
2. Multiplique o valor decimal por 1e5, arredondando o resultado:
   -17998321
3. Converta o valor decimal para binário. Um valor negativo precisa ser calculado usando o complemento de dois, invertendo o valor binário e adicionando um ao resultado:
   

   00000001 00010010 10100001 11110001
   11111110 11101101 01011110 00001110
   11111110 11101101 01011110 00001111
   

4. Desloque o valor binário um bit 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 (começando do lado direito):
   00001 00010 01010 10000 11111 00001
7. Coloque os blocos de 5 bits na ordem inversa:
   00001 11111 10000 01010 00010 00001
8. OU cada valor com 0x20 se outro bloco de bits seguir:
   100001 111111 110000 101010 100010 000001
9. Converta cada valor para 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, exibindo as codificações como uma série de deslocamentos em relação aos pontos anteriores.