GeoHash——滴滴打车如何找出方圆一千米内的乘客?

这篇具有很好参考价值的文章主要介绍了GeoHash——滴滴打车如何找出方圆一千米内的乘客?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

背景

不知道大家是否思考过一个问题,在一些场景下(如大家在使用高德地图打车的时候,邻近的司机是如何知道你在他的附近并将你的打车通知推送给他去接单的?)是如何实现的?

一般来讲,大家也许会想到,首先肯定需要知道每位乘客的经纬度(lng,lat),也即是二维坐标(当然这是在绝对理想的情况,不考虑上下坡度)。

而在知道了经纬度之后,一个暴力简单且容易想到的思路就是将经纬度这个二元组都存放在一个数组当中,然后当我们需要拿到离我们规定范围内的用户(如获取当前位置方圆百米内正在打车的乘客),我们就可以去遍历维护的那个数组,以此去判断数组中的经纬度与自己所在经纬度的距离,然后判断是否在范围内。

显然这种方法一定是能够达到目的的,但是值得注意的点是,维护的数据量一般来讲是海量的,因此如果每次都需要遍历所有数据去进行计算,那这计算量以及存储量目前是无法满足的。那如何在此基础上去优化性能呢??那么这个内容就是本篇文章主要想探讨的问题…


GeoHash基本原理介绍

首先我想先介绍一下GeoHash这种算法基本原理,再讨论如何进行应用。

对于每一个坐标都有它的经纬度(lng,lat),而GeoHash的原理就是将经纬度先通过一个二分的思路拿到一个二进制数组的字符串,然后再通过base32编码去进行压缩存储。

举一个例子,比如经纬度为(116.3111126,40.085003),对其进行二分步骤如下:

经度步骤:

bit left mid right
1 -180 0 180
1 0 90 180
0 90 135 180
1 90 112.5 135
0 112.5 123.75 135
0 112.5 118.125 123.75
1 112.5 115.3125 118.125
0 115.3125 116.71875 118.125
1 115.3125 116.015625 116.71875
0 116.015625 116.3671875 116.71875
1 116.015625 116.19140625 116.3671875
1 116.19140625 116.279296875 116.3671875
0 116.279296875 116.323242188 116.3671875
1 116.279296875 116.301269532 116.323242188
0 116.301269532 116.31225586 116.323242188

纬度步骤:

bit left mid right
1 -90 0 90
0 0 45 90
1 0 22.5 45
1 22.5 33.75 45
1 33.75 39.375 45
0 39.375 42.1876 45
0 39.375 40.78125 42.1876
1 39.375 40.078125 40.78125
0 40.078125 40.4296875 40.78125
0 40.078125 40.25390625 40.4296875
0 40.078125 40.166015625 40.25390625
0 40.078125 40.1220703125 40.166015625
0 40.078125 40.1000976563 40.1220703125
0 40.078125 40.0891113282 40.1000976563
1 40.078125 40.0836181641 40.0891113282

其思路就是不断二分,如果原本值大于mid那本bit位就是1,以此往下递归,最终,我们递归二分得到纬度方向上的二进制字符串为 101110010000001,长度为 15 位

那此时就拿到了30bit位的字符串,然后就开始进行拼接

结合经度字符串 110100101011010和纬度字符串 101110010000001,我们遵循先经度后纬度的顺序,逐一交错排列,最终得到的一维字符串为 11100 11101 00100 11000 10100 01001.

然后再进行Base32编码,主要步骤就是首先会维护一个0-9A-Za-z中32个字符的数组,如:[‘a’,‘b’,‘1’,‘2’,‘3’,‘4’,‘5’,‘6’,‘7’,‘A’…],然后再将这30位的字符串每五个一组(正好覆盖0-31的索引)去索引到指定字符以此拿到30/5=6位的base32编码去进行存储。

ps:注意并不一定是必要将经纬度都二分得到15位长度,多少位都可以,只是精度越高结果也就越精确,但是算力就越大,只需在此做出权衡即可


GeoHash如何应用到这个问题当中?

上面讲到了可以通过GeoHash将经纬度转换成bit位的字符串,那么怎么进行应用呢,其实答案很明显,其实如果经纬度越接近,他们的前缀匹配位数也就越长,比如

image.png
通过这个思路我们就比较容易得到我们想要的范围内的乘客了。

遗留问题

但是其实仅仅如此是不够的,因为一个base32其实是覆盖了一片区域的,它并不是说仅仅代表一个精确的ip地址,那这其实就衍生出了一些问题,就比如

image.png
,用geohash那结果显然是AB更近,但是实际上A与B的距离比AE、AC、AD都远。这其实是一个边缘性的问题…后续我会更新如何去避免这种问题的出现文章来源地址https://www.toymoban.com/news/detail-670993.html

到了这里,关于GeoHash——滴滴打车如何找出方圆一千米内的乘客?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 如何修改JAR包内的代码

    有时候由于找不到源码,只有一个jar包,但又想去修改jar包中的代码,就可以进行将jar包反编译后,修改,再重新编译的方式来实现。 一、下载反编译软件JD-GUI https://github.com/java-decompiler/jd-gui/releases 二、用JD-GUI打开所要修改代码的jar包 三、将要修改的代码复制到一个新的

    2024年02月08日
    浏览(34)
  • 如何快速找出路由器毛故障及解决方法

    对于路由器出现故障,相信每一个网管几乎每天都会遇到,本篇介绍的是如何快速找出思科路由器一些常见的故障,以方便大家在遇到问题时,能够及时找出原因所在,尽量将损失减小。 一、路由器奇偶错误 如果奇偶错误只一次出现,路由器会认为只是单独事件干扰并且不

    2024年02月05日
    浏览(48)
  • 【ARM 调试】如何从 crash 信息找出问题原因

    粉丝在进行 ARM-A 系列软件编程时遇到以下问题,串口打印这段日志后就重启了,粉丝求助问是什么原因?  我们来先看第一段:         这里主要将发生问题时的相关的寄存器 dump 出来,包括通用寄存器 x0 ~ x29,EL3/EL1 模式下的控制寄存器和状态寄存器以及 GIC 相关寄存器。

    2024年02月13日
    浏览(35)
  • ORACLE如何找出视图依赖的对象和视图嵌套层数

    之前写过一篇文章“SQL Server如何找出视图依赖的对象和视图嵌套层数”,这里我介绍一下Oracle数据库中如何找出视图的依赖对象以及视图嵌套层数关系。主要通过DBA_DEPENDENCIES这个系统视图(这个系统视图中包含有对象的依赖关系数据)。另外,我们使用了Oracle的树形查询(

    2024年02月08日
    浏览(35)
  • 如何自定义iview树形下拉内的内容

    1.使用render函数给第一层父级定义  2. 使用树形结构中的render函数来定义子组件  3.呈现结构  

    2024年02月10日
    浏览(36)
  • chatgpt赋能python:Python如何找出列表中相同的元素

    在 Python 编程中,我们常常需要在列表中找出相同的元素,这样能帮助我们更快速地处理数据和优化代码的效率。在本文中,我们将介绍几种不同的方法来找出 Python 列表中相同的元素。 使用 for 循环是最简单的方法来找出列表中相同的元素。我们可以利用嵌套 for 循环,逐一

    2024年02月14日
    浏览(48)
  • Redis如何找出大量以某一个前缀开头的key

    Redis如何找出大量以某一个前缀开头的key 使用keys命令 KEYS命令是一个非常耗费资源的命令,它需要在Redis中遍历整个键空间,因此应该尽量避免在生产环境中使用。如果需要查找的key非常多,可以考虑使用SCAN命令,或者使用其他更高效的方式来实现类似的功能。 SCAN命令 SCA

    2024年02月20日
    浏览(44)
  • 如何跟踪IP地址找出某个地址范围内哪些没有被使用

    作为网管员,在我们解决Windows 操作系统的DHCP故障时,有时要找出某个地址范围内有哪些地址没有被使用。本人以前介绍过一种方法:打开命令提示窗口,在For…in…Do循环中调用ping命令。 例如,为了找出在地址范围192.168.1.1 到 192.168.1.100有哪些地址没有被使用,可以使用这

    2024年02月05日
    浏览(38)
  • Geohash算法原理及实现

    最近需要实现一个功能,查找车辆附近的加油站,如果车和加油站距离在200米以内,则查找成功。 加油站数量肯定不小,能否缩小查找范围,否则以遍历形式,效率肯定高不了。 Geohash算法就是将经纬度编码,将二维变一维,给地址位置分区的一种算法。 GeoHash是一种地址编

    2024年02月07日
    浏览(31)
  • GeoHash之存储篇

    在上一篇文章GeoHash——滴滴打车如何找出方圆一千米内的乘客主要介绍了GeoHash的应用是如何的,本篇文章我想要带大家探索一下使用什么样的数据结构去存储这些Base32编码的经纬度能够节省内存并且提高查询的效率。 针对于没有接触过前缀树或者不熟悉前缀树的同学,我先

    2024年02月10日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包