附近地点搜索算法的几种实现方式

电玩女神 2022-08-26 14:28 190阅读 0赞

基于LBS的应用在眼下已是如火如荼，地理位置功能都相应的被添加在各大应用中，基本上算是作为了行业的标杆。最近开发的一个应用也是涉及到对用户发表帖子的当前位置下的附近帖子的搜索，类似的搜索功能其实也不是什么新鲜事，但是貌似都没有公布其实现，所以当时也是非常的茫然。

**想法一：**

最容易想到的肯定就是给定范围然后直接全库搜索，但是一旦数据量过大，性能肯定下降得非常快，所以行不通否定了。

** 想法二：**

幸好之前有看到过一些介绍R树的文章，就是基于空间搜索，将常用的数据库的一维搜索扩展到了二维甚至是多维。虽然有了点思路，但是有看过R树的就应该知道，R树的分裂与合并是比较麻烦的，如果自己写，肯定是没有戏的。所以很快就否定了，真是有理论没得实践。

**想法三：**

后来在网上搜到还有一种常用的算法是geohash算法，它是一种地址编码，它能把二维的经纬度编码成一维的字符串，但是其算法自身也是有缺陷的，位于格子边界两侧的两点，虽然十分接近，但编码会完全不同。实际应用中，可以同时搜索当前格子周围的8个格子，即可解决这个问题，虽然不是十全十美，但是还是能解决问题。。

**想法四：**

**     **因为想法三的局限性，所以就进一步查了下，突然发现一个好东西，那就是**空间数据库**，而其底层的实现方式果然就是用到了想法二中的R树算法，所以虽然想法二自己不能实现，但是还是证明了其强大性，O(∩\_∩)O哈哈~。。

那下面就具体的介绍一下想法三和想法四的具体实现：

**    一、geohash算法**

***geohash算法有以下几个特点：***

首先，geohash用一个字符串表示经度和纬度两个坐标。某些情况下无法在两列上同时应用索引（例如MySQL 4之前的版本，Google App Engine的数据层等），利用geohash，只需在一列上应用索引即可。

其次，geohash表示的并不是一个点，而是一个矩形区域。比如编码wx4g0ec19，它表示的是一个矩形区域。使用者可以发布地址编码，既能表明自己位于北海公园附近，又不至于暴露自己的精确坐标，有助于隐私保护。

第三，编码的前缀可以表示更大的区域。例如wx4g0ec1，它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。这个特性可以用于附近地点搜索。首先根据用户当前坐标计算geohash（例如wx4g0ec1）然后取其前缀进行查询（`SELECT * FROM place WHERE geohash LIKE 'wx4g0e%'`），即可查询附近的所有地点。

![20c4adf7-3a98-3e88-aabf-c2e6b475539f.jpg][]

下面以(39.92324, 116.3906)为例，介绍一下geohash的编码算法。首先将纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90)，如果目标纬度位于前一个区间，则编码为0，否则编码为1。由于39.92324属于(0, 90)，所以取编码为1。然后再将(0, 90)分成 (0, 45), (45, 90)两个区间，而39.92324位于(0, 45)，所以编码为0。以此类推，直到精度符合要求为止，得到纬度编码为1011 1000 1100 0111 1001。

经度也用同样的算法，对(-180, 180)依次细分，得到116.3906的编码为1101 0010 1100 0100 0100。

接下来将经度和纬度的编码合并，奇数位是纬度，偶数位是经度，得到编码 11100 11101 00100 01111 00000 01101 01011 00001。

最后，用0-9、b-z（去掉a, i, l, o）这32个字母进行base32编码，得到(39.92324, 116.3906)的编码为wx4g0ec1。

解码算法与编码算法相反，先进行base32解码，然后分离出经纬度，最后根据二进制编码对经纬度范围进行细分即可，这里不再赘述。不过由于geohash表示的是区间，编码越长越精确，但不可能解码出完全一致的地址。

**geohash的应用：附近地址搜索**

geohash的最大用途就是附近地址搜索了。不过，从geohash的编码算法中可以看出它的一个缺点：位于格子边界两侧的两点，虽然十分接近，但编码会完全不同。实际应用中，可以同时搜索当前格子周围的8个格子，即可解决这个问题。

**二、空间数据库**

** **   根据OpenGIS规范的的空间数据库实现有几种方式，自己采用的是Mysql的实现，比较简单，但是Mysql存在一些尚未实现的GIS特性，所以如果你的应用相对复杂的话，可以采用其它实现方式。

对于Mysql的具体实现请参考Mysql中的空间扩展文档

[http://dev.mysql.com/doc/refman/5.1/zh/spatial-extensions-in-mysql.html\#gis-class-polygon][http_dev.mysql.com_doc_refman_5.1_zh_spatial-extensions-in-mysql.html_gis-class-polygon]

先关参考：

从B树、B+树、B\*谈到R树

[http://blog.csdn.net/v\_JULY\_v/article/details/6530142][http_blog.csdn.net_v_JULY_v_article_details_6530142]

geohash：用字符串实现附近地点搜索

[http://tech.idv2.com/2011/07/05/geohash-intro/][http_tech.idv2.com_2011_07_05_geohash-intro]

MySQL中的空间扩展

[http://dev.mysql.com/doc/refman/5.1/zh/spatial-extensions-in-mysql.html\#gis-class-polygon][http_dev.mysql.com_doc_refman_5.1_zh_spatial-extensions-in-mysql.html_gis-class-polygon]

[20c4adf7-3a98-3e88-aabf-c2e6b475539f.jpg]: /images/20220824/264704ded94d4a3989f51a1ecaf7ba23.png
[http_dev.mysql.com_doc_refman_5.1_zh_spatial-extensions-in-mysql.html_gis-class-polygon]: http://dev.mysql.com/doc/refman/5.1/zh/spatial-extensions-in-mysql.html#gis-class-polygon
[http_blog.csdn.net_v_JULY_v_article_details_6530142]: http://blog.csdn.net/v_JULY_v/article/details/6530142
[http_tech.idv2.com_2011_07_05_geohash-intro]: http://tech.idv2.com/2011/07/05/geohash-intro/