GeoHash简介

原创
2018/07/30 10:52
阅读数 170

参考文档:

 

http://blog.csdn.net/wangxiafghj/article/details/9014363geohash  算法原理及实现方式
http://blog.charlee.li/geohash-intro/  geohash:用字符串实现附近地点搜索
http://blog.sina.com.cn/s/blog_7c05385f0101eofb.html    查找附近点--Geohash方案讨论
http://www.wubiao.info/372        查找附近的xxx 球面距离以及Geohash方案探讨
http://en.wikipedia.org/wiki/Haversine_formula       Haversine formula球面距离公式
http://www.codecodex.com/wiki/Calculate_Distance_Between_Two_Points_on_a_Globe   球面距离公式代码实现
http://developer.baidu.com/map/jsdemo.htm#a6_1   球面距离公式验证  
http://www.wubiao.info/470     Mysql or Mongodb LBS快速实现方案

 

现在很多APP都有搜索附近的功能,比如附近的人、附近的店铺等。要实现这样的功能,我们可以用最笨的方法:根据经纬度计算距离,然后划定一个阈值,只要小于该阈值就算是附近的。这种方法在数据量小时基本没问题,但是,如果数据量特别大,那服务器就需要进行大量的计算,负担很重!为了解决这一类问题,一个比较常用的方法就是利用GeoHash。 
一、简介 
GeoHash是一种地址编码方法。他能够把二维的空间经纬度数据编码成一个字符串。GeoHash具有以下特点: 
1、GeoHash用一个字符串表示经度和纬度两个坐标。在数据库中可以实现在一列上应用索引 
2、GeoHash表示的并不是一个点,而是一个区域; 
3、GeoHash编码的前缀可以表示更大的区域。例如wx4g0ec1,它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索 
二、计算方法: 
GeoHash的计算过程分为三步: 
1、将经纬度转换成二进制: 
比如这样一个点(39.923201, 116.390705) 
纬度的范围是(-90,90),其中间值为0。对于纬度39.923201,在区间(0,90)中,因此得到一个1;(0,90)区间的中间值为45度,纬度39.923201小于45,因此得到一个0,依次计算下去,即可得到纬度的二进制表示,如下表: 
这里写图片描述 
最后得到纬度的二进制表示为: 
10111000110001111001 
同理可以得到经度116.390705的二进制表示为: 
11010010110001000100 
2、合并纬度、经度的二进制: 
合并方法是将经度、纬度二进制按照奇偶位合并: 
11100 11101 00100 01111 00000 01101 01011 00001 
3、按照Base32进行编码: 
Base32编码表(其中一种): 
这里写图片描述
将上述合并后二进制编码后结果为: 
wx4g0ec1 
三、GeoHash的精度 
这里写图片描述
编码越长,表示的范围越小,位置也越精确。因此我们就可以通过比较GeoHash匹配的位数来判断两个点之间的大概距离。 
四、不足之处及解决方法 
1、边缘附近的点,黄色的点要比黑色的点更加靠近红点,但是由于黑点跟红点的GeoHash前缀匹配数目更多,因此得到黑点更加靠近红点的结果 
这里写图片描述 
解决方法: 
可以通过筛选周围8个区域内的所有点,然后计算距离得到满足条件结果。 
2、因为现有的GeoHash算法使用的是Peano空间填充曲线(可感兴趣的可自己查看),这种曲线会产生突变,造成了编码虽然相似但距离可能相差很大的问题,因此在查询附近的时候,首先筛选GeoHash编码相似的点,然后进行实际距离计算。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部