1.Geohash 算法简介
Geohash 是一种地理编码,由 Gustavo Niemeyer 发明的。它是一种分级的数据结构,把空间划分为网格。Geohash 属于空间填充曲线中的 Z 阶曲线(Z-order curve)的实际应用。
Geohash 能够提供任意精度的分段级别。一般分级从 1-12 级。
我们可以利用 Geohash 的字符串长短来决定要划分区域的大小。这个对应关系可以参考上面表格里面 cell 的宽和高。一旦选定 cell 的宽和高,那么 Geohash 字符串的长度就确定下来了。这样我们就把地图分成了一个个的矩形区域了。
地图上虽然把区域划分好了,但是还有一个问题没有解决,那就是如何快速的查找一个点附近邻近的点和区域呢?
Geohash 有一个和 Z 阶曲线相关的性质,那就是一个点附近的地方(但不绝对) hash 字符串总是有公共前缀,并且公共前缀的长度越长,这两个点距离越近。
由于这个特性,Geohash 就常常被用来作为唯一标识符。用在数据库里面可用 Geohash 来表示一个点。Geohash 这个公共前缀的特性就可以用来快速的进行邻近点的搜索。越接近的点通常和目标点的 Geohash 字符串公共前缀越长(但是这不一定,也有特殊情况,下面举例会说明)
geohash各级别误差:
Geohash 也有几种编码形式,常见的有2种,base 32 和 base 36。
base32编码:是用0-9、b-z(去掉a, i, l, o)这32个字母进行编码。(一般选32)
base 36 的版本对大小写敏感,用了36个字符,“23456789bBCdDFgGhHjJKlLMnNPqQrRtTVWX”。
2.为什么要使用GeoHash
需求:地图app 界面上会显示出自己附近一个范围内可用的出租车或者共享单车。假设地图上会显示以自己为圆心,5公里为半径,这个范围内的车。如何实现呢?
查询数据库所有的车的位置信息,计算出与自己的距离,筛选出距离小于等于5公里的,然后再推数据界面显示,非常耗时。
如果采用geoHash,只用模糊查询自身点的geohash编码的前几位,来模糊查询附近的geohash点,再关联该点的出租车或共享单车。以存geohash的字段建立索引,加快查询效率。
3.Geohash 实际应用举例
地图中间有一个美罗城,假设需要查询距离美罗城最近的餐馆,该如何查询?
第一步我们需要把地图网格化,利用 geohash。通过查表,我们选取字符串长度为6的矩形来网格化这张地图。
经过查询,美罗城的经纬度是[31.1932993, 121.43960190000007]。
先处理纬度。地球的纬度区间是[-90,90]。把这个区间分为2部分,即[-90,0),[0,90]。31.1932993位于(0,90]区间,即右区间,标记为1。然后继续把(0,90]区间二分,分为[0,45),[45,90],31.1932993位于[0,45)区间,即左区间,标记为0。一直划分下去。
再处理经度,一样的处理方式。地球经度区间是[-180,180]
纬度产生的二进制是101011000101110,经度产生的二进制是110101100101101,按照“偶数位放经度,奇数位放纬度”的规则,重新组合经度和纬度的二进制串,生成新的:111001100111100000110011110110,最后一步就是把这个最终的字符串转换成字符,对应需要查找 base-32 的表。11100 11001 11100 00011 00111 10110转换成十进制是 28 25 28 3 7 22,查表编码得到最终结果,wtw37q。
4.Geohash 具体代码实现
实现思路:
1.经纬度,按照[-90,90],[-180,180]逐渐二分,在左区间为0,在右区间为1,得到二进制编码,具体要得到多少位的二进制,看选取的精度,5位二进制对应1位geoHash,一般选8位的geoHash,所以经纬度单独编码为20位
2.合并经纬度,偶数位放经度,奇数位放纬度,注意第一位是0,放偶数,简单理解,经度纬度经度纬度…叠加
3.每5位对应以为base32编码,转译一下就得到了GeoHash编码
GeoHash转经纬度,反之即可,只是geohash代码的是一块区域,转换后的经纬度是区域的中心点的经纬度。
geoHash实现的样例代码参考另一篇博文:
java代码实现
5.Geohash 使用注意点
由于GeoHash是将区域划分为一个个规则矩形,并对每个矩形进行编码,这样在查询附近信息时会导致以下问题,比如红色的点是我们的位置,绿色的两个点分别是附近的两个餐馆,但是在查询的时候会发现距离较远餐馆的GeoHash编码与我们一样(因为在同一个GeoHash区域块上),而较近餐馆的GeoHash编码与我们不一致。这个问题往往产生在边界处。
解决的思路很简单,我们查询时,除了使用定位点的GeoHash编码进行匹配外,还使用周围8个区域的GeoHash编码,这样可以避免这个问题。