geo hash原理

GEO Hash椒地理坐标(经度,纬度)
实现步骤
墨卡托投影把纬度为Φ (-90°<Φ<90°)的点投影到：y = sign(Φ)ln(tan(45° + abs(Φ/2))
墨卡托投影把经度度为Φ (-90°<Φ<90°)的点投影到：y = cos(Φ)ln(tan(45° + abs(Φ/2))

球在圆柱体的投影,
曲面投影,高度球面体的直径(6372797.560856),宽度是赤道的周长（3.14...... X 6372797.560856/2）

在纬度相等的情况下：

经度每隔0.00001度，距离相差约1米；
每隔0.0001度，距离相差约10米；
每隔0.001度，距离相差约100米；
每隔0.01度，距离相差约1000米；
每隔0.1度，距离相差约10000米。

在经度相等的情况下：

纬度每隔0.00001度，距离相差约1.1米；
每隔0.0001度，距离相差约11米；
每隔0.001度，距离相差约111米；
每隔0.01度，距离相差约1113米；
每隔0.1度，距离相差约11132米。

d.jpg f.jpg

在纬度相等的情况下：

经度每隔0.00001度，距离相差约1米；
每隔0.0001度，距离相差约10米；
每隔0.001度，距离相差约100米；
每隔0.01度，距离相差约1000米；
每隔0.1度，距离相差约10000米。
在经度相等的情况下：

纬度每隔0.00001度，距离相差约1.1米；
每隔0.0001度，距离相差约11米；
每隔0.001度，距离相差约111米；
每隔0.01度，距离相差约1113米；
每隔0.1度，距离相差约11132米。

Redis的GEOHash是把投影分割成N个HashBox，每个HashBox是一个四分项,redis分成了多个bucket

Base32编码16进制0-9,a-z 。0，1，2，3，4........9,a,b,c,d,e,f
private static final char[] 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'};

对经度146.842813452468进行区间二分的过程。这里左区间是左闭右开区间、右区间是左闭右闭区间

                左区间                                       右区间                     结果

---

[-180.000000000000000, 0.000000000000000) [ 0.000000000000000, 180.000000000000000] 1
[ 0.000000000000000, 90.000000000000000) [ 90.000000000000000, 180.000000000000000] 1
[ 90.000000000000000, 135.000000000000000) [ 135.000000000000000, 180.000000000000000] 1
[ 135.000000000000000, 157.500000000000000) [ 157.500000000000000, 180.000000000000000] 0
[ 135.000000000000000, 146.250000000000000) [ 146.250000000000000, 157.500000000000000] 1
[ 146.250000000000000, 151.875000000000000) [ 151.875000000000000, 157.500000000000000] 0
[ 146.250000000000000, 149.062500000000000) [ 149.062500000000000, 151.875000000000000] 0
[ 146.250000000000000, 147.656250000000000) [ 147.656250000000000, 149.062500000000000] 0
[ 146.250000000000000, 146.953125000000000) [ 146.953125000000000, 147.656250000000000] 0
[ 146.250000000000000, 146.601562500000000) [ 146.601562500000000, 146.953125000000000] 1
[ 146.601562500000000, 146.777343750000000) [ 146.777343750000000, 146.953125000000000] 1
[ 146.777343750000000, 146.865234375000000) [ 146.865234375000000, 146.953125000000000] 0
[ 146.777343750000000, 146.821289062500000) [ 146.821289062500000, 146.865234375000000] 1
[ 146.821289062500000, 146.843261718750000) [ 146.843261718750000, 146.865234375000000] 0
[ 146.821289062500000, 146.832275390625000) [ 146.832275390625000, 146.843261718750000] 1
[ 146.832275390625000, 146.837768554687500) [ 146.837768554687500, 146.843261718750000] 1
[ 146.837768554687500, 146.840515136718750) [ 146.840515136718750, 146.843261718750000] 1
[ 146.840515136718750, 146.841888427734380) [ 146.841888427734380, 146.843261718750000] 1
[ 146.841888427734380, 146.842575073242200) [ 146.842575073242200, 146.843261718750000] 1
[ 146.842575073242200, 146.842918395996100) [ 146.842918395996100, 146.843261718750000] 0

---

/**

• Hashing works like this:
• Divide the world into 4 buckets. Label each one as such:
  bucket就是盒子

• ---

• |___ | __ |
• | ___ | __ |
• | 0,1 | 1,1 |

• ---

• |__ | __ |
• |__ | __ |
• | 0,0 | 1,0 |

• ---

*/

地球上任意两点距离计算公式
/* latitude distance is less expensive to compute than longitude distance
* so we check first for the latitude condition */
double lat_distance = geohashGetLatDistance(y2, y1);
if (lat_distance > height_m/2) {
return 0;
}
double lon_distance = geohashGetDistance(x2, y2, x1, y2);
if (lon_distance > width_m/2) {
return 0;
}
distance = geohashGetDistance(x1, y1, x2, y2);
return 1;
地球上任意两点距离计算公式为
：
D＝R
arccos(siny1siny2+cosy1cosy2cos(x1-x2)
)
其中:R为地球半径，均值为6370km.
A点经、纬度分别为x1和y1,，东经为正，西经为负
B点经、纬度分别为x2和y2，北纬为正，南纬为

redis 实现思路

两点之间的计算方式


const double EARTH_RADIUS_IN_METERS = 6372797.560856;

//网格胡单元
const double MERCATOR_MAX = 20037726.37;
const double MERCATOR_MIN = -20037726.37;

//
int geohashDecodeAreaToLongLat(const GeoHashArea *area, double *xy) {
    if (!xy) return 0;
    xy[0] = (area->longitude.min + area->longitude.max) / 2;
    if (xy[0] > GEO_LONG_MAX) xy[0] = GEO_LONG_MAX;
    if (xy[0] < GEO_LONG_MIN) xy[0] = GEO_LONG_MIN;
    xy[1] = (area->latitude.min + area->latitude.max) / 2;
    if (xy[1] > GEO_LAT_MAX) xy[1] = GEO_LAT_MAX;
    if (xy[1] < GEO_LAT_MIN) xy[1] = GEO_LAT_MIN;
    return 1;
}


static void geohash_move_x(GeoHashBits *hash, int8_t d) {
    if (d == 0)
        return;

    uint64_t x = hash->bits & 0xaaaaaaaaaaaaaaaaULL;
    uint64_t y = hash->bits & 0x5555555555555555ULL;

    uint64_t zz = 0x5555555555555555ULL >> (64 - hash->step * 2);

    if (d > 0) {
        x = x + (zz + 1);
    } else {
        x = x | zz;
        x = x - (zz + 1);
    }

    x &= (0xaaaaaaaaaaaaaaaaULL >> (64 - hash->step * 2));
    hash->bits = (x | y);
}