是什么能让 APP 快速精准定位到我们的位置?

本文作者:smallyang,腾讯 IEG 开发工程师

什么是geohash?它的原理是什么?它帮助我们解决了哪些痛点,本文为你娓娓道来。

本文包含以下内容,阅读完需要约10分钟:

  • 我们日常生活中遇到哪些定位的场景
  • 简单复习一下经纬度
  • geohash原理解析
  • geohash存在的边界问题
  • 如何解决边界问题
  • 计算两点距离的计算
  • geohash 在redis中的实现

我们日常生活中遇到哪些定位的场景

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

我脑海中第一个实现方式是:实时上报经纬度。在数据库里,把经纬度都标记为索引,通过查找对比经纬度的值,来找到附近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值。

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

1. 找出一个位置的经纬度

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

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

2. 将经纬度按照二分算法变成01二进制

上海腾讯大厦的经纬度是 (31.1688749, 121.3975184)

将纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90), 如果目标纬度位于前一个区间,则编码为0,否则编码为1。

  1. 由于31.1688749属于(0, 90),所以取编码为1。
  2. 然后再将(0, 90)分成 (0, 45), (45, 90)两个区间,而31.1688749位于(0, 45),所以编码为0。
  3. 然后再将(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;

3. 偶数位放经度,奇数位放纬度

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

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"

4. 二进制转换成十进制

我们把这个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;

5. 匹配对应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 为弧度
  • $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

GEOADD
GEOPOS
GEODIST
GEORADIUS
GEORADIUSBYMEMBER
GEOHASH

其他资料

  • geohash在线换算: http://geohash.co/
  • 换算+地图定位: https://www.movable-type.co.uk/scripts/geohash.html
Image placeholder
豆豆天尊
未设置
  100人点赞

没有讨论,发表一下自己的看法吧

推荐文章
jquery如何获取当前元素的位置?

jquery获取当前元素的位置,并且是相对于文档的位置。我们可以使用jQueryoffset()方法来实现。offset()方法仅适用于可见元素。下面我们结合简单的代码,给大家介绍jquery获取当前

css如何设置元素不显示仅占位置?

css如何设置元素不显示仅占位置?隐藏页面元素可以使用visibility:hidden属性,它将元素设置为不可见,并且占据原来的位置,不能响应点击事件。不可见 .hide{ visibility:

历史上最著名计算机病毒,似乎都成了我们的回忆

Windows勒索病毒似乎让全球计算机用户都闻风丧胆,不过这其实真的不算什么。然而令人始料不及的是,即便勒索病毒传遍了100多个国家,也仅仅才收获了5万美金。所以说勒索病毒真的不算啥。历史上比勒索病毒

快看,我们的分布式缓存就是这样把注册中心搞崩塌

写公众号两年以来,每当有机会写故障类主题的时候,我都会在开始前静静地望着显示器很久,经过多次煎熬和挣扎之后才敢提起笔来,为什么呢?因为这样的话题很容易招来吐槽,比如“说了半天,不就是配置没配好吗?”,

阿里巴巴为什么能抗住90秒100亿?看完这篇你就明白了!

1、概述本文以淘宝作为例子,介绍从一百个并发到千万级并发情况下服务端的架构的演进过程,同时列举出每个演进阶段会遇到的相关技术,让大家对架构的演进有一个整体的认知,文章最后汇总了一些架构设计的原则。2、

建立开放的大数据精准扶贫平台,让全社会参与进来!

精准扶贫”的重要思想最早是在2013年11月,习近平主席到湖南湘西考察时首次作出了“实事求是、因地制宜、分类指导、精准扶贫”的重要指示。2015年6月,习近平主席在贵州召开部分省区市党委主要负责同志座

搞个大事情,阿里如何实现上亿级数据的精准计数?

背景关系型数据库在执行计数任务时,其执行效率会随着数据量级的增长而降低;当数据量达到亿级别时,计数任务的执行效率已经低到令人不忍直视。在闲鱼团队的关系系统中,我们采用了这样一种方式来实现亿级别数据的毫

智联、前程无忧、58们的革命和被革命

近日,前程无忧发布三季度薪酬调研报告。从报告内容来看,2019年三季度的招聘市场用“冰火两重天”来形容,再合适不过。一方面,对于大部分求职者来说,企业“金九银十”的招聘旺季一点也不旺。受宏观经济环境的

深度复盘GitHub发展史:如何在短短10年内改变了人们的编程方式?

前不久,微软以75亿美元的价格收购GitHub,引发了科技行业的关注。在短短的10年内,GitHub改变了人们的编程方式。不仅让编程变得更简单,还改变了软件开发者对编程的看法。GitHub是如何做到的

记一次JVM FullGC引发严重线上事故的定位、分析、解决过程!

这篇文章给大家聊一次线上生产系统事故的解决经历,其背后代表的是线上生产系统的JVMFullGC可能引发的严重故障。一、业务场景介绍先简单说说线上生产系统的一个背景,因为仅仅是文章作为案例来讲,所以弱化

SQL优化案例-定位系统中大量的rollback(十八)

系统中logfilesync比较严重,查看存储都没有问题,logfileparallelwrite很低,时间分布直方图也没问题数据库中提交和回滚操作比较频繁,每秒1000多次,rollback占比1/

如何进行I/O评估、监控、定位和优化?

生产中经常遇到一些IO延时长导致的系统吞吐量下降、响应时间慢等问题,例如交换机故障、网线老化导致的丢包重传;存储阵列条带宽度不足、缓存不足、QoS限制、RAID级别设置不当等引起的IO延时。本文由社区

css怎么去除定位?

如果没有指定元素的position属性值,也就是默认情况下,元素也是静态定位。只要是支持position属性的html对象都是默认为static。static是position属性的默认值,它表示块保

css怎么定位?

position属性规定元素的定位类型。这个属性定义建立元素布局所用的定位机制。任何元素都可以定位,不过绝对或固定元素会生成一个块级框,而不论该元素本身是什么类型。相对定位元素会相对于它在正常流中的默

css定位(position)属性怎么用?

position属性规定元素的定位类型。说明position属性定义建立元素布局所用的定位机制。任何元素都可以定位,不过绝对或固定元素会生成一个块级框,而不论该元素本身是什么类型。相对定位元素会相对于

css中ul怎么定位

css中ul怎么定位css中所有的元素默认都是static定位,要改变ul的定位方式,我们只需要指定元素的cssposition属性即可。关于定位的几种方式1、static定位(普通流定位)--默认定

CSS粘性定位(position: sticky)是怎样工作的?

浏览器对CSS粘性定位有着非常好的支持,但很多开发者都没有用过它。究其原因有两个: ● 第一,受到浏览器的良好支持需要漫长的等待:浏览器的支持往往需要很长的时间才能完成,到时候它的功能已经被人们遗忘了

css怎么设置粘性定位?

css怎么设置粘性定位?粘性定位的设置方法是给元素添加position:sticky;,sticky是css定位新增属性,类似static(没有定位)和固定定位fixed的结合。它主要用在对scrol

css定位怎么实现居中?

css定位怎么实现居中?使用绝对定位absolute是一种常用、兼容性很好的方式。.element{ width:600px;height:400px; position:absolute; left

css如何设置字体位置

css如何设置字体位置1、text-align设置字体的位置text-align语法:text-align:left|right|center|justifytext-align参数值与说明:left

css文字水平垂直居中怎么设置?

1、文字水平居中在CSS中想要让文字水平居中,可以使用text-align:center;。text-align是一个基本的属性,它会影响一个元素中的文本行互相间的对齐方式。值left、right和c

css图片属性如何设置?

css图片属性如何设置?首先新建一个style标签;然后在style标签内使用语法img{属性:值}即可,比如设置图片边框属性img{border:1pxsolidred}。语法:img{ 属性:值;

app.vue是什么文件?

app.vue是vue页面资源的首加载项,是主组件,页面入口文件,所有页面都是在App.vue下进行切换的;也是整个项目的关键,app.vue负责构建定义及页面组件归集。 exportde

app.vue的作用是什么?

app.vue的作用是什么?app.vue可以当做是网站首页,是一个vue项目的主组件,页面入口文件,所有页面都是在App.vue下进行切换的。是整个项目的关键,app.vue负责构建定义及页面组件归

create-react-app是什么?

create-react-app是用于搭建react项目的脚手架。它的优势在于省略了很多涉及配置的地方,让新手能够更加容易上手,减低入门的门槛。使用脚手架create-react-app1.准备工作操