geohash基本原理及算法

geohash基本原理是将地球理解为一个二维平面,将平面递归分解成更小的子块,每个子块在一定经纬度范围内拥有相同的编码,这种方式简单粗暴,可以满足对小规模的数据进行经纬度的检索。

目录:

经纬度常识

认识geohash

geohash算法

geohash原理

对照表

经纬度常识

经线是纵的,经度是横的,用于表示不同的经线,纬线是横的,纬度是纵的,用于表示不同的纬线,如下图

纬线:地球仪上的横线,lat,赤道是最大的纬线,从赤道开始分为北纬和南纬,都是0-90°,纬线是角度数值,并不是米;

经线:地球仪上的竖线,lng,子午线为0°,分为西经和东经,都是0-180°,经线也是角度数值;

经纬线和米的换算:经度或者纬度0.00001度,约等于1米,这个在GPS测算距离的时候可以体会到,GPS只要精确到小数点后五位,就是10米范围内的精度

经度0度的位置为本初子午线,在180度的位置转为西经,数字由大到小依次经过北美洲到达西欧.纬度0度的位置为赤道

为了便于理解,将地球看成一个基于经纬度线的坐标系。纬线就是平行于赤道平面的那些平面的周线,经线就是连接南北两极的大圆线的半圆弧。纬度分为北纬(正),南纬(负),赤道所在的纬度值为0。经度以本初子午线界(本初子午线经度为0),分为东经(正),西经(负)。故纬度范围可表示为[-90, 0),(0, 90],经度范围可表示为[-180, 0),(0, 180]

将经度和纬度看成二维坐标系中的两个纬度,横轴表示经度,纵轴表示纬度,如上图

认识geohash

GeoHash将二维的经纬度转换成字符串,比如下图展示了北京9个区域的GeoHash字符串,分别是WX4ER,WX4G2、WX4G3等等,每一个字符串代表了某一矩形区域。也就是说,这个矩形区域内所有的点(经纬度坐标)都共享相同的GeoHash字符串,这样既可以保护隐私(只表示大概区域位置而不是具体的点),又比较容易做缓存。

不同的编码长度,表示不同的范围区间,字符串越长,表示的范围越精确

字符串相似的表示距离相近(特殊情况后文阐述),这样可以利用字符串的前缀匹配来查询附近的POI信息。如下两个图所示,一个在城区,一个在郊区,城区的GeoHash字符串之间比较相似,郊区的字符串之间也比较相似,而城区和郊区的GeoHash字符串相似程度要低些

总结:GeoHash就是一种将经纬度转换成字符串的方法,并且使得在大部分情况下,字符串前缀匹配越多的距离越近

geohash算法

以经纬度值:(116.389550, 39.928167)进行算法说明,对纬度39.928167进行逼近编码 (地球纬度区间是[-90,90])

区间[-90,90]进行二分为[-90,0),[0,90],称为左右区间,可以确定39.928167属于右区间[0,90],给标记为1

接着将区间[0,90]进行二分为 [0,45),[45,90],可以确定39.928167属于左区间 [0,45),给标记为0

递归上述过程39.928167总是属于某个区间[a,b]。随着每次迭代区间[a,b]总在缩小,并越来越逼近39.928167

如果给定的纬度x(39.928167)属于左区间,则记录0,如果属于右区间则记录1,序列的长度跟给定的区间划分次数有关,如下图

同理,地球经度区间是[-180,180],可以对经度116.389550进行编码

通过上述计算,纬度产生的编码为1 1 0 1 0 0 1 0 1 1 0 0 0 1 0,经度产生的编码为1 0 1 1 1 0 0 0 1 1 0 0 0 1 1

合并:偶数位放经度,奇数位放纬度,把2串编码组合生成新串如下图:

首先将11100 11101 00100 01111 0000 01101转成十进制,对应着28、29、4、15,0,13 十进制对应的base32编码就是wx4g0e,如下图

Ø同理,将编码转换成经纬度的解码算法与之相反

geohash原理

Geohash其实就是将整个地图或者某个分割所得的区域进行一次划分,由于采用的是base32编码方式,即Geohash中的每一个字母或者数字(如wx4g0e中的w)都是由5bits组成(2^5 = 32,base32),这5bits可以有32中不同的组合(0~31),这样我们可以将整个地图区域分为32个区域,通过00000 ~ 11111来标识这32个区域。第一次对地图划分后的情况如下图所示(每个区域中的编号对应于该区域所对应的编码):

Geohash的0、1串序列是经度0、1序列和纬度0、1序列中的数字交替进行排列的,偶数位对应的序列为经度序列,奇数位对应的序列为纬度序列,在进行第一次划分时,Geohash0、1序列中的前5个bits(11100),那么这5bits中有3bits是表示经度,2bits表示纬度,所以第一次划分时,是将经度划分成8个区段(2^3 = 8),将纬度划分为4个区段(2^2 = 4),这样就形成了32个区域。如下图

同理,可以按照第一次划分所采用的方式对第一次划分所得的32个区域各自再次划分.

对照表

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180506G14IVY00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券