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

Question

几个谷歌地图产品都有折线的概念。在底层数据方面，这基本上只是一系列纬度/经度点的序列，例如可以在地图上画出一条线。谷歌地图开发库使用编码折线格式，生成代表组成折线的点的ASCII字符串。然后，此编码格式通常使用谷歌库的内置函数或由实现解码算法的第三方编写的函数进行解码。编码折线点的算法在Encoded Polyline Algorithm Format文档中描述。没有描述实施该算法的理由以及每个单独步骤的意义。我想知道实施该算法方式背后的思考/目的是否公开描述在任何地方。两个例子问题：

- 一些步骤对压缩有可量化的影响，这种影响如何随着点之间的差异而变化？ - ASCII 63的值相加是否是某种兼容性黑客？

但总的来说，需要一份与算法配合的说明，解释为什么要按照这种方式实施算法。

- Bryce Thomas

---

Mark McClure曾经有过一次很好的讨论。那个服务器现在似乎已经崩溃了在wayback机器上的快照。 - geocodezip

我也很感兴趣。我发现这些代码注释很有用：https://dev59.com/BWDVa4cB1Zd3GeqPdXGU#13890455 - Karussell

Answer 1

更新: 这篇博客文章 来自James Snook，其中包含“有效的ASCII”范围参数，并且在其他步骤中也很合理。例如，在存储之前左移，以便将负位作为第一位。

我找到了一些解释，不确定是否全部正确。

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

- Karussell

---

使用64位编码的原因是为了能够将值作为纯文本发送。显然，除了63之外，还有许多其他值可以用于此。但就非常低的工作解决方案而言，63似乎是一个相当不错的值。它避免了引号和分号。人们会怀疑避免“？”可能是理想的。很难找到更好的范围来选择ASCII表中的64个字符。 [维基百科]（http://en.wikipedia.org/wiki/Base64）建议对于许多64位编码，通常选择更复杂的映射。 - James Snook

official Java implementation with Apache License 的链接返回 404。你能更新一下吗？ - Peter VARGA