利用Geohash算法，快速检索周边兴趣点
文章目录
一、前言二、基本原理三、Geohash算法四、算法存在的问题五、代码实现六、问题解决处理
一、前言
需要一个需求，查找某小区附近的超市，如果该小区和超市距离在500米以内，则查找成功。 实现该功能按照传统方式，需要获取小区中心点坐标，然后500米半径做缓冲，然后对所有的超市点位和生成的缓冲区做空间分析，在缓冲区内的就是符合条件的超市。但是超市数据量很大，有什么方式能快速过滤超市数据呐？geohash是不错的方式，下面这种介绍geohash算法的原因和实现方式。
二、基本原理
GeoHash是一种地址编码方法。他能够把二维的空间经纬度数据编码成一个字符串。 （1） 按照经度范围[-180°,180°]，纬度范围[-90°,90°]对目标经纬度进行计算；二分经度和纬度范围区间，分别判断经度和纬度，在右侧集合则为1，在左侧集合则为0；循环进行此计算。 （2）将所得经纬度1和0结果，经度在偶数位（从0位计算），纬度在奇数位进行拼接，5位二进制结果为 一组，转换为十进制数后，再转换为对应Base32码表中数字，即得到对应GeoHash值。 具体分法： 经度范围是东经180到西经180，纬度范围是南纬90到北纬90，我们设定西经为负，南纬为负，所以地球上的经度范围就是[-180， 180]，纬度范围就是[-90，90]。如果以本初子午线、赤道为界，地球可以分成4个部分。 如果纬度范围[-90°, 0°)用二进制0代表，（0°, 90°]用二进制1代表，经度范围[-180°, 0°)用二进制0代表，（0°, 180°]用二进制1代表，那么地球可以分成如下4个部分
如果在小块范围内递归对半划分呢？ 可以看到，划分的区域更多了，也更精确了。geohash算法就是基于这种思想，划分的次数更多，区域更多，区域面积更小了。通过将经纬度编码，给地理位置分区
三、Geohash算法
Geohash算法一共有三步。 首先将经纬度变成二进制。 第一步： 比如这样一个点（39.923201, 116.390705） 纬度的范围是（-90，90），其中间值为0。对于纬度39.923201，在区间（0，90）中，因此得到一个1；（0，90）区间的中间值为45度，纬度39.923201小于45，因此得到一个0，依次计算下去，即可得到纬度的二进制表示，如下表： 最后得到纬度的二进制表示为：
10111000110001111001
同理可以得到经度116.390705的二进制表示为：
11010010110001000100
第2步将经纬度合并： 经度占偶数位，纬度占奇数位，注意，0也是偶数位。
11100 11101 00100 01111 00000 01101 01011 00001
第3步，按照Base32进行编码： Base32编码表的其中一种如下，是用0-9、b-z（去掉a, i, l, o）这32个字母进行编码。具体操作是先将上一步得到的合并后二进制转换为10进制数据，然后对应生成Base32码。需要注意的是，将5个二进制位转换成一个base32码。上例最终得到的值为
wx4g0ec1
Geohash比直接用经纬度的高效很多，而且使用者可以发布地址编码，既能表明自己位于北海公园附近，又不至于暴露自己的精确坐标，有助于隐私保护。
GeoHash用一个字符串表示经度和纬度两个坐标。在数据库中可以实现在一列上应用索引（某些情况下无法在两列上同时应用索引） GeoHash表示的并不是一个点，而是一个矩形区域 GeoHash编码的前缀可以表示更大的区域。例如wx4g0ec1，它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索 编码越长，表示的范围越小，位置也越精确。因此我们就可以通过比较GeoHash匹配的位数来判断两个点之间的大概距离。
四、算法存在的问题
geohash算法有两个问题。首先是边缘问题。 如图，如果小区中心点在红点位置，区域内还有一个黄点。相邻区域内的绿点明显离红点更近。但因为黄点的编码和红点一样，最终找到的将是黄点。这就有问题了。 要解决这个问题，很简单，只要再查找周边8个区域内的点，看哪个离自己更近即可。 另外就是曲线突变问题。 本文第2张图片比较好地解释了这个问题。其中0111和1000两个编码非常相近，但它们的实际距离确很远。所以编码相近的两个单位，并不一定真实距离很近，这需要实际计算两个点的距离才行。
五、代码实现
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; //经纬度单独编码长度
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' };
//定义编码映射关系
final static HashMap
//初始化编码映射内容
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
//Log.i("okunu", "getArroundGeoHash lat = " + lat + " lng = " + lon);
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;
}
//根据经纬度和范围，获取对应的二进制
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;
}
//将经纬度合并后的二进制进行指定的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;
}
}
//根据二进制和范围解码
private double decode(BitSet bs, double floor, double ceiling) {
double mid = 0;
for (int i=0; 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(); //偶数位，经度 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); } //奇数位，纬度 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]); } } 可以到 http://geohash.co/ 进行geohash编码，以确定自己代码是否写错 六、问题解决处理 针对查找小区500米范围超市，可以通过匹配geohash的前几位过滤超市，然后根据过滤后的超市再进行空间过滤，这样既有速度也有准确度 // 例如 SELECT * FROM place WHERE geohash LIKE 'wx4g0%'; 参考： Geohash算法原理及实现