算法简介
geohash是实现空间索引的一种算法,其他实现空间索引的算法有:R树和其变种GIST树、四叉树、网格索引等
算法基本原理
geohash算法将地球理解为一个二维平面,将平面递归分解成更小的子块,每个子块在一定经纬度范围内拥有相同的编码,这种方式简单粗暴,可以满足对小规模的数据进行经纬度的检索
通过对经纬度的分割,将地球分割成无数的小正方形,每个区域,就是个geohash编码
Geohash其实就是将整个地图或者某个分割所得的区域进行一次划分,由于采用的是base32编码方式,即Geohash中的每一个字母或者数字(如wx4g0e中的w)都是由5bits组成(2^5 = 32,base32),这5bits可以有32中不同的组合(0~31),这样我们可以将整个地图区域分为32个区域,通过00000 ~ 11111来标识这32个区域。第一次对地图划分后的情况如下图所示(每个区域中的编号对应于该区域所对应的编码):
如图:
算法实现(php)
- 以经纬度值:(118.6197800000,24.88849)进行算法说明,对纬度24.88849进行逼近编码 (地球纬度区间是[-90,90])
- 纬度区间[-90,90]进行二分为[-90,0],[0,90],命名为左右区间,坐标属于右区间记为1,左区间为0,24.88849为右区间,记为1
- 对所在区间进行再次划分[0,90]二分为[0,45],[45,90],24.88849属于左区间,左区间记为0
- 以下是php的纬度区间算法函数:
|
- 由此,纬度24.88849可得字符串为10100011011001011001
- 经度118.6197800000,经度分为东经和西经,区间为[-180,180],由此可得字符串11010100010110100001
- 组合2个字符串,偶数放经度位,奇数放纬度位,php代码实现
|
- 每隔5位取出一串,转为10进制,最后使用[0-9][b-z]去掉a, i, l, o这32个字符进行编码.php代码实现
|
- 这样,就得到了一串'wskme6b3'字符串了,该字符串就表示了一个区域
geohash算法使用:
根据附录精度,传入经纬度生成geohash编码,存入数据库,例如:
当需要查询附近某个区域块点时,只需要,就可以查出该区域块所有数据
|
用法补充:
当碰到需要渲染一整个地图,而数据量大的时候怎么办?总不可能把几千万的点全部查出来渲染吧?
可以新增一个大区域块统计表,将精度更小的数据进行分组并且统计总数,例如:
gps_id无用字段,请忽略
查出精度为2的数据:
当地图放大时:可相应的查出:level=3,level=4.....等等数据
精度bug
一:如图:
当查询红点所在区域时,数据库只能查询到该区域块右下角的点,而找不到离他更近的上面的绿点
该bug可通过查询周围8个区域块进行再次比对,或者增加精度到厘米级别,就可忽略该bug
附录:geohash精度
php扩展
php已经实现了对geohash的扩展,
传送门:https://www.oschina.net/news/48848/geohash-1-1
其他补充
等有时间,将会把geohash解码算法发出来