查看原文
其他

揭秘!是什么能让APP快速精准定位?

smallyang 云加社区 2022-06-14


导语 | 我们在使用APP时,是什么能让它快速精准定位我们的具体位置?答案就是geohash。那究竟什么是geohash呢?它的原理是什么?它又帮助我们解决了哪些痛点,本文帮你逐一击破,且听我娓娓道来。



一、日常生活中遇到哪些定位的场景


我们上下班经常会用APP打车和共享单车,下图应该都很熟悉,打开定位,查找我附近的车,那么,这个是怎么实现的呢?



我脑海中第一个实现方式是:实时上报经纬度。在数据库里,把经纬度都标记为索引,通过查找对比经纬度的值,来找到附近1km的车子,但是这种做法第一是索引比较多,数值比较大,二是需要循环遍历经纬度,查询会很慢,效率很低。


那么,这些APP是怎么做到,既能精准定位,又能快速查找呢?答案就是geohash

geohash通过算法将1个定位的经度和纬度2个数值,转换成1个hash字符串。如果2个地方距离越近,那么他们的hash值的前缀越相同。然后通过数据库中like操作符“like wtw366%”快速查找到附近的车。


比如上海腾讯大厦的经纬度是:(31.1688749, 121.3975184),那么转换成geohash就是wtw366ngz5qt,我们想找附近的车子,可以用:


select * from cart where geohash like 'wtw366%' ;
select * from cart where LEFT(geohash, 6) = 'wtw366';



二、简单复习一下经纬度


在大致了解什么是geohash之后,我们先来复习一下什么是经纬度(高中学的,可能已经忘记光了(逃)),这对于理解geohash有很大的帮助。

我们将地球铺平开来,会得到下面这个平面图:



以赤道和本初子午线为界,将地球分为经度和纬度。赤道是在0度,本初子午线也在0度。以赤道作为经度X横坐标,以本初子午线作为纬度Y竖坐标:



经度(longitude)和纬度(latitude)简称lng和lat


其中,从本初子午线向东划分180度称为东经,用”E”表示:(0, 180];向西划分180度为西经,用“W”表示:[-180, 0)。


以赤道为0度,向南北各分出90度,南北极的读数均是90度,北纬用“N”表示 :(0, 90] ,南纬用“S”表示: [-90, 0)。


注意:纬线和纬线是角度数值,并不是米。[表示等于,(表示小于。


所以,我们常用十字坐标法来表示经纬度坐标图:



注意:我们一般读“经纬度”,其实,表示一个定位的书面经纬度是 “(纬度,经度)”。


比如上海腾讯大厦的定位就是:(31.1688749, 121.3975184)表示的是:纬度=31.1688749,经度=121.3975184。




三、geohash原理解析


在了解什么是经纬度之后,现在我们就可以开始来说下geohash的原理了,geohash通过以下步骤,实现了将一个经纬度数子串,转换成1个hash字符串。


  1. 指定一个位置的经纬度坐标值。


  2. 根据十字坐标图和二分法,将纬度和经度划分成1和0的二进制数字串。


  3. 按照“偶数位放经度,奇数位放纬度”算法,合并经度和纬度这2个二进制数字串。


  4. 合并后的二进制数字串,按照从前往后,每隔5位,换算成十进制数字,最后不足5位的用0补齐。


  5. 十进制数字,对应base32字符串算法的所在位置,一一匹配,得到了最后的字符串结果。


  6. 按照进度划分截取,得到最终的geohash值。


我们按照这个顺序,结合实际的例子,依次计算操作一下。



(一)找出一个位置的经纬度


我们可以用各种地图和定位工具,比如依靠Google地图,通过定位或者搜索一个地点,就容易找出经纬度。



这样,我们就找出了上海腾讯大厦的经纬度是(31.1688749, 121.3975184)。



(二)将经纬度按照二分算法变成01二进制


上海腾讯大厦的经纬度是(31.1688749, 121.3975184)。将纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90),如果目标纬度位于前一个区间,则编码为0,否则编码为1。


  • 由于31.1688749属于(0, 90),所以取编码为1。

  • 然后再将(0, 90)分成 (0, 45), (45, 90)两个区间,而31.1688749位于(0, 45),所以编码为0。


  • 然后再将(0, 45)分成 (0, 22.5), (22.5, 45)两个区间,而31.1688749位于(22.5, 45),所以编码为1。

依次类推可得上海腾讯大厦纬度编码为:


101011000101010000111101101101


经度也用同样的算法,对(-180, 180)依次细分,(-180,0)、(0,180) ,得出编码为:


110101100101001110111110011010


我们用php代码来具体实现一下这个算法:


//纬度$minLat = -90;$maxLat = 90;
//经度$minLng = -180;$maxLng = 180;
//2分查找计算,将经纬度转换成二进制数字串$latLength = $lngLength = 0;$latList = $lngList = [];
//$precision 精度最大是12,代表12个字符,1个字符由5个二进制组成,也就是 12 * 5 = 60//精度和纬度对半开,得除以2,也就是最大长度为30个二进制。
$originPrecision = 30;
//纬度while ($latLength < $originPrecision) {
//大于中间值,则为右区间,值为1 ,反之,则为0 if ($lat >= $middle = ($minLat + $maxLat) / 2) { $latList[] = 1; $minLat = $middle; } else { $latList[] = 0; $maxLat = $middle; }
$latLength++;}
//经度while ($lngLength < $originPrecision) {
//大于中间值,则为右区间,值为1 ,反之,则为0 if ($lng >= $middle = ($minLng + $maxLng) / 2) { $lngList[] = 1; $minLng = $middle; } else { $lngList[] = 0; $maxLng = $middle; }
$lngLength++;}
var_dump(implode("", $latList), implode("", $lngList));die;



(三)偶数位放经度,奇数位放纬度


通过二分算法,我们得到了腾讯大厦的纬度和经度的二进制串为:


string(30) "101011000101010000111101101101"string(30) "110101100101001110111110011010"

现在需要按照"偶数位放经度,奇数位放纬度",将这2个数字串,合二为一。那么这个到底怎么理解呢?我刚开始不理解到底怎么操作,后来经过一系列的思考,可以如下操作:



无法用文字表述,我截了个操作图,如图上的箭头操作顺序所示,就是把纬度往右移动一个位置,然后依次串起来。


用php代码实现,或许看起来更好理解:


//偶数位放经度,奇数位放纬度$stringList = ''; for ($i = 0; $i < 30; $i++) { $stringList .= $lngList[$i]; $stringList .= $latList[$i];}var_dump($stringList);die;


这样,合并之后,我们得了一个60个字符长度的的二进制数字串:


string(60) "111001100111100000110011000110101000111111111001011011011001"



(四)二进制转换成十进制


我们把这个60位的二进制,按照从左往右,每5位划分成1个组,最后一组如果不足5位就用0补齐到5位。划分后如下所示:


11100 11001 11100 00011 00110 00110 10100 01111 11111 00101 10110 11001


然后,把分好的二进制,转换成十进制:


28 25 28 3 6 6 20 15 31 5 22 25


用php实现也很简单:


$stringList = "111001100111100000110011000110101000111111111001011011011001";
//二进制转成十进制,5个一组$stringListLen = strlen($stringList) / 5;$code = [];for ($i = 0; $i < $stringListLen; $i++) { $code[] = bindec(substr($stringList, 5 * $i, 5));}
var_dump(implode(" ",$code));die;



(五)匹配对应base32表算法的所在位置


base32表是用0-9、b-z(去掉a, i, l, o)这32个字母进行组合的编码集合,base-32如下所示:


0123456789bcdefghjkmnpqrstuvwxyz


为了更好理解和一一对应,我们把base32各个字符的位置信息和它的字符串用表对应起来:



所以,28 25 28 3 6 6 20 15 31 5 22 25对应上面的表的位置就得到了:


wtw366ngz5qt


同样,我们也用php算法来实现一下:


//base32 映射$base32Code = "0123456789bcdefghjkmnpqrstuvwxyz";$encodeString = '';foreach ($code as $value) { $encodeString .= $base32Code{$value};}
var_dump($encodeString);die;


这样,最后我们得到了,上海腾讯大厦的经纬度(31.1688749, 121.3975184)所对应的geohash为wtw366ngz5qt。



四、geohash的精度问题


geohash其实表示的是一个矩形的块状区间,它总共分成最大12个字符串,也就是表示从1-12级。字符数越大,块区间就越小,那么定位就越精准。


我们刚才计算上海腾讯大厦的geohash采用的是12级,基本计算出来的位置就是毫米级别了,可以说是非常的精准了。



上面是geohash字符串长度对应的区间精度,我们可以看到,当geohash为12位时,表示是37毫米范围的区间,已经是非常的精准了。当geohash为6位时,表示为1.2k米范围内的矩形位置。


所以,当2个定位的geohash前7位是一样的时,表示他们在附近1.2km的范围内。


那我们还是用腾讯大厦的geohash值,分别截取经度为前7,6,5位看看,在地图上是怎么样的:





所以,根据上面的图,随着字符越来越少,精度越来越小,这个矩形也越来越大,这一整块区间都共用一个geohash来表示。在实际应用中,我们就可以动态的调整精度,实现更大或者更小范围内的搜索,既能精准定位,又可以隐藏住一个地点的具体区位信息。



五、geohash存在的边界问题


由于geohash表示的是一个区块信息,在同一个区块里的2个位置,它会认为是最近的,然而,其实更近的位置可能刚好在另一个区间,这样就造成了不匹配的问题。这就存在一个边界问题。


我们用实际例子来看。我们想找腾大附近1.5km范围内的便利店,我们选取geohash精度为6。园区有2家A和B。B距离我们更近一点,但是,由于A和腾大在一个hash区块内,所以,就得出了A是最佳的选择。这就是边界的问题。




六、如何解决边界问题


那么如何解决这个边界问题,给出最近最优的算法方案呢?答案就是:把定位附近的8个方向的geohash都算出来。最后分别计算这些点和自己的距离(由于范围很小,点的数量就也很少,计算量就很少)过滤掉不满足条件的点就ok了。




七、计算两点距离的计算


通过余弦定理以及弧度计算方法,最终推导出来的算式A为:


$s = acos(cos($radLat1) * cos($radLat2) * cos($radLng1 - $radLng2) + sin($radLat1) * sin($radLat2)) * $R;


目前大多使用的是Google公开的距离计算公司,推导算式B为:


$s = 2*asin(sqrt(pow(sin(($radLat1-$radLat2)/2),2)+cos($radLat1)*cos($radLat2)*pow(sin(($radLng1-$radLng2)/2),2)))*$R;


其中:$radLat1, $radLng1, $radLat2,$radLng2为2个地点的经纬度弧度,$R为地球半径。


用PHP实现一下:


function getDistance($lat1, $lng1, $lat2, $lng2) { //地球半径 $R = 6378137; //将角度转为狐度 $radLat1 = deg2rad($lat1); $radLat2 = deg2rad($lat2); $radLng1 = deg2rad($lng1); $radLng2 = deg2rad($lng2); //结果 $s = acos(cos($radLat1)*cos($radLat2)*cos($radLng1-$radLng2)+sin($radLat1)*sin($radLat2))*$R; //精度 $s = round($s* 10000)/10000; return round($s);} /* *求两个已知经纬度之间的距离,单位为米 * @param lat1,lat2 纬度 * @param lng1,lng2 经度 * @return float 距离,单位米*/function getDistanceByGoogle($lat1, $lng1, $lat2, $lng2){ //地球半径 $R = 6378137; //deg2rad()函数将角度转换为弧度 $radLat1 = deg2rad($lat1); $radLat2 = deg2rad($lat2); $radLng1 = deg2rad($lng1); $radLng2 = deg2rad($lng2); $a = $radLat1 - $radLat2; $b = $radLng1 - $radLng2; $s = 2 * asin(sqrt(pow(sin($a / 2), 2) + cos($radLat1) * cos($radLat2) * pow(sin($b / 2), 2))) * $R; return $s;}



八、geohash在redis中的实现


redis在3.2.0中加入了geo相关的命令,对geohash的支持。


redis中经纬度使用52位的整数进行编码,放进zset中,zset的value元素是key,score是GeoHash的52位整数值。在使用redis进行Geo查询时,其内部对应的操作其实只是zset(skiplist)的操作。通过zset的score进行排序就可以得到坐标附近的其它元素,通过将score还原成坐标值就可以得到元素的原始坐标


redis中处理这些地理位置坐标点的思想是:二维平面坐标点-->一维整数编码值-->zset(score为编码值)-->zrangebyrank(获取score相近的元素)、zrangebyscore-->通过score(整数编码值)反解坐标点-->附近点的地理位置坐标。


redis中有6个命令,对地理位置的算法支持,可以去redis官网具体查看其用法:(https://redis.io/commands#geo)。



 作者简介


杨义(smallyang)

腾讯高级工程师

腾讯高级工程师,主要负责IEG游戏活动运营及高可用平台的建设,对云服务、k8s以及高性能服务上也有很深的了解。



 推荐阅读


人机共生时代,分布式机器学习是如何加速的?

手把手教你快速理解gRPC!

golang:快来抓住让我内存泄漏的“真凶”!

一文读懂@Decorator装饰器——理解VS Code源码的基础(下)





您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存