GeoHash 介绍

在实现地图相关的查询时,经纬度比较不好实现,Geohash则能很好的解决经纬度查询问题。

GeoHash

Geohash算法将经纬度二维数据通过切分地图区域为小方块转换并编码为一个字符串，本质是一个降维的过程。也就是说，理论上geohash字符串表示的并不是一个点，而是一个矩形区域，只要矩形区域足够小，达到所需精度即可。

示例：

水立方就在鸟巢在附近，距离600米左右，而故宫到鸟巢直线距离9公里左右，体现在Geohash上，鸟巢和水立方的前五位是一样的，而鸟巢和故宫只有前4位是一样的，也就是说Geohash前面相同的越多，两个位置越近，但是反过来说，却不一定正确，这个在后面会详细介绍。

技术原理：

• 将纬度(-90, 90)平均分成两个区间(-90, 0)、(0, 90)，如果坐标位置的纬度值在第一区间，则编码是0，否则编码为1。我们用 39.918118 举例，由于39.918118 属于 (0, 90)，所以编码为1，然后我们继续将(0, 90)分成(0, 45)、(45, 90)两个区间，而39.918118 位于(0, 45)，所以编码是0，依次类推，我们进行20次拆分，最后计算39.918118 的编码是 1011 1000 1100 0101 1011；经度的处理也是类似，只是经度的范围是(-180, 180)，116.40382的编码是1101 0010 1100 0110 1010
• 经纬度的编码合并，从0开始，奇数为是纬度，偶数为是经度，得到的编码是1110 0111 0100 1000 1111 0000 0011 1001 1100 1101
• 对经纬度合并后的编码，进行base32编码，最终得到wx4g0ffe
• 其编码也有base 36 的版本对大小写敏感，用了36个字符，“23456789bBCdDFgGhHjJKlLMnNPqQrRtTVWX”。

java 版本实现：

import java.util.BitSet;
import java.util.HashMap;
 
public class GeoHash {
	private static int numbits = 6 * 5;
	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'};
	final static HashMap<Character, Integer> lookup = new HashMap<Character, Integer>();
	static {
		int i = 0;
		for(char c : digits)
			lookup.put(c, i++);
	}
	
	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();
		
		// even bits
		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);
		}
		
		// odd bits
		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};
	}
	
	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 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');
		}
		return base32(Long.parseLong(buffer.toString(), 2));
	}
	
	private BitSet getBits(double d, double floor, double ceiling) {
		BitSet buffer = new BitSet(numbits);
		for(int i = 0; i < numbits; i++) { double mid = (floor + ceiling) / 2; if(d >= mid) {
				buffer.set(i);
				floor = mid;
			} else {
				ceiling = mid;
			}
		}
		return buffer;
	}
	
	private static 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));
	}
	
	public static void main(String[] args) {
		System.out.println(new GeoHash().encode(39.92324, 116.3906));
		//输出：wx4g0ec19x3d
	}
}

边界问题

两个位置距离得越近是否意味着Geohash前面相同的越多呢？答案是否定的，两个很近的地点[116.3967,44.9999]和[116.3967,45.0009]的Geohash分别是wxfzbxvr和y84b08j2，这就是Geohash存在的边界问题，这两个地点虽然很近，但是刚好在分界点45两侧，导致Geohash完全不同，单纯依靠Geohash匹配前缀的方式并不能解决这种问题 

在一维空间解决不了这个问题，回到二维空间中，将当前Geohash这块区域周围的八块区域的Geohash计算出来 [116.3967,44.9999] 周围8块区域的Geohash

y84b08j2, wxfzbxvq, wxfzbxvx, wxfzbxvp, y84b08j8, y84b08j0, wxfzbxvw, wxfzbxvn

[116.3967,45.0009] 周围8块区域的Geohash

y84b08j3, wxfzbxvr, y84b08j8, y84b08j0, y84b08j9, y84b08j1, wxfzbxvx, wxfzbxvp

[116.3967,44.9999]和[116.3967,45.0009]分别出现在各自附近的区域中，周围8个区域的Geohash怎么计算得到呢？很简单，当Geohash长度是8时，对应的每个最小单元

    double latUnit = (Max_Lat - Min_Lat) / (1 << 20);
    double lngUnit = (Max_Lng - Min_Lng) / (1 << 20);

这样可以计算出8个分别分布在周围8个区域的地点，根据地点便可以计算出周围8个区域的Geohash

[lat + latUnit, lng]
[lat - latUnit, lng]
[lat, lng + lngUnit]
[lat, lng - lngUnit]
[lat + latUnit, lng + lngUnit]
[lat + latUnit, lng - lngUnit]
[lat - latUnit, lng + lngUnit]
[lat - latUnit, lng - lngUnit]

附：

Geohash 能够提供任意精度的分段级别。一般分级从 1-12 级。

GeoHash网站
http://geohash.co/

http://geohash.org/