最近需要實(shí)現(xiàn)一個(gè)功能衣式，查找車輛附近的加油站寸士，如果車和加油站距離在200米以內(nèi)，則查找成功碴卧。

加油站數(shù)量肯定不小弱卡，能否縮小查找范圍，否則以遍歷形式住册，效率肯定高不了婶博。

Geohash算法就是將經(jīng)緯度編碼，將二維變一維荧飞，給地址位置分區(qū)的一種算法凡人。

基本原理

GeoHash是一種地址編碼方法。他能夠把二維的空間經(jīng)緯度數(shù)據(jù)編碼成一個(gè)字符串

我們知道叹阔，經(jīng)度范圍是東經(jīng)180到西經(jīng)180挠轴，緯度范圍是南緯90到北緯90，我們設(shè)定西經(jīng)為負(fù)耳幢，南緯為負(fù)岸晦，所以地球上的經(jīng)度范圍就是[-180， 180]睛藻，緯度范圍就是[-90启上，90]。如果以本初子午線店印、赤道為界冈在，地球可以分成4個(gè)部分。

如果緯度范圍[-90°, 0°)用二進(jìn)制0代表按摘，（0°, 90°]用二進(jìn)制1代表讥邻，經(jīng)度范圍[-180°, 0°)用二進(jìn)制0代表，（0°, 180°]用二進(jìn)制1代表院峡，那么地球可以分成如下4個(gè)部分

如果在小塊范圍內(nèi)遞歸對半劃分呢兴使？

可以看到，劃分的區(qū)域更多了照激，也更精確了发魄。geohash算法就是基于這種思想，劃分的次數(shù)更多，區(qū)域更多励幼，區(qū)域面積更小了汰寓。通過將經(jīng)緯度編碼，給地理位置分區(qū)

Geohash算法

Geohash算法一共有三步苹粟。

首先將經(jīng)緯度變成二進(jìn)制有滑。

比如這樣一個(gè)點(diǎn)（39.923201, 116.390705）
緯度的范圍是（-90，90）嵌削，其中間值為0毛好。對于緯度39.923201，在區(qū)間（0苛秕，90）中肌访，因此得到一個(gè)1；（0艇劫，90）區(qū)間的中間值為45度吼驶，緯度39.923201小于45，因此得到一個(gè)0店煞，依次計(jì)算下去蟹演，即可得到緯度的二進(jìn)制表示，如下表：

最后得到緯度的二進(jìn)制表示為：

  10111000110001111001

同理可以得到經(jīng)度116.390705的二進(jìn)制表示為：

  11010010110001000100

第2步顷蟀，就是將經(jīng)緯度合并酒请。

經(jīng)度占偶數(shù)位，緯度占奇數(shù)位衩椒，注意蚌父，0也是偶數(shù)位哮兰。

  11100 11101 00100 01111 00000 01101 01011 00001

第3步毛萌，按照Base32進(jìn)行編碼

Base32編碼表的其中一種如下，是用0-9喝滞、b-z（去掉a, i, l, o）這32個(gè)字母進(jìn)行編碼阁将。具體操作是先將上一步得到的合并后二進(jìn)制轉(zhuǎn)換為10進(jìn)制數(shù)據(jù)，然后對應(yīng)生成Base32碼右遭。需要注意的是做盅，將5個(gè)二進(jìn)制位轉(zhuǎn)換成一個(gè)base32碼。上例最終得到的值為

  wx4g0ec1

Geohash比直接用經(jīng)緯度的高效很多窘哈，而且使用者可以發(fā)布地址編碼吹榴，既能表明自己位于北海公園附近，又不至于暴露自己的精確坐標(biāo)滚婉，有助于隱私保護(hù)图筹。

• GeoHash用一個(gè)字符串表示經(jīng)度和緯度兩個(gè)坐標(biāo)。在數(shù)據(jù)庫中可以實(shí)現(xiàn)在一列上應(yīng)用索引（某些情況下無法在兩列上同時(shí)應(yīng)用索引）
• GeoHash表示的并不是一個(gè)點(diǎn)，而是一個(gè)矩形區(qū)域
• GeoHash編碼的前綴可以表示更大的區(qū)域远剩。例如wx4g0ec1扣溺，它的前綴wx4g0e表示包含編碼wx4g0ec1在內(nèi)的更大范圍。 這個(gè)特性可以用于附近地點(diǎn)搜索

編碼越長瓜晤，表示的范圍越小锥余，位置也越精確。因此我們就可以通過比較GeoHash匹配的位數(shù)來判斷兩個(gè)點(diǎn)之間的大概距離痢掠。

問題

geohash算法有兩個(gè)問題驱犹。首先是邊緣問題。

如圖志群，如果車在紅點(diǎn)位置着绷，區(qū)域內(nèi)還有一個(gè)黃點(diǎn)。相鄰區(qū)域內(nèi)的綠點(diǎn)明顯離紅點(diǎn)更近锌云。但因?yàn)辄S點(diǎn)的編碼和紅點(diǎn)一樣荠医，最終找到的將是黃點(diǎn)。這就有問題了桑涎。

要解決這個(gè)問題彬向，很簡單，只要再查找周邊8個(gè)區(qū)域內(nèi)的點(diǎn)攻冷，看哪個(gè)離自己更近即可娃胆。

另外就是曲線突變問題。

本文第2張圖片比較好地解釋了這個(gè)問題等曼。其中0111和1000兩個(gè)編碼非常相近里烦，但它們的實(shí)際距離確很遠(yuǎn)。所以編碼相近的兩個(gè)單位禁谦，并不一定真實(shí)距離很近胁黑，這需要實(shí)際計(jì)算兩個(gè)點(diǎn)的距離才行。

代碼實(shí)現(xiàn)

geohash原理清楚后州泊，代碼實(shí)現(xiàn)就比較簡單了丧蘸。不過仍然有一個(gè)問題需要解決，就是如何計(jì)算周邊的8個(gè)區(qū)域key值呢

假設(shè)我們計(jì)算的key值是6位遥皂，那么二進(jìn)制位數(shù)就是 6*5 = 30位力喷，所以經(jīng)緯度分別是15位。我們以緯度為例演训，緯度會均分15次弟孟。這樣我們很容易能夠算出15次后，劃分的最小單位是多少

  private void setMinLatLng() {
    minLat = MAXLAT - MINLAT;
    for (int i = 0; i < numbits; i++) {
        minLat /= 2.0;
    }
    minLng = MAXLNG - MINLNG;
    for (int i = 0; i < numbits; i++) {
        minLng /= 2.0;
    }
}

得到了最小單位样悟，那么周邊區(qū)域的經(jīng)緯度也可以計(jì)算得到了拂募。比如說左邊區(qū)域的經(jīng)度肯定是自身經(jīng)度減去最小經(jīng)度單位。緯度也可以通過加減，得到上下的緯度值没讲，最終周圍8個(gè)單位也可以計(jì)算得到眯娱。

可以到 http://geohash.co/ 進(jìn)行g(shù)eohash編碼，以確定自己代碼是否寫錯(cuò)

整體代碼如下所示：

public class GeoHash {
public static final double MINLAT = -90;
public static final double MAXLAT = 90;
public static final double MINLNG = -180;
public static final double MAXLNG = 180;

private static int numbits = 3 * 5; //經(jīng)緯度單獨(dú)編碼長度

private static double minLat;
private static double minLng;

private final static char[] digits = { '0', '1', '2', '3', '4', '5', '6', '7', '8',
        '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p',
        'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };

//定義編碼映射關(guān)系
final static HashMap<Character, Integer> lookup = new HashMap<Character, Integer>();
//初始化編碼映射內(nèi)容
static {
    int i = 0;
    for (char c : digits)
        lookup.put(c, i++);
}

public GeoHash(){
    setMinLatLng();
}

public String encode(double lat, double lon) {
    BitSet latbits = getBits(lat, -90, 90);
    BitSet lonbits = getBits(lon, -180, 180);
    StringBuilder buffer = new StringBuilder();
    for (int i = 0; i < numbits; i++) {
        buffer.append( (lonbits.get(i))?'1':'0');
        buffer.append( (latbits.get(i))?'1':'0');
    }
    String code = base32(Long.parseLong(buffer.toString(), 2));
    //Log.i("okunu", "encode  lat = " + lat + "  lng = " + lon + "  code = " + code);
    return code;
}

public ArrayList<String> getArroundGeoHash(double lat, double lon){
    //Log.i("okunu", "getArroundGeoHash  lat = " + lat + "  lng = " + lon);
    ArrayList<String> list = new ArrayList<>();
    double uplat = lat + minLat;
    double downLat = lat - minLat;

    double leftlng = lon - minLng;
    double rightLng = lon + minLng;

    String leftUp = encode(uplat, leftlng);
    list.add(leftUp);

    String leftMid = encode(lat, leftlng);
    list.add(leftMid);

    String leftDown = encode(downLat, leftlng);
    list.add(leftDown);

    String midUp = encode(uplat, lon);
    list.add(midUp);

    String midMid = encode(lat, lon);
    list.add(midMid);

    String midDown = encode(downLat, lon);
    list.add(midDown);

    String rightUp = encode(uplat, rightLng);
    list.add(rightUp);

    String rightMid = encode(lat, rightLng);
    list.add(rightMid);

    String rightDown = encode(downLat, rightLng);
    list.add(rightDown);

    //Log.i("okunu", "getArroundGeoHash list = " + list.toString());
    return list;
}

//根據(jù)經(jīng)緯度和范圍爬凑，獲取對應(yīng)的二進(jìn)制
private BitSet getBits(double lat, double floor, double ceiling) {
    BitSet buffer = new BitSet(numbits);
    for (int i = 0; i < numbits; i++) {
        double mid = (floor + ceiling) / 2;
        if (lat >= mid) {
            buffer.set(i);
            floor = mid;
        } else {
            ceiling = mid;
        }
    }
    return buffer;
}

//將經(jīng)緯度合并后的二進(jìn)制進(jìn)行指定的32位編碼
private String base32(long i) {
    char[] buf = new char[65];
    int charPos = 64;
    boolean negative = (i < 0);
    if (!negative){
        i = -i;
    }
    while (i <= -32) {
        buf[charPos--] = digits[(int) (-(i % 32))];
        i /= 32;
    }
    buf[charPos] = digits[(int) (-i)];
    if (negative){
        buf[--charPos] = '-';
    }
    return new String(buf, charPos, (65 - charPos));
}

private void setMinLatLng() {
    minLat = MAXLAT - MINLAT;
    for (int i = 0; i < numbits; i++) {
        minLat /= 2.0;
    }
    minLng = MAXLNG - MINLNG;
    for (int i = 0; i < numbits; i++) {
        minLng /= 2.0;
    }
}

//根據(jù)二進(jìn)制和范圍解碼
private double decode(BitSet bs, double floor, double ceiling) {
    double mid = 0;
    for (int i=0; i<bs.length(); i++) {
        mid = (floor + ceiling) / 2;
        if (bs.get(i))
            floor = mid;
        else
            ceiling = mid;
    }
    return mid;
}

//對編碼后的字符串解碼
public double[] decode(String geohash) {
    StringBuilder buffer = new StringBuilder();
    for (char c : geohash.toCharArray()) {
        int i = lookup.get(c) + 32;
        buffer.append( Integer.toString(i, 2).substring(1) );
    }

    BitSet lonset = new BitSet();
    BitSet latset = new BitSet();

    //偶數(shù)位徙缴，經(jīng)度
    int j =0;
    for (int i=0; i< numbits*2;i+=2) {
        boolean isSet = false;
        if ( i < buffer.length() )
            isSet = buffer.charAt(i) == '1';
        lonset.set(j++, isSet);
    }

    //奇數(shù)位，緯度
    j=0;
    for (int i=1; i< numbits*2;i+=2) {
        boolean isSet = false;
        if ( i < buffer.length() )
            isSet = buffer.charAt(i) == '1';
        latset.set(j++, isSet);
    }

    double lon = decode(lonset, -180, 180);
    double lat = decode(latset, -90, 90);

    return new double[] {lat, lon};
}

public static void main(String[] args)  throws Exception{
    GeoHash geohash = new GeoHash();
//        String s = geohash.encode(40.222012, 116.248283);
//        System.out.println(s);
    geohash.getArroundGeoHash(40.222012, 116.248283);
//        double[] geo = geohash.decode(s);
//        System.out.println(geo[0]+" "+geo[1]);
}
}