Formato del algoritmo de polilínea codificada

El algoritmo de codificación de polilínea es un algoritmo de compresión con pérdida que te permite almacenar una serie de coordenadas como una sola string. Las coordenadas de punto se codifican usando valores firmados. Si solo tienes algunos puntos estáticos, es posible que también desees usar la utilidad de codificación de polilínea interactiva.

El proceso de codificación convierte un valor binario en una serie de códigos de caracteres para caracteres ASCII usando el esquema de codificación conocido base64: para garantizar que estos caracteres se muestren de manera apropiada, los valores codificados se suman con 63 (el carácter ASCII “?”) antes de convertirse en ASCII. El algoritmo también comprueba códigos de caracteres adicionales para un punto dado verificando el bit menos significativo de cada grupo de bytes. Si este bit se fija en 1, el punto todavía no estará completamente formado y se deberán aplicar datos adicionales.

A su vez, para conservar el espacio, los puntos solo incluyen el desplazamiento desde el punto previo (excepto, por supuesto, para el primer punto). Todos los puntos se codifican en Base64 como valores enteros firmados, ya que las latitudes y las longitudes son valores firmados. El formato de codificación dentro de una polilínea debe representar dos coordenadas que representan la latitud y la longitud con una precisión razonable. Dada una longitud máxima de +/- 180 grados con una precisión de 5 lugares decimales (180,00000 a -180,00000), como resultado se necesita un valor entero binario firmado de 32 bits.

Ten en cuenta que la barra invertida se interpreta como un carácter de escape dentro de los literales de string. Cualquier salida de esta utilidad debe convertir los caracteres de la barra invertida en barras invertidas dobles dentro de los literales de string.

A continuación, se especifican aspectos de codificación como los valores firmados.

  1. Toma el valor inicial firmado:
    -179,9832104
  2. Toma el valor decimal y multiplícalo por 1e5. Redondea el resultado:
    -17998321
  3. Convierte el valor decimal en binario. Ten en cuenta que un valor negativo se debe calcular usando su complemento de dos invirtiendo el valor binario y agregando uno al resultado:
    00000001 00010010 10100001 11110001
    11111110 11101101 01011110 00001110
    11111110 11101101 01011110 00001111
  4. Desplaza el valor binario un bit a la izquierda:
    11111101 11011010 10111100 00011110
  5. Si el valor decimal original es negativo, invierte esta codificación:
    00000010 00100101 01000011 11100001
  6. Divide el valor binario en fragmentos de 5 bits (comenzando desde la derecha):
    00001 00010 01010 10000 11111 00001
  7. Ubica los fragmentos de 5 bits en el orden inverso:
    00001 11111 10000 01010 00010 00001
  8. De manera alternativa, cualquier valor con 0x20 si sigue otro fragmento de bit:
    100001 111111 110000 101010 100010 1
  9. Convierte cada valor en un decimal:
    33 63 48 42 34 1
  10. Agrega 63 a cada valor:
    96 126 111 105 97 64
  11. Convierte cada valor a su equivalente ASCII:
    `~oia@

En la siguiente tabla, se muestran algunos ejemplos de puntos codificados en los que se presenta la codificación como una serie de desplazamientos respecto de puntos previos.

Ejemplo

Puntos: (38,5, -120,2), (40,7, -120,95), (43,252, -126,453)



Latitud Longitud Latitud en E5 Longitud en E5 Cambio de latitud Cambio de longitud Latitud codificada Longitud codificada Punto 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`@

Polilínea codificada: _p~iF~ps|U_ulLnnqC_mqNvxq`@

Enviar comentarios sobre...