基于Redis的GeoHash在PHP上的应用

Posted on 2018-11-29 Edited on 2019-09-12

GeoHash有着以下几个特点

GeoHash用一个字符串表示经度和纬度两个坐标,便于加上索引.
GeoHash表示的并不是一个点，而是一个矩形区域.
编码的前缀可以表示更大的区域, 可以很方便的进行区域检索, 聚合等相关操作.

综上所述, GeoHash比直接用经纬度的高效很多.

➡️GeoHash算法

编码

GeoHash首先将精度范围设定为划分成两个区间(-180, 0), (0, 180), 如果经度坐标落到了前一个区间则标记为0, 反之则标记为1.
然后再将上一步获得到的区间划分成两个区间, 重复上一步.
重复前前两步直到得到自己所需要的精度
以此类推来得到纬度的HashBin (关于纬度的初始划分区间, 一般的共用算法里都是±90, 而redis里用的却是±85.05112878)
如 (23.17015353059966287, 113.46623629331588745) 通过区间划分可以得到:
(1101000010101111111001011110, 101000101101111011011100011)
接下来是对划分结果的合并, 按照奇数位是纬度, 偶数位为经度的原则来进行合并.
上面的例子合并可得:
1110011000000100110110011111111011111001011100101011110
之后再按照非标准的base32算法进行字符串的转化, 下面是对照表格

十进制	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
二进制	00000	00001	00010	00011	00100	00101	00110	00111	01000	01001	01010	01011	01100	01101	01110	01111
base32	0	1	2	3	4	5	6	7	8	9	b	c	d	e	f	g
十进制	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
二进制	10000	10001	10010	10011	10100	10101	10110	10111	11000	11001	11010	11011	11100	11101	11110	11111
base32	h	j	k	m	n	p	q	r	s	t	u	v	w	x	y	z

最终(23.17015353059966287, 113.46623629331588745)被转化成’ws2emzrtfby’.

解码则和编码正好相反即可.

➡️PHP的实现

class Geohash
{
    private static $coding    = '0123456789bcdefghjkmnpqrstuvwxyz';
    private static $codingMap = [
        '0' => '00000', '1' => '00001', '2' => '00010',
        '3' => '00011', '4' => '00100', '5' => '00101',
        '6' => '00110', '7' => '00111', '8' => '01000',
        '9' => '01001', 'b' => '01010', 'c' => '01011',
        'd' => '01100', 'e' => '01101', 'f' => '01110',
        'g' => '01111', 'h' => '10000', 'j' => '10001',
        'k' => '10010', 'm' => '10011', 'n' => '10100',
        'p' => '10101', 'q' => '10110', 'r' => '10111',
        's' => '11000', 't' => '11001', 'u' => '11010',
        'v' => '11011', 'w' => '11100', 'x' => '11101',
        'y' => '11110', 'z' => '11111'
    ];

    public static function decode(string $hash, $number = false)
    {
        if ($number) {
            $binary = base_convert($hash, 10, 2);
        } else {
            $binary = '';
            $hl     = strlen($hash);

            for($i=0; $i<$hl; $i++) {
                $binary .= self::$codingMap[substr($hash,$i,1)];
            }
        }

        $bl    = strlen($binary);
        $blat  = '';
        $blong = '';

        //取出经纬度
        for ($i=0; $i<$bl; $i++)
        {
            if ($i%2)
                $blat  = $blat.substr($binary,$i,1);
            else
                $blong = $blong.substr($binary,$i,1);

        }

        //翻译经纬度
        list(
            $lat,
            $latErr
            ) = self::binDecode($blat,-85.05112878,85.05112878);
        list(
            $long,
            $longErr
            ) = self::binDecode($blong,-180,180);

        //精度处理
        $latPlaces  = max(1, -round(log10($latErr))) - 1;
        $longPlaces = max(1, -round(log10($longErr))) - 1;

        $lat        = round($lat, $latPlaces);
        $long       = round($long, $longPlaces);

        return [$lat, $long];
    }

    public static function hash2num(string $hash, $bin = false)
    {

        $binary = '';
        $hl     = strlen($hash);
        for($i=0; $i<$hl; $i++)
        {
            $binary .= self::$codingMap[substr($hash,$i,1)];
        }

        if ($bin)
            return $binary;

        return base_convert(substr($binary, 0, 52), 2, 10);
    }

    /**
     * 坐标转化
     * @param $lat
     * @param $long
     * @return string
     */
    public static function encode(
        $lat, $long,
        bool $number = false
    ) :string {
        //计算lat精度
        $latbits = 1;
        $err     = 45;
        $plat    = self::precision($lat);
        //计算计算次数
        while($err > $plat)
        {
            $err     /= 2;
            $latbits ++;
        }

        $longbits = 1;
        $err      = 90;
        $plong    = self::precision($long);
        while($err > $plong)
        {
            $err      /= 2;
            $longbits ++;
        }

        $bits     = max($latbits, $longbits);

        $longbits = $bits;
        $latbits  = $bits;
        $addlong  = 1;

        //为了可以进行合并填充数位 2^5 = 32
        while (($longbits+$latbits)%5 != 0)
        {
            $longbits += $addlong;
            $latbits  += !$addlong;
            $addlong  = !$addlong;
        }

        $blat     = self::binEncode($lat,90, 90, $latbits);
        $blong    = self::binEncode($long, -180, 180, $longbits);

        $binary  = '';
        $uselong = 1;
        $strlen  = strlen($blat) + strlen($blong);

        //合并位数
        for ($i = 0; $i<$strlen; $i++) {
            if ($uselong)
            {
                $binary .= substr($blong,0,1);
                $blong  = substr($blong,1);
            }
            else
            {
                $binary .= substr($blat,0,1);
                $blat   = substr($blat,1);
            }
            $uselong = !$uselong;
        }
        if ($number)
            return bindec(substr($binary, 0, 52));

        $hash = '';
        $leng = strlen($binary);
        for ($i=0; $i<$leng; $i+=5)
        {
            $n    = bindec(substr($binary,$i,5));
            $hash = $hash. self::$coding[$n];
        }

        return $hash;
    }

    /**
     * 计算精度
     * @param float $number
     * @return float|int
     */
    private static function precision(float $number)
    {
        $precision = 0;
        $pt        = strpos($number,'.');
        if ($pt !== false)
        {
            $precision = - (strlen($number) - $pt - 1);

        }

        return pow(10, $precision) / 2;
    }

    private static function binEncode($number, $min, $max, $bitcount)
    {
        if ($bitcount == 0)
            return '';
        $mid = bcdiv(bcadd($min, $max, 52), 2, 52);
        if (bccomp($number, $mid, 52) == 1)
            return '1'. self::binEncode(
                $number, $mid,
                $max,$bitcount-1
            );
        else
            return '0'. self::binEncode(
                $number, $min,
                $mid,$bitcount-1
            );
    }

    private static function binDecode(
        $binary, $min,
        $max
    ) {
        $binlen = strlen($binary);
        $err    = bcsub($max, $min, 52);

        for($i = 0; $i < $binlen; $i++) {
            $bit = substr($binary,$i,1);
            $mid = bcdiv(bcadd($min, $max, 52), 2, 52);
            $err = bcdiv($err, 2, 52);
            if ($bit == 1) {
                $min = $mid;
            } else {
                $max = $mid;
            }
        }

        return [$mid, $err];
    }
}

➡️Redis上的应用

Redis的GEO特性在Redis 3.2版本释出,这个功能可以将用户给定的地理位置信息储存起来,并对这些信息进行操作.

GEOADD

1	GEOADD key longitude latitude name [longitude latitude name ...]

GEOADD 命令每次可以添加一个或多个经纬度地理位置。其中key为储存地理位置的集合，而 longitude 、 latitude 和 name 则分别为地理位置的经度、纬度、名字.

1	127.0.0.1:6379> GEOADD geo_test 113.46623629331588745 23.17015353059966287 test_1 113.46620947122573853 23.17010790561879929 test_2

GEOPOS
GEOPOS 命令可以获取Geo的坐标

1	GEOPOS key name [name ...]

如:

1
2
3

127.0.0.1:6379> geopos geo_test test_2
1) 1) "113.46620947122573853"
   2) "23.17010790561879929"

GEODIST
计算两个坐标点之间的距离

1	GEODIST key location-x location-y [unit]

其中unit表示单位默认为 m

m 表示单位为米。
km 表示单位为千米。
mi 表示单位为英里。
ft 表示单位为英尺。

GEORADIUS 和 GEORADIUSBYMEMBER
这两个命令都是获取一定范围内的坐标

1
2

GEORADIUS key longitude latitude radius m|km|ft|mi[WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key]
GEORADIUSBYMEMBER key location radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key]

WITHCOORD 在返回匹配的位置时会将位置的经纬度一并返回.
WITHDIST 指定中心返回项目的距离, 距离以与指定为命令的radius参数的单位相同的单位返回.
WITHHASH 还以52位无符号整数的形式返回项的原始geohash编码的有序集分数
ASC|DESC ASC 可以让查找结果根据距离从近到远排序，而 DESC 则可以让查找结果根据从远到近排序
COUNT 指定要返回的结果数量
STORE key 结果存到新的有序集合中, 以GeoHash值做score, 该选项与WITH[DIST|COORD|HASH]选项冲突
STOREDIST key 结果存到新的有序集合中, 以与指定位置的距离作score, 该选项与WITH[DIST|COORD|HASH]选项冲突

127.0.0.1:6379> georadius key 113.46620947122573853 23.17010790561879929 100 km WITHCOORD WITHDIST
1) 1) "test_2"
   2) "0.0000"
   3) 1) "113.46620947122573853"
      2) "23.17010790561879929"
127.0.0.1:6379>

GEOHASH
将redis里的Geo转化为标准的GeoHash输出
注意:这里输出的是标准的GeoHash, 不是redis里面存储的HashInt转化出来的

1	GEOHASH key member [member ...]

1
2
3

127.0.0.1:6379> geohash geo_test test_1 test_2
1) "7pkg3sdkv40"
2) "ws0evczxdm0"

➡️存储原理

Redis里的Geo坐标在实际存储时是将gps坐标分别按照(-180, 180)和(-85.05112878, 85.05112878)来划分计算成HashInt作为zset集合进行存储的.
所以Redis的Geo操作中并没有删除命令, 可以直接使用zrem命令去删除Geo坐标.