Geohash

举个例子来说明下Geohash的作用。

我们需要搜索当前200米范围内的所有餐馆啊什么的。那么我们怎么去定位所有餐馆的位置呢？

最普通的方法就是，算出当前位置能找到的餐馆的距离，然后在筛选出 ≤ 200 的餐馆。这样也是可以的，但是问题在于

一个城市有茫茫多的餐馆，每次定位都需要计算一次然后筛选。这个开销太大了。简直可以说是爆炸。然后就可以想想别的

方法了。按照正常的想法，我站在某个位置，那么最好的定位方法当然是以我为中心向外辐射200米。然后在这个区域内的

所有餐馆都是我想要的。这样的话，计算量就会小很多了。

于是呢，出现了Geohash这个东东。下面是Geohash的原理。

Geohash 原理：

Geohash主要是把二维的地址坐标（经纬度）转换成一个一维的字符串标识。然后用这个标识来标注这个区域。具体的

编解码方法如下：

经度的范围是 [-90, 90]，那么先划分成 [-90, 0), [0, 90]。我们将这个划分为左右区域。当得到的经度在左区域的

时侯标注0，在右区域的时候标注为1. 假定我们现在的坐标为 39.928167，那么得到第一个标志位是1.

然后在从[0, 90]进行二次划分，[0, 45), [45, 90]. 这时候 39.928167在左区域，得到标志位是0，一次类推，我们

可以得到一窜1011100011（具体精确到多少个01 需要根据客户需求来定。）

纬度的编码方式和经度的编码方式是一样的，只是范围是[-180， 180]。然后对116.389550进行编码，就会得到10

111 00011。

然后根据偶数位放经度，奇数位放纬度进行交替编码。

我们得到的经度编码是： 11010 01011

我们得到的纬度编码是： 10111 00011

所以Geohash编码是： 11100 11101 00100 01111

注： Geohash 编码的字符串是从0开始算起的，所以第一位是经度，然后纬度，然后经度。。。

得到Geohash编码之后，五位五位的开始编码，所以是 28、29、4、15

所以得到是Geohash 是 wx4g.

下面是一些参考网站：

https://en.wikipedia.org/wiki/Geohash

http://www.cnblogs.com/LBSer/p/3310455.html

http://www.cnblogs.com/dengxinglin/archive/2012/12/14/2817761.html

下面是C++ 代码实现：

 1 string encodeGeohash(const double & theLat, const double & theLong, int thePrecision)
 2 {
 3     string aStrGeohash = "";
 4     double aLatStart = -90.000000;
 5     double aLatEnd = 90.000000;
 6     double aLongStart = -180.000000;
 7     double aLongEnd = 180.000000;
 8     double aLatMidPoint = (aLatStart + aLatEnd) / 2;
 9     double aLongMidPoint = (aLongStart + aLongEnd) / 2;
10     int aBit = 0;
11     int aCh = 0;
12     char aBits[] = {16, 8, 4, 2, 1};
13     const string BASEENCODE = "0123456789bcdefghjkmnpqrstuvwxyz";
14 
15     if(theLat < aLatStart || theLat > aLatEnd || theLong < aLongStart || theLong > aLongEnd)
16     {
17         return aStrGeohash;
18     }
19     //The Geohash first bit is longtitude
20     for(int i = 0; i < thePrecision; i++)
21     {
22         if(0 == i % 2)
23         {
24             if(theLong >= aLongMidPoint)
25             {
26                 aCh |= aBits[aBit];
27                 aLongStart = aLongMidPoint;
28             }
29             else
30             {
31                 aLongEnd = aLongMidPoint;
32             }
33             aLongMidPoint = (aLongStart + aLongEnd) / 2;
34         }
35         else
36         {
37             if(theLat >= aLatMidPoint)
38             {
39                 aCh |= aBits[aBit];
40                 aLatStart = aLatMidPoint;
41             }
42             else
43             {
44                 aLatEnd = aLatMidPoint;
45             }
46             aLatMidPoint = (aLatStart + aLatEnd) / 2;
47         }
48 
49         if(aBit < 4)
50         {
51             aBit++;
52         }
53         else
54         {
55             aStrGeohash += BASEENCODE[aCh];
56             aCh = 0;
57             aBit = 0;
58         }
59     }
60 
61     return aStrGeohash;
62 }