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

frostmourn716

首先，在Google API上所描述的算法如下：
下面说明了对此类有符号值进行编码的步骤。

取初始有符号值：
-179.9832104

将其取十进制值乘以 1e5，并取整：
-17998321

将十进制值转换为二进制值。请注意负值必须求反，并以值填充字节边界：
00000001 00010010 10100001 11110001
11111110 11101101 10100001 00001110
11111110 11101101 01011110 00001111

变换二进制值：
11111110 11101101 01011110 00001111 0

如果原来的十进制值是负数，则对以下编码求反：
00000001 00010010 10100001 11110000 1

将该二进制值分为 5 位一组的块（从右侧开始）:
00001 00010 01010 10000 11111 00001

将这些 5 位一组的块倒序放置：
00001 11111 10000 01010 00010 00001

如果后面还有一个位块，则将每个值与 0x20 进行“或”操作 (OR)：：
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)
   
   
   
   
    纬度
    经度
    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_int1;
        //如果原来的数是负数则求反
        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；”的字符串即可返回最后的经过编码的字符串。


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/104586/showart_2090863.html