9

一些谷歌地图产品具有折线的概念，就基础数据而言，它基本上只是一系列纬度/经度点，例如可能在地图上绘制的线中体现。Google 地图开发人员库使用编码的折线格式，该格式生成一个 ASCII 字符串，表示组成折线的点。然后，通常使用 Google 库的内置函数或由第三方编写的实现解码算法的函数对这种编码格式进行解码。

编码折线点的算法在编码折线算法格式文档中描述。没有描述的是以这种方式实现算法的基本原理，以及每个单独步骤的重要性。我很想知道以这种方式实现算法的想法/目的是否在任何地方公开描述。两个示例问题：

  • 某些步骤是否对压缩有可量化的影响？这种影响如何随着点之间的增量而变化？
  • 使用 ASCII 63 对值求和是某种兼容性黑客吗？

但一般来说，与算法一起的描述解释了为什么算法以这种方式实现。

4

1 回答 1

4

更新： James Snook 的这篇博客文章也有“有效的 ascii”范围参数，并且在逻辑上阅读了我想知道的其他步骤。例如，在存储之前左移，将负位作为第一位。

我发现了一些解释，不确定是否一切都是 100% 正确的。

  • 一个双精度值存储在多个 5 位块中，并且 0x20（二进制“0010 0000”）用于指示下一个 5 位条目属于当前双精度。
  • 0x1f（二进制'0001 1111'）用作位掩码以丢弃其他位
  • 我希望使用 5 位，因为纬度或经度的增量在此范围内。因此，对于很多示例（但尚未验证），每个双精度值平均只需要 5 位。
  • 现在，通过假设附近的双精度值非常接近并且创建的差异接近 0 来完成压缩，因此结果适合几个字节。然后这个结果以动态方式存储：存储 5 位，如果值更长，则用 0x20 标记并存储接下来的 5 位，依此类推。所以我想如果你尝试 6 或 4 位，你可以调整压缩，但我想 5 是一个实际上合理的选择。
  • 现在关于魔术 63，这是 0x3f 和二进制 0011 1111。我不确定他们为什么要添加它。我认为添加 63 会给出一些“更好”的 asci 字符（例如，在 XML 或 URL 中允许），因为我们跳过了例如 62，>但 63?真的更好？至少第一个 ascii 字符是不可显示的，必须避免。请注意，如果使用 64，那么将使用 ascii char 127 获得最大值 31 (31+64+32)，并且该 char 未在 html4 中定义。还是因为有符号字符从 -128 变为 127，我们需要将负数存储为正数，从而添加最大可能的负数？
  • 只为我：这里是一个使用 Apache 许可证的官方 Java 实现的链接
于 2014-07-01T12:52:11.660 回答