编码多段线算法格式

多段线编码是一种有损压缩算法,允许您将一系列坐标存储为单个字符串。点坐标使用有符号的值进行编码。如果只有几个静态点,您可能还希望使用交互式多段线编码实用程序

在编码过程中,我们使用熟悉的 base64 编码方案将二进制值转换为一系列 ASCII 字符的字符代码:为确保这些字符能够正常显示,在将编码值转换为 ASCII 之前,系统会先使用 63(ASCII 字符 '?')将其转换为 ASCII 字符。该算法还会通过检查每个字节组的最低有效位来检查给定点的其他字符代码;如果此位设置为 1,则该点尚未完全形成,必须显示额外的数据。

此外,为了节省空间,点仅包含与前一个点的偏移量(当然,第一个点除外)。所有点都采用 Base64 编码为带符号的整数,因为纬度和经度是带符号的值。多段线中的编码格式需要以合理精度表示分别代表纬度和经度的两个坐标。由于最大经度范围为 +/- 180 度,精度为 5 位小数(180.00000 至 -180.00000),因此需要 32 位带符号的二进制整数值。

请注意,在字符串字面量中,反斜杠被解释为转义字符。此实用程序的任何输出都应在字符串字面量中将反斜杠字符转换为双反斜杠。

下文指定了编码此类有符号的值的步骤。

  1. 接受初始有符号值:
    -179.9832104
  2. 将此十进制值乘以 1e5,然后进行四舍五入,得出结果:
    -17998321
  3. 将十进制值转换为二进制值。请注意,负数值必须使用其二元补码进行计算,具体方法是将二进制值反转,并向结果加 1:
    00000001 00010010 10100001 11110001
    11111110 111011010101010101010101010101010101010101010101010101010101010101010
  4. 将二进制值左移 1 位:
    11111101 11011010 10111100 00011110
  5. 如果原始小数值为负数,请反转此编码:
    00000010 00100101 01000011 11100001
  6. 将二进制值拆分为 5 位区块(从右侧开始):
    00001 00010 01010 10000 11111 00001
  7. 按倒序排列 5 位区块:
    00001 11111 10000 01010 00010 00001
  8. 或每个值在 0x20 值后面的另一个位块:
    100001 111111 110000 101010 100010 000001
  9. 将每个值转换为小数:
    33 63 48 42 34 1
  10. 在每个值中添加 63:
    96 126 111 105 97 64
  11. 将每个值转换为其对应的 ASCII 码:
    `~oia@

下表显示了一些编码点的示例,其中将编码显示为相对于先前点的一系列偏移。

示例

点:(38.5, -120.2)、(40.7, -120.95)、(43.252, -126.453)

纬度 经度 纬度 (E5) 经度 (E5) 纬度变化 经度变化 编码纬度 编码经度 编码点
38.5 -120.2 3850000 -12020000 +3850000 -12020000 _p~iF ~ps|U _p~iF~ps|U
40.7 -120.95 4070000 -12095000 +220000 -75000 _ulL nnqC _ulLnnqC
43.252 -126.453 4325200 -12645300 +255200 -550300 _mqN vxq`@ _mqNvxq`@

编码多段线_p~iF~ps|U_ulLnnqC_mqNvxq`@