Polyline encode gets wrong lat/lng after decoding

Question

We are using Google's Polyline decoding algorithm to decode our coordinates. But in our case the most coordinates are wrong after decoding it. We have also tested the process with a deeper precision.

This is our code and also our logs to test that the coordinates are wrong:

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

In this case the distance is 20 meters which is a lot. Other points have distances like 150 meter or even more.

In my coordinates array are around 250.000 coordinates which we want to decode.

Am I missing something so the decode/encode process fails this hard ?

Answer 1

TL;DR Add the following lines after the declaration of the coordinates variable:

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

---

Full answer

It looks like you're dealing with floating point rounding errors. Probably the library you use has incorrect implementation of the Polyline encoding algorithm.

In the description of the algorithm we read that the encoded string generated by the algorithm stores the differences between consecutive coordinates using fixed-precision numbers (with 5 decimal places). Therefore it is important to round the latitude and longitude to 5 decimal places before computing the differences. Without that step, the rounding errors may accumulate. In the worst case error may increase by about 0.000005 deg for each subsequent item in the encoded list.

The official implementation of the algorithm does not introduce accumulated rounding errors. However, the implementation found in NPM (package polyline) gives incorrect results that indicate the invalid rounding of numbers.

Please look at the examples bellow:

Example 1. Encoding a polyline using official implementation of the algorithm

(using google.maps.geometry.encoding.encodePath from the Google Maps JavaScript API)

originalList = [];
for (var i = 0; i < 100; ++i) 
    originalList.push(
        new google.maps.LatLng(6 * i / 1000000, 0)
    );
// originalList looks like: [[0.000000,0],[0.000006,0],[0.000012,0],[0.000018,0], ..., [0.000594,0]];
// (but with LatLng objects instead of 2-element arrays)

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

Example 2. Encoding a polyline using package polyline from NPM

let Polyline = require('polyline');

var originalList = [];
for (var i = 0; i < 100; ++i) 
    originalList.push(
        [6 * i / 1000000, 0]
    );
// again: 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

Invalid result: the values 0.000594 and 0.00099 differ by more than 0.000005.

Possible fix

The library that you're using probably doesn't round the coordinates before computing the differences. For example when two consecutive points have latitudes 0.000000 and 0.000006, the difference is 0.000006 and it is rounded to 0.00001 giving error of 0.000004. You may want to round the coordinates manually, before passing them to Polyline.encode(), eg. using the function .toFixed(5):

let Polyline = require('polyline');

var originalList = [];
for (var i = 0; i < 100; ++i) 
    originalList.push(
        [(6 * i / 1000000).toFixed(5), 0]
    );
// before rounding: [[ 0.000000,0],[ 0.000006,0],[ 0.000012,0],[ 0.000018,0], ..., [ 0.000594,0]];
// after rounding:  [['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

Polyline encoding is lossy:

https://developers.google.com/maps/documentation/utilities/polylinealgorithm (Polyline encoding is a *lossy* compression algorithm that allows you to store a series of coordinates as a single string

How about using your own encoding scheme? The page above also shows the encoding scheme used by Google. Perhaps you can look for a trade-off between space and accuracy.