GeoHash算法

附近的职位(POI: 兴趣点)

最近有个需求，要求实现附近的职位的功能

那么首先我们需要定位当前的点，用经纬度表示，是一个二维的坐标。那么如果要筛选附近一公里以内的职位，我们不可能把数据库所有的职位坐标取出来计算，所以我们需要增加筛除条件减小结果集。

这个时候我想到的方法是，计算出以当前点为中心，取得相同纬度，距离1公里的左右经度临界线，再以相同经度取得上下维度临界线，这样就可以得到一个正方形范围的矩形和经纬度的最大最小临界值。

在数据库进行查询的时候就可以用临界值去排除(经纬度要用B+索引)。

对于查出来的数据再进行距离计算，筛除排序等。

但当请求量大的时候，肯定需要做缓存。但问题就来了，坐标点太精细了,如果要做缓存肯定得把同一区域内的点都做一致处理，那么就要对经纬度进行误差处理，但因为经纬度是两个系数，所以特别难做。

这个时候就需要用到Geohash了, Geohash最适合做热点缓存了。

什么是Geohash

维基百科定义: Geohash是Gustavo Niemeyer于2008年发明的公共领域地理编码系统，将地理位置编码为一小段字母和数字。 它是一种分层的空间数据结构，可将空间细分为网格状的桶。

其实，geohash就是通过base32编码将二维的坐标经纬度转化成一维的字符串表示，字符串的长度就代表了误差精准度。

• 精度表
  

可以看到，划分的区域更多了，也更精确了。geohash算法就是基于这种思想，划分的次数更多，区域更多，区域面积更小了。通过将经纬度编码，给地理位置分区

Geohash的原理

如图所示，我们将二进制编码的结果填写到空间中，当将空间划分为四块时候，编码的顺序分别是左下角00，左上角01，右下脚10，右上角11，也就是类似于Z的曲线，当我们递归的将各个块分解成更小的子块时，编码的顺序是自相似的（分形），每一个子快也形成Z曲线，这种类型的曲线被称为Peano空间填充曲线。

这种类型的空间填充曲线的优点是将二维空间转换成一维曲线（事实上是分形维），对大部分而言，编码相似的距离也相近，但Peano空间填充曲线最大的缺点就是突变性，有些编码相邻但距离却相差很远，比如0111与1000，编码是相邻的，但距离相差很大。

Geohash的实现

假设我们现在有一个点(116.389550, 39.928167), 我们需要三步完成geohash算法

1.将经纬度转化成二进制表示

以纬度39.928167举例

• 将区间[-90, 90]分为左右两个区间，维度在左区间则为0，在右区间则为1，这里在右区间取1
• 继续将纬度所在区间[0, 90]二分,发现在左区间取0
• 不断二分至15次(15次算出的geohash字符串长度为6，见上图精度表)
  
• 最后我们得出纬度的二进制数为

101110001100100

经度的二进制数为

110100101100010

2.将经纬度合并

经度占偶数位，纬度占奇数位。首位是从0开始的，0当偶数处理

111001110100100011110000011000

3.按照Base32进行编码

Base32编码表的其中一种如下，是用0-9、b-z（去掉a, i, l, o）这32个字母进行编码。具体操作是先将上一步得到的合并后二进制转换为10进制数据，然后对应生成Base32码。需要注意的是，将5个二进制位转换成一个base32码。
最终结果为

wx4g0s

算法缺陷

• 边缘问题
  
  如图，如果车在红点位置，区域内还有一个黄点。相邻区域内的绿点明显离红点更近。但因为黄点的编码和红点一样，最终找到的将是黄点。这就有问题了。

要解决这个问题，很简单，只要再查找周边8个区域内的点，看哪个离自己更近即可。

如何计算周边的8个区域key值呢

假设我们计算的key值是6位，那么二进制位数就是 6*5 = 30位，所以经纬度分别是15位。我们以纬度为例，纬度会均分15次。这样我们很容易能够算出15次后，划分的最小单位是多少

• 曲线突变问题
  有些编码相邻但距离却相差很远，比如0111与1000，编码是相邻的，但距离相差很大。所以需要实际计算两个点的距离才行。

代码实现

from typing import List

LOC_BITS = 25  # 经纬度二进制长度都为25时，geohash长度为10，误差范围在0.5m内

B32_DIGIT = "0123456789bcdefghjkmnpqrstuvwxyz"

# 精度表
PRECISION = {
    1: (3, 2),
    2: (5, 5),
    3: (8, 7),
    4: (10, 10),
    5: (13, 12),
    6: (15, 15),
    7: (18, 17),
    8: (20, 20),
    9: (22, 23),
    10: (25, 25),
    11: (28, 27),
    12: (30, 30)
}


def encode_location(lng: float, lat: float) -> str:
    """
    将经纬度转化为geohash表示，并按奇数位纬度，偶数位经度组合，从0开始0算偶数
    :param lng: 经度, 范围在-180~180
    :param lat: 纬度, 范围在-90～90
    :return:
    """
    if not isinstance(lat, (int, float)) or not isinstance(lng, (int, float)):
        raise TypeError("lat and lng must be int or float")

    if lng < -180 or lng > 180:
        raise ValueError("lng must be between -180 and 180")

    if lat < -90 or lat > 90:
        raise ValueError("lat must be between -90 and 90")

    lng_bits = get_binary(lng, -180, 180)
    lat_bits = get_binary(lat, -90, 90)

    # 合并两个二进制
    res_bits = [lat_bits[i // 2] if i % 2 else lng_bits[i // 2] for i in range(LOC_BITS * 2)]

    # 转十进制Base32编码
    res_int = [int(''.join(res_bits[i:i+5]), 2) for i in range(0, len(res_bits), 5)]
    geohash_str = "".join([B32_DIGIT[i] for i in res_int])

    return geohash_str


def decode_geohash(hash_str: str) -> (float, float):
    """
    将geohash字符串解码出具体经纬度坐标(范围中间点)
    :param hash_str: geohash字符串
    :return:
    """
    res_bits = []
    for s in hash_str:
        _binary = bin(B32_DIGIT.find(s))
        _binary = '%5s' % _binary[2:]  # 指定宽度5
        for i in _binary:
            res_bits.append('0' if i == ' ' else i)  # 组合出总二进制串

    lng_bits = [r for i, r in enumerate(res_bits) if not i % 2]  # 经度二进制
    lat_bits = [r for i, r in enumerate(res_bits) if i % 2]  # 纬度二进制

    lng = get_degree(lng_bits, -180, 180)
    lat = get_degree(lat_bits, -90, 90)

    return round(lng, 6), round(lat, 6)


def get_around_hash_list(hash_str: str) -> List[str]:
    """
    计算周围8区域的geohash值，返回顺序为从左往右从上到下
    :param hash_str: 所在区域geohash值
    :return:
    """
    hash_len = len(hash_str)
    if hash_len < 1 or hash_len > 12:
        raise ValueError('geohash length must be less than 13')

    lng, lat = decode_geohash(hash_str)  # 当前坐标点

    lng_length, lat_length = PRECISION[len(hash_str)]

    min_lng = get_min_degree(360, lng_length)
    min_lat = get_min_degree(180, lat_length)

    hash_list = list()
    # 左上
    hash_list.append(encode_location(lng - min_lng, lat + min_lat))
    # 上
    hash_list.append(encode_location(lng, lat + min_lat))
    # 右上
    hash_list.append(encode_location(lng + min_lng, lat + min_lat))
    # 左
    hash_list.append(encode_location(lng - min_lng, lat))
    # 右
    hash_list.append(encode_location(lng + min_lng, lat))
    # 左下
    hash_list.append(encode_location(lng - min_lng, lat - min_lat))
    # 下
    hash_list.append(encode_location(lng, lat - min_lat))
    # 右下
    hash_list.append(encode_location(lng + min_lng, lat - min_lat))

    return hash_list


def get_binary(degree: float, left: float, right: float) -> str:
    """
    将经度或纬度转化为二进制集合
    左右区间划分为左闭右开
    :param degree: 角度(经纬度)
    :param left: 区间左边界
    :param right: 区间右边界
    :return:
    """
    _bin = ""
    for i in range(LOC_BITS):
        mid = (right + left) / 2
        if degree >= mid:
            _bin += "1"
            left = mid
        else:
            _bin += "0"
            right = mid
    return _bin


def get_degree(binary: List[str], left: float, right: float) -> float:
    """
    根据二进制得到具体经纬度(取结果范围中间点)
    :param binary: 二进制数组
    :param left: 区间左边界
    :param right: 区间右边界
    :return:
    """
    for b in binary:
        mid = (right + left) / 2
        if b == '1':
            left = mid
        else:
            right = mid
    return (right + left) / 2


def get_min_degree(scope: float, times: int) -> float:
    """
    根据经纬度拆分次数获取最小单位角度
    :param scope: 拆分区间总大小
    :param times: 拆分次数
    :return:
    """
    while times:
        times -= 1
        scope /= 2

    return scope

Geohash的特点

• GeoHash用一个字符串表示经度和纬度两个坐标。在数据库中可以实现在一列上应用索引
• GeoHash表示的并不是一个点，而是一个矩形区域
• GeoHash编码的前缀可以表示更大的区域。例如wx4g0s，它的前缀wx4g0表示包含编码wx4g0s在内的更大范围。 这个特性可以用于附近地点搜索
• 编码越长，表示的范围越小，位置也越精确。因此我们就可以通过比较GeoHash匹配的位数来判断两个点之间的大概距离。

参考

Geohash精度和原理

聊聊GEOHASH

Geohash算法原理及实现

最后

以上就是顺利朋友为你收集整理的GeoHash算法的全部内容，希望文章能够帮你解决GeoHash算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。