Google MAP编码折线算法的Java实现

首先，在Google API上所描述的算法如下：

下面说明了对此类有符号值进行编码的步骤。

1. 取初始有符号值：
   -179.9832104
2. 将其取十进制值乘以 1e5，并取整：
   -17998321
3. 将十进制值转换为二进制值。请注意负值必须求反，并以值填充字节边界：
   00000001 00010010 10100001 11110001
   11111110 11101101 10100001 00001110
   11111110 11101101 01011110 00001111
4. 变换二进制值：
   11111110 11101101 01011110 00001111 0
5. 如果原来的十进制值是负数，则对以下编码求反：
   00000001 00010010 10100001 11110000 1
6. 将该二进制值分为 5 位一组的块（从右侧开始）:
   00001 00010 01010 10000 11111 00001
7. 将这些 5 位一组的块倒序放置：
   00001 11111 10000 01010 00010 00001
8. 如果后面还有一个位块，则将每个值与 0x20 进行“或”操作 (OR)：：
   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`@

自己写的Java代码如下（参考了一个网上流传的C语言版本，但是那个版本里面对第8条描述的理解有误，即encode（double）这个函数里的while的退出条件）：



    private String encode(double point) {
        //取十进制乘以1e5

        int _point_int = (int) (point*1e5);
        //对二进制低位补0

        _point_int = _point_int<<1;
        //如果原来的数是负数则求反

        if( point < 0) {
            _point_int = ~_point_int;
        }
        
        String resultString = "";
        while ( _point_int>>>5 > 0) {//如果位块后面还有一个位块

            int _block = _point_int&0x1F;//将二进制数分为5位一组的块，倒序处理

            _block = (_block|0x20)+63;
            char _result = (char) _block;
            resultString +=_result;
            _point_int = _point_int>>>5;
        }
        resultString += (char)(_point_int+63);
        return resultString;
    }
    
    private String encodeLatLng(double lat, double lng) {
        String _lat = this.encode(lat);
        String _lng = this.encode(lng);
        return _lat+_lng;
    }
    
    private String encodeLatLng(String lat, String lng) {
        double _lat = Double.parseDouble(lat);
        double _lng = Double.parseDouble(lng);
        return this.encodeLatLng(_lat, _lng);
    }
    
    private String encodeLine(String line) {
        String [] _points = null;
        String _result = "";
        BigDecimal _lat_temp = new BigDecimal(0.0);
        BigDecimal _lng_temp = new BigDecimal(0.0);
        _points = line.split(";");
        for (String _point : _points) {
            String [] _latlng = _point.split(",");
            BigDecimal _lat = BigDecimal.valueOf(Double.parseDouble(_latlng[0]));
            BigDecimal _lng = BigDecimal.valueOf(Double.parseDouble(_latlng[1]));
            double _lat_disp = _lat.subtract(_lat_temp).doubleValue();
            double _lng_disp = _lng.subtract(_lng_temp).doubleValue();
            _result += this.encodeLatLng(_lat_disp,_lng_disp);
            _lat_temp = _lat;
            _lng_temp = _lng;
        }
        return _result;
    }

其中encode（double）这个函数是实现的折线编码算法，剩余三个函数是一些辅助函数，其中最后一个encodeLine（String）函数只需传入一个类似“26.12345，139.1234；26.12345，139.1234；”的字符串即可返回最后的经过编码的字符串。