GeoHash algorithm

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

方法一
方法二
在 8 个方向移动
参考

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

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

class Pos {
    float x;
    float y;
};

vector<Shop> top_k(Pos& user);

方法一

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

如果返回集合仍然很大，怎么处理？

方法二

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 时，需要做一些操作。因为进位和补位都不能发生交错。

方法一

方法二

在 8 个方向移动

参考