折线编码解码后得到错误的后期/液化天然气

Question

我们正在使用Google的Polyline解码算法来解码我们的坐标。但在我们的情况下，解码后大多数坐标都是错误的。我们还对这一过程进行了更精确的测试。

这是我们的代码，也是我们的日志来测试坐标是否错误:

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

在这种情况下，距离是20米，这是一个很大的距离。其他点的距离如150米甚至更远。

在我的坐标数组中有大约250.000个我们想要解码的坐标。

我是否错过了一些东西，所以解码/编码过程失败了?

Answer 1

TL;DR在coordinates变量声明之后添加以下行:

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

---

完整的答案

看起来你在处理浮点舍入误差。可能您使用的库对Polyline编码算法有不正确的实现。

在算法的描述中，我们读到算法生成的编码字符串使用固定精度的数字(有5位小数)存储连续坐标之间的差异。因此，在计算差异之前，将经纬度四舍五入到小数点后5位是很重要的。如果没有这一步，舍入误差可能会累积。在最坏的情况下，对于编码列表中的每个后续项目，错误可能增加约0.000005度。

该算法的官方实现没有引入累积舍入误差。然而，在NPM(包折线)中找到的实现给出了不正确的结果，表明数字四舍五入无效。

请看下面的例子:

示例1。使用算法的官方实现编码折线

(使用google.maps.geometry.encoding.encodePath从谷歌地图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

2的例子。使用NPM

中的包polyline编码折线

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

无效结果:值0.000594与0.00099相差大于0.000005.

可能修复

您正在使用的库可能在计算差值之前没有将坐标舍入。例如，当两个连续点的纬度分别为0.000000和0.000006时，差值为0.000006，舍入为0.00001，误差为0.000004。在将坐标传递给Polyline.encode()之前，您可能需要手动四舍五入。使用函数.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

折线编码有损:

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

)

如何使用自己的编码方案?上面的页面还显示了Google使用的编码方案。也许您可以在空间和准确性之间寻找折衷。