GeoHash -------寻找附近人

2019/06/03 14:35
阅读数 22
当两个元素的距离不是很远时,可以直接使⽤勾股定理就能算得元素之间的距离。我们平时使⽤的「附近的⼈」的功能,元素距离都不是很⼤,勾股定理算距离⾜矣。不过需要注意的是,经纬度坐标的密度不⼀样 (地球是⼀个椭圆),勾股定律计算平⽅差时之后再求和时,需要按⼀定的系数⽐加权求和,如果不求精确的话,也可以不必加权。
业界⽐较通⽤的地理位置距离排序算法是 GeoHash 算法,Redis 也使⽤ GeoHash 算法。GeoHash 算法将⼆维的经纬度数据映射到⼀维的整数,这样所有的元素都将在挂载到⼀条线上,距离靠近的⼆维坐标映射到⼀维后的点之间距离也会很接近。当我们想要计算「附近的⼈时」,⾸先将⽬标位置映射到这条线上,然后在这个⼀维的线上获取附近的点就⾏了。那这个映射算法具体是怎样的呢?它将整个地球看成⼀个⼆维平⾯,然后划分成了⼀系列正⽅形的⽅格,就好⽐围棋棋盘。所有的地图元素坐标都将放置于唯⼀的⽅格中。⽅格越⼩,坐标越精确。然后对这些⽅格进⾏整数编码,越是靠近的⽅格编码越是接近。那如何编码呢?⼀个最简单的⽅案就是切蛋糕法。设想⼀个正⽅形的蛋糕摆在你⾯前,⼆⼑下去均分分成四块⼩正⽅形,这四个⼩正⽅形可以分别标记为 00,01,10,11 四个⼆进制整数。然后对每⼀个⼩正⽅形继续⽤⼆⼑法切割⼀下,这时每个⼩⼩正⽅形就可以使⽤ 4bit 的⼆进制整数予以表示。然后继续切下去,正⽅形就会越来越⼩,⼆进制整数也会越来越⻓,精确度就会越来越⾼。

增加

geoadd 指令携带集合名称以及多个经纬度名称三元组,注意这⾥可以加⼊多个三元组
127.0.0.1:6379> geoadd company 116.48105 39.996794 juejin
(integer) 1
127.0.0.1:6379> geoadd company 116.514203
(error) ERR wrong number of arguments for 'geoadd' command
127.0.0.1:6379> geoadd company 116.514203 39.905409 ireader
(integer) 1
127.0.0.1:6379> geoadd company 116.489033 40.007669 meituan
(integer) 1
127.0.0.1:6379> geoadd company 116.562108 39.787602 jd 116.334255 40.027400 xiaomi
(integer) 2
也许你会问为什么 Redis 没有提供 geo 删除指令?前⾯我们提到 geo 存储结构上使⽤的是 zset,意味着我们可以使⽤ zset 相关的 指令来操作 geo 数据,所以删除指令可以直接使⽤ zrem 指令即 可。

距离

geodist 指令可以⽤来计算两个元素之间的距离,携带集合名称、2个名称和距离单位。距离单位可以是m、km、ml、ft,分别代表⽶、千⽶、英⾥和尺。
127.0.0.1:6379> geodist company juejin ireader km
"10.5501"
127.0.0.1:6379> geodist company juejin meituan km
"1.3878"
127.0.0.1:6379> geodist company juejin xiaomi km
"12.9606"

获取元素位置

geopos 指令可以获取集合中任意元素的经纬度坐标,可以⼀次获取多个。
127.0.0.1:6379> geopos company juejin
1) 1) "116.48104995489120483"
   2) "39.99679348858259686"
127.0.0.1:6379> geopos company juejin ireader
1) 1) "116.48104995489120483"
   2) "39.99679348858259686"
2) 1) "116.5142020583152771"
   2) "39.90540918662494363"

获取元素的 hash 值

geohash 可以获取元素的经纬度编码字符串,上⾯已经提到,它是base32 编码。你可以使⽤这个编码值去 http://geohash.org/${hash}中进⾏直接定位,它是 geohash 的标准编码值。

geohash计算过程依据上述原理,接下来详细介绍一下geohash的计算过程,这里拿经纬度(116.389550, 39.928167)进行算法说明。

a. 纬度计算
中学学过的地理知识知道,地球分为南纬与北纬,分别都是0~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;依据最大精度,定义一个最大重复次数,这里我们定义为15,这样就能得出一个01字串;

b. 全局计算
经度计算与纬度计算类似,也是依据区间划分,左右判断来进行,这里就不在复述了,给出最终计算结果为:1 1 0 1 0 0 1 0 1 1 0 0 0 1 0,接下来就是如何通过经度与纬度的01字串,编码成相应的字母+数字的组合。将经度与纬度的01字串进行合并,合并方法为:基数为放纬度,偶数位放经度

  • 最终字串为:11011, 01110, 00010, 01111, 00001, 00100
  • 将字串转换成十进制,得到:27, 14, 2, 15, 1, 4
  • 对应base32编码表
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部