Polyline encode obtient une lat/lng incorrecte après le décodage

Question

Nous utilisons l'algorithme de décodage Polyline de Google pour décoder nos coordonnées. Mais dans notre cas, la plupart des coordonnées sont incorrectes après décodage. Nous avons également testé le processus avec une plus grande précision.

Voici notre code et aussi nos journaux pour vérifier que les coordonnées sont incorrectes:

let coordinates = [ [lat, lng], [...], ...];
console.log(coordinates[13347]); // Sortie: [ 13.44668, 52.47429 ]
let encoded = Polyline.encode(coordinates);
let decoded = Polyline.decode(encoded);
console.log(decoded[13347]); // Sortie: [ 13.44671, 52.47445 ]
console.log(coordinates.length == decoded.length)// true

Dans ce cas, la distance est de 20 mètres, ce qui est beaucoup. D'autres points ont des distances de 150 mètres ou même plus.

Dans mon tableau de coordonnées, il y a environ 250 000 coordonnées que nous voulons décoder.

Est-ce que j'oublie quelque chose pour que le processus de décodage/codage échoue autant ?

Answer 1

TL;DR Ajoutez les lignes suivantes après la déclaration de la variable coordinates :

coordinates = coordinates.map(
    pair => { return [pair[0].toFixed(5), pair[1].toFixed(5)]; }
);

---

Réponse complète

Il semble que vous rencontriez des erreurs d'arrondi des nombres à virgule flottante. Probablement, la bibliothèque que vous utilisez a une implémentation incorrecte de l'algorithme d'encodage de polyligne.

Dans la description de l'algorithme, il est indiqué que la chaîne encodée générée par l'algorithme stocke les différences entre les coordonnées consécutives en utilisant des nombres à précision fixe (avec 5 décimales). Il est donc important d'arrondir la latitude et la longitude à 5 décimales avant de calculer les différences. Sans cette étape, les erreurs d'arrondi peuvent s'accumuler. Dans le pire des cas, l'erreur peut augmenter d'environ 0,000005 degré pour chaque élément suivant de la liste encodée.

L'implémentation officielle de l'algorithme n'introduit pas d'erreurs d'arrondi accumulées. Cependant, l'implémentation trouvée dans NPM (package polyline) donne des résultats incorrects qui indiquent l'arrondi invalide des nombres.

Veuillez consulter les exemples ci-dessous :

Exemple 1. Encodage d'une polyligne en utilisant l'implémentation officielle de l'algorithme

(en utilisant google.maps.geometry.encoding.encodePath de l'API JavaScript Google Maps)

originalList = [];
for (var i = 0; i < 100; ++i) 
    originalList.push(
        new google.maps.LatLng(6 * i / 1000000, 0)
    );
// originalList ressemble à: [[0.000000,0],[0.000006,0],[0.000012,0],[0.000018,0], ..., [0.000594,0]];
// (mais avec des objets LatLng au lieu de tableaux à 2 éléments)

console.log(originalList[99].lat()) // 0.000594

var encodedList = google.maps.geometry.encoding.encodePath(originalList)
var decodedList = google.maps.geometry.encoding.decodePath(encodedList)

console.log(decodedList[99].lat())  // 0.00059

Exemple 2. Encodage d'une polyligne en utilisant package polyline de NPM

let Polyline = require('polyline');

var originalList = [];
for (var i = 0; i < 100; ++i) 
    originalList.push(
        [6 * i / 1000000, 0]
    );
// encore une fois : originalList == [[0.000000,0],[0.000006,0],[0.000012,0],[0.000018,0], ..., [0.000594,0]];

console.log(originalList[99][0]) // 0.000594

var encodedList = Polyline.encode(originalList);
var decodedList = Polyline.decode(encodedList);

console.log(decodedList[99][0])  // 0.00099

Résultat invalide : les valeurs 0.000594 et 0.00099 diffèrent de plus de 0.000005.

Correction possible

La bibliothèque que vous utilisez ne doit probablement pas arrondir les coordonnées avant de calculer les différences. Par exemple, lorsque deux points consécutifs ont des latitudes 0.000000 et 0.000006, la différence est 0.000006 et elle est arrondie à 0.00001, entraînant une erreur de 0.000004. Vous pouvez arrondir les coordonnées manuellement avant de les passer à Polyline.encode(), par exemple en utilisant la fonction .toFixed(5):

let Polyline = require('polyline');

var originalList = [];
for (var i = 0; i < 100; ++i) 
    originalList.push(
        [(6 * i / 1000000).toFixed(5), 0]
    );
// avant l'arrondi : [[ 0.000000,0],[ 0.000006,0],[ 0.000012,0],[ 0.000018,0], ..., [ 0.000594,0]];
// après l'arrondi :  [['0.00000',0],['0.00001',0],['0.00001',0],['0.00002',0], ..., ['0.00059',0]];

console.log(originalList[99][0]) // 0.00059

var encodedList = Polyline.encode(originalList);
var decodedList = Polyline.decode(encodedList);

console.log(decodedList[99][0])  // 0.00059

Answer 2

L'encodage de polyligne est perte de données:

https://developers.google.com/maps/documentation/utilities/polylinealgorithm (L'encodage de polyligne est un algorithme de compression *perte* qui vous permet de stocker une série de coordonnées sous forme d'une seule chaîne de caractères

Et si vous utilisiez votre propre schéma d'encodage? La page ci-dessus montre également le schéma d'encodage utilisé par Google. Peut-être pouvez-vous chercher un compromis entre l'espace et la précision.