Formato do algoritmo de polilinha codificada

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

O processo de codificação converte um valor binário em uma série de códigos para caracteres ASCII usando o esquema de codificação familiar base64: para garantir a exibição correta desses caracteres, os valores codificados são somados com 63 (o caractere ASCII '?') antes de serem convertidos para ASCII. O algoritmo também verifica códigos de caracteres adicionais para um determinado ponto verificando o bit menos significado de cada grupo de bytes; se esse bit é 1, o ponto ainda não está totalmente formado e dados adicionais devem existir em seguida.

Além disso, para economizar espaço, pontos incluem somente o deslocamento em relação ao ponto anterior (exceto, é claro, o primeiro ponto). Todos os pontos são codificados em Base64 com inteiros com sinal, pois latitudes e longitudes são valores com sinal. O formato de codificação dentro de uma polilinha precisa representar duas coordenadas, que são latitude e longitude, com precisão razoável. Considerando uma longitude máxima de +/- 180 graus com precisão de 5 casas decimais (180.00000 a -180.00000), isso resulta na necessidade de um valor inteiro binário com sinal de 32 bits.

Observe que a barra invertida é interpretada como um caractere de escape dentro de literais de strings. Qualquer saída desse utilitário deve converter caracteres de barra invertida para 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 com sinal:
    -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 deve ser calculado usando seu 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 essa codificação:
    00000010 00100101 01000011 11100001
  6. Divida o valor binário em pedaços 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. Execute OR de cada valor com 0x20 se houver mais um pedaço de bits:
    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 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.

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`@

Enviar comentários sobre…