GeoHash

2019/04/29 11:37
阅读数 241

1. 简介

Geohash是一种地理编码,用于将二维经纬度映射成一维编码,方便计算机存储与索引。

2. 基本原理

分别将经纬度进行二等分逼近编码,按照所属区域进行连续编码,最后将两组编码混合进行Base32编码,便生成Geohash编码。

如下所是对经纬度(110.53785, 39.92324)进行Geohash编码:

经度范围    区间编码:0    区间编码:1    110.53785
1    (-180.000000 180.000000)    (-180.000000, 0.000000)    (0.000000 180.000000)    1
2    (0.000000 180.000000)    (0.000000, 90.000000)    (90.000000 180.000000)    0
3    (90.000000 180.000000)    (90.000000, 135.000000)    (135.000000 180.000000)    1
4    (90.000000 135.000000)    (90.000000, 112.500000)    (112.500000 135.000000)    1
5    (90.000000 112.500000)    (90.000000, 101.250000)    (101.250000 112.500000)    1
6    (101.250000 112.500000)    (101.250000, 106.875000)    (106.875000 112.500000)    0
7    (106.875000 112.500000)    (106.875000, 109.687500)    (109.687500 112.500000)    0
8    (109.687500 112.500000)    (109.687500, 111.093750)    (111.093750 112.500000)    0
9    (109.687500 111.093750)    (109.687500, 110.390625)    (110.390625 111.093750)    1
10    (110.390625 111.093750)    (110.390625, 110.742188)    (110.742188 111.093750)    1
11    (110.390625 110.742188)    (110.390625, 110.566406)    (110.566406 110.742188)    0
12    (110.390625 110.566406)    (110.390625, 110.478516)    (110.478516 110.566406)    0
13    (110.478516 110.566406)    (110.478516, 110.522461)    (110.522461 110.566406)    0
14    (110.522461 110.566406)    (110.522461, 110.544434)    (110.544434 110.566406)    1
15    (110.522461 110.544434)    (110.522461, 110.533447)    (110.533447 110.544434)    1
纬度范围                   区间编码:0                 区间编码:1              39.92324
1     (-90.000000 90.000000)   (-90.000000, 0.000000)    (0.000000 90.000000)     1
2     (0.000000 90.000000)     (0.000000, 45.000000)     (45.000000 90.000000)    0
3     (0.000000 45.000000)     (0.000000, 22.500000)     (22.500000 45.000000)    1
4     (22.500000 45.000000)    (22.500000, 33.750000)    (33.750000 45.000000)    1
5     (33.750000 45.000000)    (33.750000, 39.375000)    (39.375000 45.000000)    1
6     (39.375000 45.000000)    (39.375000, 42.187500)    (42.187500 45.000000)    0
7     (39.375000 42.187500)    (39.375000, 40.781250)    (40.781250 42.187500)    0
8     (39.375000 40.781250)    (39.375000, 40.078125)    (40.078125 40.781250)    0
9     (39.375000 40.078125)    (39.375000, 39.726562)    (39.726562 40.078125)    1
10    (39.726562 40.078125)    (39.726562, 39.902344)    (39.902344 40.078125)    1
11    (39.902344 40.078125)    (39.902344, 39.990234)    (39.990234 40.078125)    0
12    (39.902344 39.990234)    (39.902344, 39.946289)    (39.946289 39.990234)    0
13    (39.902344 39.946289)    (39.902344, 39.924316)    (39.924316 39.946289)    0
14    (39.902344 39.924316)    (39.902344, 39.913330)    (39.913330 39.924316)    1
15    (39.913330 39.924316)    (39.913330, 39.918823)    (39.918823 39.924316)    1

  经纬度交叉编码(偶数位:经度,奇数位:纬度):

编码    1 1 0 0 1 1 1 1 1 1 0  0  0  0  0  0  1  1  1  1  0  0  0  0  0  0  1  1  1   1
序号    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

 

 Base32 编码:

 

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

交叉编码进行Base32化(5位二进制对应一个Base32码)

编码    1    1    0    0    1    1    1    1    1    1    0    0    0    0    0    0    1    1    1    1    0    0    0    0    0    0    1    1    1    1
序号    0    1    2    3    4    5    6    7    8    9    10    11    12    13    14    15    16    17    18    19    20    21    22    23    24    25    26    27    28    29
    25/T                    31/Z                    0/0                    15/G                    0/0                    15/G

编码结果:TZ0G0G

3. 精度

(geohash length * 5 == lat bits + lng bits)

4. 查询

1)静态邻域查询

将坐标点编码成Geohash存储在Redis或MySQL(排序进行索引)中,前缀匹配进行邻域查询。 

2)动态邻域查询(动态点、线段、多边形)

对于动态邻域查询需要转换思路,需要将地图进行Geohash切分与编码,具体的实体该在与之相交的格子中。

5. 线与多边形编码

上述主要进行了点的Geohash编码,对于线与多边形就需要转换一下思路,不再对线与多边形进行编码,而对平面空间区域进行Geohash划分。确定精度后,我们可以把地球表面划分成大小相近的四边形格子,每个格子都拥有一个Geohash编码。此时计算与线段或多边形相交的格子,从而得到一组Geohash编码,这组Geohash编码便是该线段或多边形的Geohash编码。

在存储上,这组Geohash节点下都将挂在该线段或多边形,在查询时,其中任何一个Geohash被命中,都将命中该线段或多边形。

7. 问题

1)交叉编码为何精度在前?

精度范围比纬度范围广,同时当Base32的编码位长度为奇数时,精度可以多进行一位编码。

2)Geohash编码为何是Z编码?

坐标Geohash编码后排序,便成为了Z编码,如图。

3)邻域查询

  查询范围内的命中目标?

  方案1:

    1)将查询范围进行Geohash编码,得到一组Geohash编码;

    2)判度每个Geohash的空间范围是否完全在查询范围内:

      YES:该Geohash下的目标都被命中

      NO:该Geohash下的目标与查询范围进行过滤

4)周边格子搜索

  搜索指定个周围8个方向的格子:

  

  如上图所示,经度在划分的时候,从左到右具有递增规律,在同一层级寻找左右方向格子只需要对当前格子进行+-1即可(纬度同理)。

8. 扩展

Geohash作为一种地理编码,不仅可以用于二维数据一维化,还可以用于地理数据索引,在Redis中作为Hash Key进行索引存储。作为地理索引,还可以参考RTree和Google s2。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部