GeoHash algorithm

Posted by chunyang on March 1, 2021

最近遇到一个问题:K 个距离最近商铺问题。用户实时汇报其坐标,需要返回距离其最近的 K 个商铺 问题。

商铺的量很大,如果每次都遍历计算一遍计算复杂度很高。


class Shop {
    Pos pos;
    // other fields
};

class Pos {
    float x;
    float y;
};

vector<Shop> top_k(Pos& user);

方法一

将地图根据 X 和 Y 坐标分别划分区间,根据输入的用户的 posxy。然后根据横纵坐标分别召回, 将召回的两个结果进行取交集,最后遍历结果进行返回。交集的计算复杂度也会比较高,可以直接取二者较小 集合,直接计算。

如果返回集合仍然很大,怎么处理?

方法二

GeoHash 算法。

Geohash

它可以将提供的经纬度转换成字符串,字符串前缀匹配越多,则二者距离越近。该算法

  • 先将经度和维度进行切分,得到一个编码的串
  • 经度维度二进制串互相交差
  • 4 个二进制位一组,转换成 base32 编码
typedef struct {
        uint64_t bits;
        uint8_t step;
} GeoHashBits;

typedef struct {
        double max;
        double min;
} GeoHashRange;

typedef struct {
        GeoHashBits hash;
        GeoHashRange latitude;
        GeoHashRange longitude;
} GeoHashArea;

int geohash_encode(
        GeoHashRange lat_range, GeoHashRange lon_range,
        double latitude, double longitude, uint8_t step, GeoHashBits* hash)
{
    if (NULL == hash || step > 32 || step == 0)
    {
        return -1;
    }
    hash->bits = 0;
    hash->step = step;
    uint8_t i = 0;
    if (latitude < lat_range.min || latitude > lat_range.max
     || longitude < lon_range.min || longitude > lon_range.max)
    {
        return -1;
    }

    for (; i < step; i++)
    {
        uint8_t lat_bit, lon_bit;
        if (lat_range.max - latitude >= latitude - lat_range.min)
        {
            lat_bit = 0;
            lat_range.max = (lat_range.max + lat_range.min) / 2;
        }
        else
        {
            lat_bit = 1;
            lat_range.min = (lat_range.max + lat_range.min) / 2;
        }
        if (lon_range.max - longitude >= longitude - lon_range.min)
        {
            lon_bit = 0;
            lon_range.max = (lon_range.max + lon_range.min) / 2;
        }
        else
        {
            lon_bit = 1;
            lon_range.min = (lon_range.max + lon_range.min) / 2;
        }
        hash->bits <<= 1;
        hash->bits += lon_bit;
        hash->bits <<= 1;
        hash->bits += lat_bit;
    }
    return 0;
}
int geohash_decode(
        GeoHashRange lat_range, GeoHashRange lon_range, GeoHashBits hash, GeoHashArea* area)
{
    if (NULL == area)
    {
        return -1;
    }
    area->hash = hash;
    uint8_t i = 0;
    area->latitude.min = lat_range.min;
    area->latitude.max = lat_range.max;
    area->longitude.min = lon_range.min;
    area->longitude.max = lon_range.max;
    for (; i < hash.step; i++)
    {
        uint8_t lat_bit, lon_bit;
        lon_bit = get_bit(hash.bits, (hash.step - i) * 2 - 1);
        lat_bit = get_bit(hash.bits, (hash.step - i) * 2 - 2);
        if (lat_bit == 0)
        {
            area->latitude.max = (area->latitude.max + area->latitude.min) / 2;
        }
        else
        {
            area->latitude.min = (area->latitude.max + area->latitude.min) / 2;
        }
        if (lon_bit == 0)
        {
            area->longitude.max = (area->longitude.max + area->longitude.min) / 2;
        }
        else
        {
            area->longitude.min = (area->longitude.max + area->longitude.min) / 2;
        }
    }
    return 0;
}

我们可以使用前缀树的数据结构来存储店铺的信息。这样就可以根据 base32 后的编码来返回对应的商铺。

在 8 个方向移动

static int geohash_move_x(GeoHashBits* hash, int8_t d)
{
    if (d == 0)
        return 0;
    uint64_t x = hash->bits & 0xaaaaaaaaaaaaaaaaLL;
    uint64_t y = hash->bits & 0x5555555555555555LL;

    uint64_t zz = 0x5555555555555555LL >> (64 - hash->step * 2);
    if (d > 0)
    {
        x = x + (zz + 1);
    }
    else
    {
        x = x | zz;
        x = x - (zz + 1);
    }
    x &= (0xaaaaaaaaaaaaaaaaLL >> (64 - hash->step * 2));
    hash->bits = (x | y);
    return 0;
}

static int geohash_move_y(GeoHashBits* hash, int8_t d)
{
    if (d == 0)
        return 0;
    uint64_t x = hash->bits & 0xaaaaaaaaaaaaaaaaLL;
    uint64_t y = hash->bits & 0x5555555555555555LL;

    uint64_t zz = 0xaaaaaaaaaaaaaaaaLL >> (64 - hash->step * 2);
    if (d > 0)
    {
        y = y + (zz + 1);
    }
    else
    {
        y = y | zz;
        y = y - (zz + 1);
    }
    y &= (0x5555555555555555LL >> (64 - hash->step * 2));
    hash->bits = (x | y);
    return 0;
}

由于经度和维度的额二进制是交差的,所以我们要注意的是在移动 X 或者 Y 时需要注意二进制位的计算。 例如: 10010101,其中 x 为:1000,y 为 0111。我们在移动 x 或者 y 的 bit 时,需要做一些操作。因为 进位和补位都不能发生交错。

参考