Format d'algorithme des polylignes encodées

L'encodage des polylignes repose sur un algorithme de compression avec perte qui vous permet de stocker une série de coordonnées sous la forme d'une chaîne unique. Les coordonnées des points sont encodées à l'aide de valeurs signées. Si vous n'avez que quelques points statiques, vous pourriez souhaiter utiliser l'utilitaire d'encodage interactif des polylignes.

Le processus d'encodage convertit une valeur binaire en une série de codes de caractères ASCII au moyen de l'encodage familier base64 : pour garantir l'affichage correct de ces caractères, la valeur 63 (le caractère ASCII « ? ») est ajoutée aux valeurs encodées avant de les convertir en caractères ASCII. L'algorithme recherche également des codes de caractères additionnels pour un point donné en vérifiant le bit le moins significatif pour chaque groupe d'octets ; si ce bit est défini sur 1, le point n'est pas encore entièrement formé et d'autres données doivent suivre.

Par ailleurs, afin d'économiser de la place, les points incluent uniquement le décalage par rapport au point précédent (à l'exception du premier point bien évidemment). Tous les points sont encodés en Base64 en tant que nombres entiers signés, de la même manière que les latitudes et les longitudes sont des valeurs signées. Le format d'encodage dans une polyligne doit représenter deux coordonnées donnant la latitude et la longitude avec une précision raisonnable. Étant donné que la longitude maximum est de +/- 180 degrés avec une précision de 5 chiffres après la virgule (c.-à-d. de 180.00000 à -180.00000), cela requiert une valeur de nombre entier binaire signée de 32 bits.

Notez que la barre oblique inversée est interprétée comme un caractère d'échappement dans les littéraux de chaîne. Toute sortie de cet utilitaire devrait convertir les barres obliques inversées en doubles barres obliques inversées dans les littéraux de chaîne.

Les étapes pour encoder une valeur signée sont indiquées ci-dessous.

  1. Prenez la valeur signée initiale :
    -179.9832104
  2. Prenez la valeur décimale et multipliez-la par 1e5, en arrondissant le résultat :
    -17998321
  3. Convertissez la valeur décimale en valeur binaire. Notez qu'une valeur négative doit être calculée en utilisant son complément à deux, c'est-à-dire en inversant la valeur binaire et en ajoutant la valeur 1 au résultat :
    00000001 00010010 10100001 11110001
    11111110 11101101 01011110 00001110
    11111110 11101101 01011110 00001111
  4. Décalez la valeur binaire d'un bit vers la gauche :
    11111101 11011010 10111100 00011110
  5. Si la valeur décimale d'origine est négative, inversez son encodage :
    00000010 00100101 01000011 11100001
  6. Décomposez la valeur binaire en groupes de 5 bits (en commençant par la droite) :
    00001 00010 01010 10000 11111 00001
  7. Inversez l'ordre des groupes de 5 bits :
    00001 11111 10000 01010 00010 00001
  8. Appliquez à chaque valeur l'opérande OR avec 0x20 si un autre groupe de bits se trouve à la suite :
    100001 111111 110000 101010 100010 000001
  9. Convertissez chaque valeur en décimales :
    33 63 48 42 34 1
  10. Ajoutez 63 à chaque valeur :
    96 126 111 105 97 64
  11. Convertissez chaque valeur en son équivalent ASCII :
    `~oia@

Le tableau ci-dessous propose quelques exemples de points encodés, en affichant les encodages sous la forme de décalages par rapport aux points précédents.

Exemple

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



Latitude Longitude Latitude en E5 Longitude en E5 Modification de la latitude Modification de la longitude Latitude encodée Longitude encodée Point encodé
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`@

Polyligne encodée : _p~iF~ps|U_ulLnnqC_mqNvxq`@

Envoyer des commentaires concernant…