Google Maps编码折线算法格式背后的设计决策是什么？

Question

一些Google Maps产品具有折线的概念,就基础数据而言,它基本上只是一系列lat/lng点,例如可能在地图上绘制的线中显示.Google Map开发人员库使用编码折线格式,该格式生成表示构成折线的点的ASCII字符串.然后通常利用Google库的内置函数或由实现解码算法的第三方编写的函数来解码该编码格式.

用于编码折线点的算法在编码折线算法格式文档中描述.什么是不是描述的是用于实现该算法通过这种方式,每个单独的步骤的重要性的理由.我很想知道以这种方式实现算法背后的思考/目的是否在任何地方公开描述.两个示例问题:

• 某些步骤是否会对压缩产生可量化的影响？这种影响如何随点之间的差异而变化？
• 使用ASCII 63的值的总和是某种兼容性黑客吗？

但总的来说,描述与算法一起解释为什么算法以它的方式实现.

Answer 1

更新： James Snook 的这篇博文也有“有效的 ascii”范围参数，并且可以逻辑地读取我想知道的其他步骤。例如，在存储之前左移，这使得负位成为第一位。

我找到了一些解释，不确定是否一切都100%正确。

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