谷歌编码的多段线算法格式之编码折线算法学习

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

编码过程使用熟悉的 base64 编码方案将二进制值转换成一系列 ASCII 字符的字符代码：为了确保正确显示这些字符，编码值将先与 63(ASCII 字符“?”)相加，然后再转换成 ASCII。算法也会通过检查每个字节组的最低有效位来检查给定点有无其他字符代码;如果此位设为 1，则说明该点尚未完全构成，后面必须跟其他数据。

此外，为了节省空间，后面的点仅包含与前一个点的偏移(当然，第一个点除外)。所有点都将采用 Base64 方案编码为有符号的整数，因为纬度和经度为有符号的值。多段线内的编码格式需要以合理精度显示分别表示代表纬度和经度的两个坐标。假设最大经度 +/- 180 度精确到 5 位小数(180.00000 至 -180.00000)，这就会需要一个 32 位有符号的二进制整数值。

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

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

假设原始的有符号的值为：

-179.9832104

将此十进制值乘以 1e5，然后进行四舍五入，得到的整数值为：

-17998321

将十进制值转换成二进制值。请注意，负数值必须使用其二补数计算，具体做法为将二进制值反转，并向结果加 1：

00000001 00010010 10100001 11110001

11111110 11101101 01011110 00001110

11111110 11101101 01011110 00001111

将二进制值左移一位：

11111101 11011010 10111100 00011110

如果原始的十进制值为负数，请反转此编码：

00000010 00100101 01000011 11100001

将二进制值以 5 位区块形式分组(从右侧开始)：

00001 00010 01010 10000 11111 00001

以倒序排列 5 位区块：

00001 11111 10000 01010 00010 00001

如果后面有另一个位区块，请使用 0x20 对每个值进行或运算：

100001 111111 110000 101010 100010 000001

将每个值转换成十进制值：

33 63 48 42 34 1

将每个值加上 63：

96 126 111 105 97 64

将每个值转换成其 ASCII 对应字符：

`~oia@

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

示例

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

编码折线：_p~iF~ps|U_ulLnnqC_mqNvxq`@

解码方式很巧妙，只可意会不可言传：

private List<GeoPoint> decodePoly(String encoded) {  
  
    List<GeoPoint> poly = new ArrayList<GeoPoint>();  
    int index = 0, len = encoded.length();  
    int lat = 0, lng = 0;  
  
    while (index < len) {  
        int b, shift = 0, result = 0;  
        do {  
            b = encoded.charAt(index++) - 63;  
            result |= (b & 0x1f) << shift;  
            shift += 5;  
        } while (b >= 0x20);  
        int dlat = ((result & 1) != 0 ? ~(result >> 1) : (result >> 1));  
        lat += dlat;  
  
        shift = 0;  
        result = 0;  
        do {  
            b = encoded.charAt(index++) - 63;  
            result |= (b & 0x1f) << shift;  
            shift += 5;  
        } while (b >= 0x20);  
        int dlng = ((result & 1) != 0 ? ~(result >> 1) : (result >> 1));  
        lng += dlng;  
  
        GeoPoint p = new GeoPoint((int) (((double) lat / 1E5) * 1E6),  
             (int) (((double) lng / 1E5) * 1E6));  
        poly.add(p);  
    }  
  
    return poly;  
}