最近会搬一些有关Geohash的文章来这里。嗯。


 

高能预警:此文属于纪录片记录了博主在知识的海洋里探索的艰辛历程,不是文档、且夹杂着大量的废话和人生感悟,如果时间紧建议您转看其他文章,比如文中的各种以这种颜色标明的原文。


 

背景:需要实现一个“由近到远列出当前位置周边的所有XX”的功能。

首先想到的是,以当前位置为圆心然后按不同的半径画出若干个同心圆然后再由近到远地列出来,不过马上就否定了这个幼稚的想法。首先以当前位置为圆心的原型不是固定其次…没有其次了这个首先就已经足够了。

然后就想到了按区域划分,也就是把整个区域用矩形划分然后找到当前所在位置的区域、以及该区域周围的8个区域,这些最近的排一次,如果用户还想看更远的,就再找到当前这9个区域外围的16个区域。而如何定位这些区域我想的是直接用区域的中心点坐标来计算。但是这个计算方式也不靠谱那么多区域呢怎么可能挨个算距离啊这不是跟挨个计算具体位置没什么区别了嘛。

之后朋友找到了一个叫做Geohash的方案,这样才算找到了一条正确的道路。

接下来就是初步的了解了下Geohash,但大多是类似的文章且描述的风格都很学术。所以在初步了解之后留下了这么几个问题:
1、Geohash的区域划分是有固定的库还是开发者自行划分?
2、由于用Geohash的字符串检索也会出现距离的问题(比如我在中间方框左上角的点、两个XX一个在中间方框右下角、另一个在左上方框的右下角,很明显我和左上方框的XX距离更近,但是Geohash的字符串相比我和中间方框右下角的XX更相似),于是各种文章里就说没有关系找到当前方框相邻的8个方框然后综合计算距离。那么问题就是:如何确定相邻的8个方框?
3、经纬度如何进行Geohash编码?这个问题其实看到了很多相关文章,除去了一些重复的、页面排版混乱的(比如在新浪博客里罗列整段代码简直让人对这篇文章都无法有任何好感)之后,挑着试了几个,但是总是有各种问题。
4、假如上面两个问题都解决了,我也从9个方框(当前所在方框、和相邻的8个方框)中找到了所有的XX,那么接下来应该是逐个计算XX和我当前位置的距离然后进行排序,那么这个距离如何计算?(这里我先不负责任的想直接计算两点之间距离不就行了么,虽然地球是圆的、有弧度,但是实际需求里相隔太远的XX的距离对于用户来讲其实意义并不大,而且误差我认为也可以接受)

那么接下来就围绕这几个问题进行一番研究。

随后发现了@一个开发者《开发LBS应用之 根据一点的经纬度实现附近点的查询 – geohash》,看过之后上面的问题至少解决了仨。

1、Geohash编码是根据经纬度获得的,那么这个编码肯定是固定的,按照既定的算法计算即可。
2、这个问题说解决了其实是无耻的偷了个懒,因为看到了@一个开发者提供了类库用来直接计算这个东西:string $hash = $geohash->encode(39.98123848, 116.30683690);。
3、同上一问题,同样提供了方法:array $neighbors = $geohash->neighbors(substr($hash, 0, 6));
4、而至于问题4,目前还没有找到可以解决问题的方法,后续再说。

既然有现成的了,那就顺着这个思路继续往下找,于是找到了这个《做了个经纬度与geohash相互转换的php扩展》,这位老兄提供了一个用C实现的方法,效率按他的说法是比PHP高若干倍,不过暂未测试。

找来找去也就@一个开发者的最靠谱,于是找来了他的栗子来测试一下,代码如下:

结果如下:

那么关于精度的问题,因为目前看到的各种讲解都是把Geohash字符串截取前六位,那么我做了如下测试,同时也是为了验证几个相邻位置的Geohash的字符串确实前几位是一致的。

如下图,取了「理想国际大厦」、「中国化工大厦」、「泰鹏大厦」、「中关村SOHO」四个建筑物的坐标:

四个点

然后代码如下:

结果如下:

由此可见,在这个0.04平方公里的范围里,计算出的Geohash的前6位是相同的,所以取前6位从精度和数量上都是很合适的。(补充:后来有个文章说,Geohash前六位的区域大概就是1平方公里…)


 

接下来,Geohash的问题基本解决,剩下的就是上面的“问题4”。

关于这个,继续搜索。那么检索到了如下几篇文章:《php计算两个经纬度地点之间距离的方法分享》《php 根据两点的经纬度计算距离》《根据两点经纬度计算距离 附C#和PHP代码》虽然名字很那个啥并且也不是出于高档社区….

大致扫了眼,这三个文章里提供了三种方法,虽然本质可能是一样的…那么,拿下来测试一下。

首先,在地图上选了两个点:理想国际大厦、首都国际机场T3航站楼,这两点的经纬度分别为:
理想国际大厦:N39.9905060000,E116.3165520000
首都国际机场T3航站楼:N40.0585830000,E116.6221280000
这里是用GPSSPG的地图里的百度地图的经纬度数据。截图如下:

理想国际大厦经纬度首都国际机场T3航站楼经纬度

接下来在百度地图里,用测距工具看一下百度地图里关于这两点的直线距离是27.1公里,如图:

理想国际大厦到首都国际机场T3航站楼直线距离

 

然后分别用这三个程序进行测试。

 

_(・ω・」 ∠)_…好吧,之前测试的时候搞错了经纬度,导致测试结果各不一样…实际上这三个算法的结果都是一样的,而且如果看得懂并究其本质的话应该也是一样的。

至此,上述的4个问题就算都解决掉了。那么接下来就需要根据上述的解决方案和实际需求来制定下数据的存储结构了。

这里主要参考《微信、陌陌 架构方案分析》这篇文章,这里面的场景是“列出用户周边的其他用户”,这个场景对于我的需求来说明显是要复杂的,毕竟“周边的其他用户”是会移动的,而我这里的需求“周边的XX”,这个XX是固定住的。

简单的流程如下图:

周边XX算法流程

也就是说:

  1. 得到当前位置的经纬度坐标:这个通过手机的定位以及某些地图的API获得(这里没详细琢磨过,也许不用这么麻烦)
  2. 由当前位置的经纬度计算得到当前位置的Geohash字符串。
  3. 用当前位置的Geohash的前六位(文章里说了,前六位大概就是一平方公里的范围,这个范围我认为是最合适的),找到当前区域周边8个相邻区域的Geohash。
  4. 找到这9个区域里所有XX(好吧说明白点,这个XX比如就是商户之类的固定的东西)的信息,信息包含ID、经纬度等。
  5. 计算这些XX到用户当前位置的距离。
  6. 按距离顺序排序。

这里面涉及的数据结构:

  1. XX的基本信息,如经度、纬度、Geohash值。
  2. 每个区域内XX的集合,即存储某个区域内(用Geohash前六位标识)所有的XX。

涉及的存储工具,这里(包括上面的数据结构)和《微信、陌陌 架构方案分析》里所提供的基本都一致:

  1. redis string (key->value) 结构,存储XX的基本信息,比如“XX的ID->XX的经纬度”。
  2. redis set (集合) 结构,以Geohash前六位作为key,存储该区域下的所有XX的ID。

这里说到了涉及到周边一共9个区域,那么如果用户还想继续往外看,那就要再往外找一圈、即找到当前9个区域外围的16个区域的XX。那么怎么确定这16个区域呢?目前看来倒是也好说。

1

比如这是当前的检索范围,用户在中间红色的区域内,给用户列出的是红色、和红色周边一共9个区域的XX。然后此时用户想要继续扩大范围,如下图:

2

也就是用户想要看最外围蓝色(也许你的屏幕看是黑色…)这一圈的XX。那么,至少我目前的想法——肯定还会有更方便的想法——是:

3

依次对绿色区域的8个区域,找各自的周边8区域,如上图,先找区域1的周边8区域,然后与现有区域的XX做去重过滤的操作:

4

这样剩下的就是再外围16个区域中5个区域的XX了。然后再依次2-8区域进行相同操作,最后得到完整的数据。


 

到这里,应该算的上一个完整的方案了。如有遗漏以后补充。

2BContinued.

记录一下:Mysql or Mongodb LBS快速实现方案

    分享到:

1 thought on “LBS – LBS方案的琢磨和制定”

发表评论

电子邮件地址不会被公开。 必填项已用*标注