Format d'algorithme des polylignes encodées

L'encodage des polylignes est 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 pouvez également utiliser l'utilitaire d'encodage de polylignes interactif.

Le processus d'encodage convertit une valeur binaire en une série de codes de caractères ASCII à l'aide du schéma d'encodage familier base64: pour garantir un affichage correct de ces caractères, les valeurs encodées sont additionnées à 63 (le caractère ASCII '?#39;) avant de les convertir en ASCII. L'algorithme recherche également des codes de caractères supplémentaires pour un point donné en vérifiant le bit le moins significatif de chaque groupe d'octets. Si ce bit est défini sur 1, le point n'est pas encore complètement formé et des données supplémentaires doivent suivre.

De plus, pour économiser de l'espace, les points n'incluent que le décalage par rapport au point précédent (à l'exception du premier point, bien sûr). Tous les points sont encodés en Base64 sous forme d'entiers signés, les latitudes et les longitudes étant des valeurs signées. Le format d'encodage dans une polyligne doit représenter deux coordonnées représentant la latitude et la longitude avec une précision raisonnable. Avec une longitude maximale de +/- 180 degrés et une précision de 5 décimales (entre 180 et -180,00000), il est nécessaire d'utiliser un nombre entier signé de 32 bits.

Notez que la barre oblique inverse est interprétée comme un caractère d'échappement dans les littéraux de chaîne. Toute sortie de cet utilitaire doit convertir les barres obliques inverses en doubles barres obliques inverses 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. Inversez les limites
  4. Décalez la valeur binaire vers la gauche d'un trait:
    11111101 11011010 10111100 00011110
  5. Si la valeur décimale initiale est négative, inversez cet encodage:
    00000010 00100101 01000011 11100001
  6. Scindez la valeur binaire en plusieurs parties de 5 bits (à partir de la droite) :
    00001 00010 01010 10000 11111 00001
  7. Inversez l'ordre des fragments de 5 bits:
    00001 11111 10000 01010 00010 00001
  8. OU chaque valeur avec 0x20 si un autre fragment de bit se trouve comme suit :
    100001 111111 110000 101010 100010 000001
  9. Convertissez chaque valeur en décimal:
    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 présente quelques exemples de points encodés, avec les encodages sous 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`@