基本原理

GeoHash是一种地址编码的方法。他能够把二位空间经纬度数据编码成一个字符串

我们知道，经纬范围是东经180到西经180，维度范围是南纬90到北纬90，我们设定西经为负，南纬为负，所以地球上的经度范围就是【-180,180】，维度范围就是【-90,90】。如果以本初子午线，赤道为界，地球可分为4个部分

如果维度范围【-90,0）用二进制0表示，(0,90)用二进制1表示，经度范围【-180,0)用erjinz 0表示，（0,180】用二进制1表示，那么地球可以分为如下4个部分
GeoHash算法原理及实现 - 图1
如果在小块范围内递归对半划分呢？
GeoHash算法原理及实现 - 图2

可以看到，划分的区域更多了，也更精确了。geohash算法就是基于这种思想，划分的次数更多，区域更多，区域面积更小了。通过将经纬度编码，给地理位置分区

Geohash算法

一共有3步

首先将经纬度变为二进制

比如这样一个点（39.923201, 116.390705）
维度范围是（-90,90），其中间值为0.对于维度39.923201，在区间（0,90）中，因此的到一个1；（0,90）区间的中间值为45°，维度39.39.923201小于45，因此得到一个0，依次计算下去，即可得到维度的二进制表示，如下表：

GeoHash算法原理及实现 - 图3

最后得到维度的二进制表示为：

  1. 10111000110001111001

第二步，就是将经纬度合并

经度占偶数位，维度占奇数位，注意，也是偶数位。

第三步，按照Base32进行编码

Base32编码表的其中一种如下，使用0-9、b-z（去掉a,i,l,o）这32个字母进行编码。具有操作是先将上一步得到的合并后二进制转换为10进制数据，然后对应生成Base32码。上例最终得到的值为

  1. wx4g0ec1

Geohash比直接用经纬度的高效很多，而且使用者可以发布地址编码，既能表明自己位于北海公园附近，又不至于暴露自己的精确坐标，有助于隐私保护

  1. GeoHash用一个字符串表示经度和维度两个坐标。在数据库中可以实现在1列上应用索引
  2. GeoHash表示的并不是提个点，而是一个矩形区域
  3. GeoHash编码的前缀可以表示更大的区域。例如wx4g0ec1，他的前缀wx4g0e表示包含编码wx4g0ec1在内的更大的范围。这个特性可以用于附近低点搜索

编码越长，表示范围越小，位置也越精确。因此我们就可以通过比较GeoHash匹配的位数来判断两个点之间的大概距离
GeoHash算法原理及实现 - 图4

问题

geohash算法有两个问题。首先是边缘问题。

GeoHash算法原理及实现 - 图5
如图，如果车在红点位置，区域内还有一个黄点。相邻区域内的绿点明显离红点更近。但因为黄点的编码与红点的一样，最终找到的将是黄点。

要解决这个问题，很简单，只要在查找周边8个区域内的点，看那个离自己更近即可

另外就是曲线突变问题

本文第二张图比较好的解释了这个问题，其中0111和1000两个编码非常相近，但他们的实际距离很远。所以编码相近的两个单位，并不一定真是距离很近，这需要实际计算两个点的距离才行。

代码实现

geohash原理清楚后，代码实现就比较简单了。不过仍然有一个问题需要解决，就是如何计算周边的8个区域key值

假设我们计算的key值是6位，那么二进制的位数就是6*5 = 30 位，所以经纬度分别是15位。我们以维度为例，维度会均分15次。这样我们很容易能够算出15次后，划分的最小单位是多少

  1.   private void setMinLatLng() {
  2.     minLat = MAXLAT - MINLAT;
  3.     for (int i = 0; i < numbits; i++) {
  4.         minLat /= 2.0;
  5.     }
  6.     minLng = MAXLNG - MINLNG;
  7.     for (int i = 0; i < numbits; i++) {
  8.         minLng /= 2.0;
  9.     }
  10. }

得到了最小单位，那么周边区域的经纬度也可以计算得到了。比如左边区域的经度肯定是自身经度减去最小经度单位。维度也可以通过加减，得到上下的经纬度，最终周围8个单位也可以计算得到

可以到 http://geohash.co/ 进行geohash编码，以确定自己代码是否写错


整体代码如下所示：

  1. public class GeoHash {
  2. public static final double MINLAT = -90;
  3. public static final double MAXLAT = 90;
  4. public static final double MINLNG = -180;
  5. public static final double MAXLNG = 180;
  7. private static int numbits = 3 * 5; //经纬度单独编码长度
  9. private static double minLat;
  10. private static double minLng;
  12. private final static char[] digits = { '0', '1', '2', '3', '4', '5', '6', '7', '8',
  13.         '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p',
  14.         'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
  16. //定义编码映射关系
  17. final static HashMap<Character, Integer> lookup = new HashMap<Character, Integer>();
  18. //初始化编码映射内容
  19. static {
  20.     int i = 0;
  21.     for (char c : digits)
  22.         lookup.put(c, i++);
  23. }
  25. public GeoHash(){
  26.     setMinLatLng();
  27. }
  29. public String encode(double lat, double lon) {
  30.     BitSet latbits = getBits(lat, -90, 90);
  31.     BitSet lonbits = getBits(lon, -180, 180);
  32.     StringBuilder buffer = new StringBuilder();
  33.     for (int i = 0; i < numbits; i++) {
  34.         buffer.append( (lonbits.get(i))?'1':'0');
  35.         buffer.append( (latbits.get(i))?'1':'0');
  36.     }
  37.     String code = base32(Long.parseLong(buffer.toString(), 2));
  38.     //Log.i("okunu", "encode  lat = " + lat + "  lng = " + lon + "  code = " + code);
  39.     return code;
  40. }
  42. public ArrayList<String> getArroundGeoHash(double lat, double lon){
  43.     //Log.i("okunu", "getArroundGeoHash  lat = " + lat + "  lng = " + lon);
  44.     ArrayList<String> list = new ArrayList<>();
  45.     double uplat = lat + minLat;
  46.     double downLat = lat - minLat;
  48.     double leftlng = lon - minLng;
  49.     double rightLng = lon + minLng;
  51.     String leftUp = encode(uplat, leftlng);
  52.     list.add(leftUp);
  54.     String leftMid = encode(lat, leftlng);
  55.     list.add(leftMid);
  57.     String leftDown = encode(downLat, leftlng);
  58.     list.add(leftDown);
  60.     String midUp = encode(uplat, lon);
  61.     list.add(midUp);
  63.     String midMid = encode(lat, lon);
  64.     list.add(midMid);
  66.     String midDown = encode(downLat, lon);
  67.     list.add(midDown);
  69.     String rightUp = encode(uplat, rightLng);
  70.     list.add(rightUp);
  72.     String rightMid = encode(lat, rightLng);
  73.     list.add(rightMid);
  75.     String rightDown = encode(downLat, rightLng);
  76.     list.add(rightDown);
  78.     //Log.i("okunu", "getArroundGeoHash list = " + list.toString());
  79.     return list;
  80. }
  82. //根据经纬度和范围，获取对应的二进制
  83. private BitSet getBits(double lat, double floor, double ceiling) {
  84.     BitSet buffer = new BitSet(numbits);
  85.     for (int i = 0; i < numbits; i++) {
  86.         double mid = (floor + ceiling) / 2;
  87.         if (lat >= mid) {
  88.             buffer.set(i);
  89.             floor = mid;
  90.         } else {
  91.             ceiling = mid;
  92.         }
  93.     }
  94.     return buffer;
  95. }
  97. //将经纬度合并后的二进制进行指定的32位编码
  98. private String base32(long i) {
  99.     char[] buf = new char[65];
  100.     int charPos = 64;
  101.     boolean negative = (i < 0);
  102.     if (!negative){
  103.         i = -i;
  104.     }
  105.     while (i <= -32) {
  106.         buf[charPos--] = digits[(int) (-(i % 32))];
  107.         i /= 32;
  108.     }
  109.     buf[charPos] = digits[(int) (-i)];
  110.     if (negative){
  111.         buf[--charPos] = '-';
  112.     }
  113.     return new String(buf, charPos, (65 - charPos));
  114. }
  116. private void setMinLatLng() {
  117.     minLat = MAXLAT - MINLAT;
  118.     for (int i = 0; i < numbits; i++) {
  119.         minLat /= 2.0;
  120.     }
  121.     minLng = MAXLNG - MINLNG;
  122.     for (int i = 0; i < numbits; i++) {
  123.         minLng /= 2.0;
  124.     }
  125. }
  127. //根据二进制和范围解码
  128. private double decode(BitSet bs, double floor, double ceiling) {
  129.     double mid = 0;
  130.     for (int i=0; i<bs.length(); i++) {
  131.         mid = (floor + ceiling) / 2;
  132.         if (bs.get(i))
  133.             floor = mid;
  134.         else
  135.             ceiling = mid;
  136.     }
  137.     return mid;
  138. }
  140. //对编码后的字符串解码
  141. public double[] decode(String geohash) {
  142.     StringBuilder buffer = new StringBuilder();
  143.     for (char c : geohash.toCharArray()) {
  144.         int i = lookup.get(c) + 32;
  145.         buffer.append( Integer.toString(i, 2).substring(1) );
  146.     }
  148.     BitSet lonset = new BitSet();
  149.     BitSet latset = new BitSet();
  151.     //偶数位，经度
  152.     int j =0;
  153.     for (int i=0; i< numbits*2;i+=2) {
  154.         boolean isSet = false;
  155.         if ( i < buffer.length() )
  156.             isSet = buffer.charAt(i) == '1';
  157.         lonset.set(j++, isSet);
  158.     }
  160.     //奇数位，纬度
  161.     j=0;
  162.     for (int i=1; i< numbits*2;i+=2) {
  163.         boolean isSet = false;
  164.         if ( i < buffer.length() )
  165.             isSet = buffer.charAt(i) == '1';
  166.         latset.set(j++, isSet);
  167.     }
  169.     double lon = decode(lonset, -180, 180);
  170.     double lat = decode(latset, -90, 90);
  172.     return new double[] {lat, lon};
  173. }
  175. public static void main(String[] args)  throws Exception{
  176.     GeoHash geohash = new GeoHash();
  177. //        String s = geohash.encode(40.222012, 116.248283);
  178. //        System.out.println(s);
  179.     geohash.getArroundGeoHash(40.222012, 116.248283);
  180. //        double[] geo = geohash.decode(s);
  181. //        System.out.println(geo[0]+" "+geo[1]);
  182. }
  183. }