Formato do algoritmo de polilinhas codificadas

A codificação de polilinhas é 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 pode usar a função utilitário de codificação de polilinhas.

O processo de codificação converte um valor binário em uma série de códigos de caracteres para Caracteres ASCII que usam o conhecido esquema de codificação base64: para garantir a exibição correta desses caracteres, os valores codificados são somados com 63 (o caractere ASCII "?") antes de convertê-los em ASCII. O algoritmo também verifica se há 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 estará totalmente formado e dados adicionais devem ser seguidos.

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

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

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

1. Use o valor inicial assinado:
   -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 seu 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 à 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 pelo lado direito):
   00001 00010 01010 10000 11111 00001
7. Posicione os pedaços de 5 bits na ordem inversa:
   00001 11111 10000 01010 00010 00001
8. OU cada valor com 0x20 se houver outro bloco 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 ASCII:
    `~oia@

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