周围的餐馆有哪些?GeoHash算法

geohash-feature

当今年代,每个人都有智能手机,出门在外,自然离不开使用手机地图了,查找附近的餐馆,附近的地铁站,非常方便,可是在这项技术背后又隐藏着什么算法呢?这篇博客将会讲述这个技术背后的GeoHash算法以及基本的实现。

首先既然算法名字叫做GeoHash了那么对单词比较敏感的人可能已经猜出来了,差不多就是对当前的位置生成一个Hash值,然后再比较相似吧,是的,大概就是这个样子。

GeoHash的原理就是讲一个地理位置的经纬度,转换成一个可以排序,可以比较的的Hash字符串。这个字符串。

GeoHash代表的不是一个精确地的标,而是一个区域,当Hash值越长的时候,这个hash代表的区域越小,就越精确,比如 wtw3eegq 这个Hash就是上海南京西路周围的的一块,但是 只有前6位 wtw3ee 的话这个Hash代表的区域面积就比 wtw3eegq要大,但是 wtw3eegq 是包扩在 wtw3ee 这个区域里面的,所以可以用这个特性来查找一个坐标周围的餐馆之类的地方。

GeoHash就是这样,他将地球首先分为四个象限,之后每一象限再平分为四个象限,就是这样无限细分下去,这样,地球就根据坐标分为了若干区域,每个区域都会根据算法来生成一个Hash值,Hash值越相似就代表两个区域的位置越近

Screen Shot 2016-05-06 at 10.47.20 PM

ProximityChat

接下来将会讨论这个算法的具体细节:

  • 计算纬度

比如我们需要计算 坐标 121.443469, 31.22246 的GeoHash值

首先将纬度范围(-90, 90)平分成两个区间(-90,0)、(0, 90),如果目标纬度位于前一个区间,则编码为0,否则编码为1。

由于31.22246属于(0, 90),所以取编码为1。

然后再将(0, 90)分成 (0, 45), (45, 90)两个区间,而31.22246位于(0, 45),所以编码为0。

就和中学时代学过的二分法解方程一样简单,对吧~

以此类推,直到精度符合要求为止,得到编码为1010 1100 0110 0111 1100 ,下面的表只是计算了前8位,可以看出,二分次数越多,取得的值就越精确。

left mid right bit
-90 0 90 1
0 22.5 45 0
22.5 33.75 45 1
22.5 30 37.5 0
30 33.75 37.5 1
30 31.875 33.75 1
30 30.9375 31.875 0
30.9375 31.40625 31.875 0

 

接下来看经度

  • 计算经度

首先将经度范围(-180, 180)平分成两个区间(-180,0)、(0, 180),如果目标经度位于前一个区间,则编码为0,否则编码为1。

由于121.443469属于(0, 180),所以取编码为1。

然后再将(0, 180)分成 (0, 90), (90, 180)两个区间,而121.443469位于(90, 180),所以编码为1。

以此类推,直到精度符合要求为止,得到经度编码为1101 0110 0101 1100 0001 ,下面的表只是计算了前8位。

left mid right bit
-180 0 180 1
0 90 180 1
90 135 180 0
90 112.5 135 1
112.5 123.75 135 0
112.5 118.125 123.75 1
118.125 120.9375 123.75 1
120.9575 122.35375 123.75 0
  • 经度纬度合并

接下来将经度和纬度的编码合并,奇数位是纬度,偶数位是经度

10101100011001111100 和 11010110010111000001 合并为:
1110011001111000001101101011010101010010

  • Base32编码转换

得到合并后的编码之后,每5位一看,转换为十进制,之后按照Base32的编码表来转换为Base32编码

Decimal 0 1 2 3 4 5 6 7
Base32 0 1 2 3 4 5 6 7
Decimal 8 9 10 11 12 13 14 15
Base32 8 9 b c d e f g
Decimal 16 17 18 19 20 21 22 23
Base32 h j k m n p q r
Decimal 24 25 26 27 28 29 30 31
Base32 s t u v w x y z

 

刚才合并的编码为:1110011001111000001101101011010101010010

将他分为11100、11001、11100、00011、01101、01101、01010、10010

十进制为:28, 25, 28, 3, 13, 13, 10, 18

根据编码表转换后的Base32编码值为 wtw3eebk

这个值:wtw3eebk 就是坐标121.443469, 31.22246 的GeoHash值

这样的话只要在坐标入库的时候程序顺便算出坐标的GeoHash值一并入库,就可以实现快速进行周边餐馆查找之类的功能了。

  • 测试

为了看一下这个算法的可行性,我写了一个爬虫来访问高德地图来不断检索地址并且算出Geohash(文章最后会给出整个爬虫和算法的代码)

posi

我生成的GeoHash是8位的,通过匹配前6位:wtw3ef,来进行查找,匹配出了下面的餐馆

热辣壹号(淮海中路百盛店)
淮海中路918号百盛商场8层
121.459133,31.217455
wtw3efgy

伊秀寿司(淮海店)
淮海中路918号淮海百盛8层(久事复兴大厦)
121.459291,31.217210
wtw3efgv

丸龟制面(淮海百盛店)
淮海中路918号百盛购物中心B1楼13铺(近陕西南路)
121.459274,31.217533
wtw3efgz

查厘士港式餐厅(淮海中路黄金店)
淮海中路988黄金世界3层
121.458316,31.216696
wtw3efg4

九久日本料理(淮海店)
淮海中路939号巴黎春天百货5楼(地铁1号线陕西南路站)
121.459520,31.216730
wtw3efu4

通过地址可以看出来这几个餐馆都是位于淮海中路上的。

和高德地图检索周边出来的餐馆差不多:

Screen Shot 2016-05-06 at 11.42.00 PM

 

下面是GeoHash的精度表:

GeoHash长度 Lat位数 Lng位数 Lat误差 Lng误差 km误差
1 2 3 ±23 ±23 ±2500
2 5 5 ± 2.8 ±5.6 ±630
3 7 8 ± 0.70 ± 0.7 ±78
4 10 10 ± 0.087 ± 0.18 ±20
5 12 13 ± 0.022 ± 0.022 ±2.4
6 15 15 ± 0.0027 ± 0.0055 ±0.61
7 17 18 ±0.00068 ±0.00068 ±0.076
8 20 20 ±0.000086 ±0.000172 ±0.01911
9 22 23 ±0.000021 ±0.000021 ±0.00478
10 25 25 ±0.00000268 ±0.00000536 ±0.0005971
11 27 28 ±0.00000067 ±0.00000067 ±0.0001492
12 30 30 ±0.00000008 ±0.00000017 ±0.0000186

 

Github链接

这个项目中有我写的爬虫,查询类和Geohash,Base32相关类

爬虫读取后存为txt,之后查询的时候读取txt作为临时数据库

nearbyfinder

 

我的博客MikeTech app现已登陆iPhone和Android

iPhone版下载
Android版下载

打赏

Leave a Reply

Your email address will not be published. Required fields are marked *