乐趣区

关于geohash:GeoHash1理论篇

GeoHash(1)- 实践篇

兄弟篇:GeoHash(2)- 实现篇

一、前言

最近有个需要,要计算出客户坐标左近 5 公里的所有门店,并依照步行间隔排序。

最间接的办法就是遍历该城市下的所有门店,然而该办法显著不可取,因为在门店数量微小,且还须要计算步行间隔并排序的状况下,工夫简单度过高。

忽然想到当年做图像遇见一个问题:给定一个视频中间断的三千帧,然而曾经乱序,通知你第一帧,将这三千帧进行排序。遍历图像的所有像素点同样不可取,过后的解决方案是利用感知哈希计算出所有图像的指纹,接着利用明氏间隔计算间隔第一张最近的图像作为第二张,而后计算间隔第二张最近的作为第三张,以此类推。

同样,必定也有哈希办法可将地理位置转换成某种编码,并且编码可用于天文计算。它就是 GeoHash

二、相干常识

进入注释之前,先一起回顾一下初中天文:

本初子午线以西为西经,分十二区,每区 15 度共 180 度;以东为东经,同样分十二区,共 180 度。

赤道以北为北纬,共 90 度;以南为南纬,同样 90 度。

那么在计算机中,坐标示意为:

西经为正数,东经为负数,因而经度取值[-180, 180]

北纬为负数,南纬为正数,因而纬度取值[-90, 90]

咱们晓得赤道长约四万公里,因而经度上每度约等于 111 公里。地球实际上是个不规则球体,但为了简便计算,咱们假如把纬度上每度约等于 222 公里。

三、初识 GeoHash

1. 计算二进制编码

首先计算二进制编码,经度上以 [-180, 180] 开始,纬度以 [-90, 90] 开始,每次将区间进行二分,若输出坐标小于两头值则编码为0,下次区间取左半区间;若大于则编码为1,下次区间取右半区间。以此类推,编码越长,越靠近坐标值,进而越准确。

118°04′04, 24°26′46 为例,首先计算经度的编码:

编码长度 区间 两头值 编码 阐明 精度(千米)
1 [-180, 180] 0 1 118°04′04 大于 0°,因而编码 1,取右区间 19980
2 [0, 180] 90 1 118°04′04 大于 90° 9990
3 [90, 180] 135 0 118°04′04 小于 135°,因而编码 0,取左区间 4995
4 [90, 135] 112.5 1 2497.5
5 [112.5, 135] 123.75 0 1248.75
6 [112.5, 123.75] 118.125 0 624.375‬
7 [112.5, 118.125] 115.3125 1 312.188
8 [115.3125, 118.125] 116.71875‬ 1 156.094
9 [116.71875‬, 118.125] 117.421875 1 78.047‬
10 [117.421875, 118.125] 117.7734375‬ 1 39.024
N .

同样情理,计算纬度得编码:

编码长度 区间 两头值 编码 阐明 精度(千米)
1 [-90, 90] 0 1 24°26′46 大于 0°,因而编码 1,取右区间 19980
2 [0, 90] 45 0 24°26′46 小于 45°,因而编码 0,取左区间 9990
3 [0, 45] 22.5 1 4995
4 [22.5, 45] 33.75 0 2497.5
5 [22.5, 33.75] 28.125 0 1248.75
6 [22.5, 28.125] 25.3125 0 624.375‬
7 [22.5, 25.3125] 23.906 1 312.188
8 [23.906, 25.3125] 24.609 0 156.094
9 [23.906, 24.609] 24.2575‬ 1 78.047‬
10 [24.2575‬, 24.609] 24.433 0 39.024
N .

综上,假如咱们只取十位编码,经度上失去得编码为 1101001111,纬度上编码为 1010001010

将两个编码就像经纬交错网一样进行交错:

最初失去经纬二进制编码为11100110000011101110,联合以上两表的精度数据,咱们晓得该编码其实代表的是一块长宽为 39.024 千米的矩形块。

2. 转换 base32 编码

二进制编码其实就能够用来作为地理位置编码,然而:

  1. 不便于查找周边邻块。计算邻块,须要解析成经、纬两个编码再做计算。而采纳 base32 编码后,可用查表法,减速计算。
  2. 二进制编码长度过长,不利于检索。

因而,GeoHash 采纳了 base32 和 base36 编码,因为大多数采纳 base32 编码,因而本文仅介绍 base32 编码。

Decimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Base 32 0 1 2 3 4 5 6 7 8 9 B C D E F G
Decimal 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Base 32 H J K M N P Q R S T U V W X Y Z

base32 编码共 32 个编码,因而须要 5 个 bit,将 11100110000011101110 转换为 base32 编码:

最初失去编码为 WS7F

四、计算邻近块

1. 通用法

通用法的输出是二进制编码,因而不像查表法有位数限度,实用于所有状况,流程简略。

首先将经纬交错的二进制编码拆分为经度、纬度,若要求输出地位以北,则将纬度加一;以南,则将纬度减一;以西,则将经度减一;以东,则将经度加一。须要留神的是,加减后必须放弃原有的有效位数(比方,11 + 01 = 00,放弃两位无效位)。最初将计算结果重新组合,失去要求地位的二进制编码。

过程如下图为例,不再赘述:

2. 查表法

查表法的计算比通用法快很多,不必将输出编码拆分成经纬度进行加减,但须要留神的是:输出的是 base32 编码,因而仅实用于二进制编码位数为 5 的倍数的GeoHash

网上大部分文章仅讲诉如何利用查表法计算邻块,那么这个查表如何失去呢?失去了编码后,如何计算邻块?网上大部分文章仅讲诉如何利用查表法计算邻块,然而这个查表如何失去呢?

依据后面,咱们晓得编码由 5 个 bit 二进制,并经纬交错组成。因而,若该编码处于奇数位上,即 经 纬 经 纬 经 交错形式;若处于偶数位上,则 纬 经 纬 经 纬 交错形式。

那么,以 W 为例,二进制为 11100,若处于奇数位则在表中为 右 上 右 下 左 ,若处于偶数位则在表中为 上 右 下 左 下,因而 W 在查表中的地位如下图:

同样,求出其余编码的地位,后果为:

WS7F 为例,当初要求该地位的邻近块,取末位F,从偶数位表中能够看到,F 的邻近为E, G, D, 9, C,以及往右出了界的 5, 4, 1。因而5, 4, 1 三个邻块还须要看倒数第二位 7。从奇数表中能够看到,7 的左边没有超界(若超界了,看倒数第三位,以此类推),为K

因而,失去四周邻块别离位 WS7E, WS7G, WS7D, WS79, WS7C, WSK5, WSK4, WSK1,地位关系如下:

五、总结

次要从实践上介绍:

  1. GeoHash 对地理位置点进行编码的办法:依据“递归二分”获取二进制,将二进制转换为 Base32 编码。
  2. GeoHash 邻块的疾速计算方法:取末位编码,依据偶数位表查找对应邻块编码,若某方向出界,则查找前一位编码,并依据奇 / 偶表查找相应方向的编码。

算法实现:【搬砖笔记】利用 GeoHash 为地理位置编码——实现篇

六、延申

  1. GeoHash 不仅能够用来对地位点进行编码,也能够用来对面进行编码,有助于解决点、面的多种组合关系计算。比方,判断点地位是否在门店的配送围栏之内。
  2. GeoHash 其实就是 Peano 曲线 的一种利用,如下:

还有许多空间填充曲线,比方公认比拟好的,没有较大渐变的 Hilbert 曲线。

参考

  1. GeoHash 外围原理解析
  2. 基于疾速 GeoHash,如何实现海量商品与商圈的高效匹配?
退出移动版