decode yields higher precision coordinates

[Fischerfredl]

Hi all,

we use a copied version of https://github.com/heremaps/flexible-polyline/blob/master/javascript/index.js in our codebase and I just noticed that the decode function returns higher precision values than expected (more decimal places). I guess this happens due to the assumption that adding two numbers of a certain order won't generate a lower order. But this is not true for IEEE 754 Floating-Point Arithmetic. Classic example:

16:39 $ node
Welcome to Node.js v16.14.0.
Type ".help" for more information.
> 0.1 + 0.2
0.30000000000000004
> 

I stumbled upon this as another library (polygon-clipping) was generating erroneous MultiPolygons when it was fed Polygons with the high precision. The following patch fixed this for us:

--- a/index.js
+++ b/index.js
@@ -33,6 +33,8 @@ function decode(encoded) {

   const factorDegree = 10 ** header.precision
   const factorZ = 10 ** header.thirdDimPrecision
+  const truncateDegree = num => Math.round(num * factorDegree) / factorDegree
+  const truncateZ = num => Math.round(num * factorZ) / factorZ
   const { thirdDim } = header

   let lastLat = 0
@@ -50,10 +52,10 @@ function decode(encoded) {
     if (thirdDim) {
       const deltaZ = toSigned(decoder[i + 2]) / factorZ
       lastZ += deltaZ
-      res.push([lastLat, lastLng, lastZ])
+      res.push([truncateDegree(lastLat), truncateDegree(lastLng), truncateZ(lastZ)])
       i += 3
     } else {
-      res.push([lastLat, lastLng])
+      res.push([truncateDegree(lastLat), truncateDegree(lastLng)])
       i += 2
     }
   }

This works for us as we only read Polylines from a third party API (HERE Isoline API) but I don't know if this is sufficient for a encoding/decoding setting. Maybe one should truncate the lastLat/lastLng/lastZ as you go for performance.

I just wanted to leave this here for a heads up if anyone stumbles upon a similar error.

[VeaaC]

The thing is: You cannot produce floating point numbers of a specific precision, there is always some addition inaccuracies guaranteed by the representation (even without additions). E.g. it is impossible to represent 0.3 with or without additions. The only way to get rid of that is converting to fixed-point / integers.

That being said: The implementation should actually delay the division after it has added up the delta. The delta-sum should not contain accumulated/addition division error.

[haifeng2013]

A PR is created to fix the precision loss and/or accumulated division error by delaying the devision after sum of coordinates as suggested by @VeaaC https://github.com/heremaps/flexible-polyline/pull/84