基于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%'），即可查询附近的所有地点。
下面以(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。
| 纬度范围 |
划分区间0 |
划分区间1 |
39.92324所属区间 |
| (-90, 90) |
(-90, 0.0) |
(0.0, 90) |
1 |
| (0.0, 90) |
(0.0, 45.0) |
(45.0, 90) |
0 |
| (0.0, 45.0) |
(0.0, 22.5) |
(22.5, 45.0) |
1 |
| (22.5, 45.0) |
(22.5, 33.75) |
(33.75, 45.0) |
1 |
| (33.75, 45.0) |
(33.75, 39.375) |
(39.375, 45.0) |
1 |
| (39.375, 45.0) |
(39.375, 42.1875) |
(42.1875, 45.0) |
0 |
| (39.375, 42.1875) |
(39.375, 40.7812) |
(40.7812, 42.1875) |
0 |
| (39.375, 40.7812) |
(39.375, 40.0781) |
(40.0781, 40.7812) |
0 |
| (39.375, 40.0781) |
(39.375, 39.7265) |
(39.7265, 40.0781) |
1 |
| (39.7265, 40.0781) |
(39.7265, 39.9023) |
(39.9023, 40.0781) |
1 |
| (39.9023, 40.0781) |
(39.9023, 39.9902) |
(39.9902, 40.0781) |
0 |
| (39.9023, 39.9902) |
(39.9023, 39.9462) |
(39.9462, 39.9902) |
0 |
| (39.9023, 39.9462) |
(39.9023, 39.9243) |
(39.9243, 39.9462) |
0 |
| (39.9023, 39.9243) |
(39.9023, 39.9133) |
(39.9133, 39.9243) |
1 |
| (39.9133, 39.9243) |
(39.9133, 39.9188) |
(39.9188, 39.9243) |
1 |
| (39.9188, 39.9243) |
(39.9188, 39.9215) |
(39.9215, 39.9243) |
1 |
经度也用同样的算法，对(-180, 180)依次细分，得到116.3906的编码为1101 0010 1100 0100 0100。
| 经度范围 |
划分区间0 |
划分区间1 |
116.3906所属区间 |
| (-180, 180) |
(-180, 0.0) |
(0.0, 180) |
1 |
| (0.0, 180) |
(0.0, 90.0) |
(90.0, 180) |
1 |
| (90.0, 180) |
(90.0, 135.0) |
(135.0, 180) |
0 |
| (90.0, 135.0) |
(90.0, 112.5) |
(112.5, 135.0) |
1 |
| (112.5, 135.0) |
(112.5, 123.75) |
(123.75, 135.0) |
0 |
| (112.5, 123.75) |
(112.5, 118.125) |
(118.125, 123.75) |
0 |
| (112.5, 118.125) |
(112.5, 115.312) |
(115.312, 118.125) |
1 |
| (115.312, 118.125) |
(115.312, 116.718) |
(116.718, 118.125) |
0 |
| (115.312, 116.718) |
(115.312, 116.015) |
(116.015, 116.718) |
1 |
| (116.015, 116.718) |
(116.015, 116.367) |
(116.367, 116.718) |
1 |
| (116.367, 116.718) |
(116.367, 116.542) |
(116.542, 116.718) |
0 |
| (116.367, 116.542) |
(116.367, 116.455) |
(116.455, 116.542) |
0 |
| (116.367, 116.455) |
(116.367, 116.411) |
(116.411, 116.455) |
0 |
| (116.367, 116.411) |
(116.367, 116.389) |
(116.389, 116.411) |
1 |
| (116.389, 116.411) |
(116.389, 116.400) |
(116.400, 116.411) |
0 |
| (116.389, 116.400) |
(116.389, 116.394) |
(116.394, 116.400) |
0 |
接下来将经度和纬度的编码合并，奇数位是纬度，偶数位是经度，得到编码 11100 11101 00100 01111 00000 01101 01011 00001。
最后，用0-9、b-z（去掉a, i, l, o）这32个字母进行base32编码，得到(39.92324, 116.3906)的编码为wx4g0ec1。
| 十进制 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
| base32 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
b |
c |
d |
e |
f |
g |
| 十进制 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
| base32 |
h |
j |
k |
m |
n |
p |
q |
r |
s |
t |
u |
v |
w |
x |
y |
z |
解码算法与编码算法相反，先进行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
先关参考：
从B树、B+树、B*谈到R树
http://blog.csdn.net/v_JULY_v/article/details/6530142
geohash：用字符串实现附近地点搜索
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
- 大小: 38.4 KB
分享到：
相关推荐
A*算法是一种广泛应用的启发式搜索算法，它结合了Dijkstra算法的全局最优性和 Greedy最佳优先搜索算法的效率。 A*算法的核心在于使用了启发式函数（h(n)），它估算从当前节点到目标节点的直线距离或曼哈顿距离，...
本文从长角甲虫的搜索行为中得到启发，提出了一种新的算法--甲虫触角搜索算法（BAS）。BAS算法模仿了自然界中甲虫的触角功能和随机行走机制，然后实现了检测和搜索的两个主要步骤。最后，该算法在2个众所周知的测试...
本篇文章将深入探讨在Java中实现的几种常见的搜索算法，包括二分搜索和线性搜索，这些都是数据结构和算法学习的重要部分。 首先，我们来理解这两种搜索算法的基本概念： 1. **线性搜索**（Linear Search）：这是最...
银行家算法安全序列全搜索算法实现代码的知识点总结 一、银行家算法简介 银行家算法（Banker's algorithm）是一种避免死锁的算法，它是由 E. Dijkstra 在 1965 年提出的。该算法用于避免在操作系统中存在的死锁...
折半查找是一种在有序数组中查找特定元素的搜索算法。利用了二分法，每次将搜索区间减半，从而快速定位目标元素。在C语言中，可以设定两个指针，分别指向数组的开始和结束，然后根据中间元素与目标值的比较结果，...
在编程领域，盲目式搜索算法是一种广泛应用于解决复杂问题的策略，主要分为广度优先搜索（Breadth-First Search, BFS）和深度优先搜索（Depth-First Search, DFS）。这两种算法都属于图论和树结构中的遍历方法，常...
A星（A*）算法是一种在图形搜索中广泛使用的路径规划算法，它的主要目标是找到从起点到终点的最短路径。A*算法结合了Dijkstra算法的全局最优性和最佳优先搜索的效率，通过引入启发式函数来指导搜索，使得算法能够更...
本文档实现了工程优化里面几种一维搜索算法的C语言程序实现，包括成功失败法、0.618法和平分法。这些算法都是为了找到函数的极小值或极大值。 一、成功失败法 成功失败法是一种简单的搜索算法，它通过不断地把搜索...
【三步快速搜索算法】是一种在数据检索和处理领域中常用的高效算法，尤其适用于大规模数据集。这个算法的核心思想是通过三次迭代逐步逼近目标值，从而实现快速定位。以下是关于三步快速搜索算法的详细解释及其相关...
迭代局部搜索（Iterated Local Search, ILS）是一种在优化领域广泛应用的启发式搜索算法，尤其在处理组合优化问题时效果显著。ILS算法的基本思想是结合局部搜索和扰动策略来跳出局部最优，寻找全局最优解。在这个...
下面我们将深入探讨和声搜索算法的基本原理、主要步骤以及其在Python中的实现方式。 ### 基本原理 和声搜索算法主要包括以下几个关键概念： 1. **初始和声**：代表一组随机生成的解，即待优化问题的初始解集。 2....
在标题中的"程序包_southil4_盲相位搜索_盲相位搜索算法_BPS算法_BPS"，"southil4"可能是指一个特定的实现或版本，而"BPS"是盲相位搜索（Blind Phase Search）的缩写，是这个程序包的核心算法。 在16QAM（16象限...
二分法是一种在有序数组中查找特定元素的搜索算法，同样可以应用于求平方根。初始区间为[0, num]，其中num是我们要开方的数。通过不断缩小区间范围，直到达到预设精度，就能得到平方根的近似值。二分法简单直观，但...
禁忌搜索算法是一种启发式搜索策略，主要用于解决全局优化问题。它的核心思想是避免在搜索过程中重复走过的路径，以防止陷入局部最优解。该算法包含几个关键步骤： 1. **初始化**：首先，随机生成一个初始解，即一...
《MATLAB算法实战应用案例精讲-爬行动物搜索算法-MATLAB实现源代码RSA》是一本专注于利用MATLAB进行算法实现与应用的教程，特别关注了爬行动物搜索算法和RSA加密算法。MATLAB是一种强大的数值计算和编程环境，广泛...
为了在FPGA上实现MUSIC算法，必须对算法进行选择与优化，主要包括以下几个方面： a. 实数化预处理问题：MUSIC算法中包含大量复数运算，而这些复数运算在硬件上实现较为复杂。为了简化硬件结构，需要将复数运算转化...
在MATLAB中实现麻雀搜索算法，主要涉及以下几个核心概念和步骤： 1. **初始化**：首先，我们需要随机生成一个初始的麻雀种群，每个麻雀代表一个可能的解决方案，即问题的解空间中的一个点。种群的大小、解的维度...