一文了解geohash原理，实践实战设计思路

/**
 * @desc 利用递归思想 找出经纬度的二进制编码
 * @param float $place 经度或纬度
 * @param string $binary_array 每次递归拿到的bit值
 * @param int $max_separate_num递归总次数
 * @param array $section 区间值
 * @param int $num 递归次数
 * @return array
 */
public function binary($place = 0, $binary_array = [], $max_recursion_num = 20, $section = [], $num = 1)
{
    if (!$section) return $binary_array;

    // 获取中间值
    $count = ($section['max'] - $section['min']) / 2;

    // 左半边区间
    $left = [
        'min' => $section['min'],
        'max' => $section['min'] + $count
    ];

    // 右半边区间
    $right = [
        'min' => $section['min'] + $count,
        'max' => $section['max']
    ];

    // 假如给点的经纬度值大于右边最小值 则属于右半边区间为1 否则就是左半边区间 0
    array_push($binary_array, $place > $right['min'] ? 1 : 0);

    // 如果递归次数已经达到最大值 则直接返回结果集
    if ($max_recursion_num <= $num) return $binary_array;

    // 下一次递归我们需要传入的经纬度 区间值
    $section = $place > $right['min'] ? $right : $left;

    // 继续针对自身做的递归处理  一直到出现结果
    return $this->binary($place, $binary_array, $max_recursion_num, $section, $num + 1);
}

// 实例化调用该方法
require_once './Geohash.php';

$geohash = new Geohash();

echo  json_encode($geohash->binary(23.117596,[],$geohash->baseLengthGetNums(4, 1), $geohash->interval[0],1));

//结果集
[1,0,1,0,0,0,0,0,1,1]-> 二进制 101000 00011 这样是不是很清晰

//再看不明白的话  那么久打印出范围值：
[{"min":-90,"max":90},{"min":0,"max":90},{"min":0,"max":45},{"min":22.5,"max":45},{"min":22.5,"max":33.75},{"min":22.5,"max":28.125},{"min":22.5,"max":25.3125},{"min":22.5,"max":23.90625},{"min":22.5,"max":23.203125},{"min":22.8515625,"max":23.203125}]

local cjson = require("cjson")

-- 定义经纬度区间范围
local interval = {
    { min = -90,  max = 90 },
    { min = -180, max = 180 }
}

--- @desc 利用递归思想 找出经纬度的二进制编码
--- @param place string 经度或纬度
--- @param binary_array table 每次递归拿到的bit值
--- @param max_separate_num number 递归总次数
--- @param section table 区间值
--- @param num number 递归次数
function binary(place, binary_array, max_recursion_num, section, num)
    -- body
    place        = tonumber(place) or 0
    binary_array = binary_array and binary_array or {}
    max_recursion_num = tonumber(max_recursion_num) or 20
    section      =  section and section or {}
    num          = tonumber(num) or 1

    if not next(section) then
       return binary_array
    end
    print(cjson.encode(section))
    -- 获取中间值
    local count = (section["max"] - section["min"]) / 2
    -- 左半边区间
    local left = {
        min = section["min"],
        max = section["min"] + count
    }
    -- 右半边区间
    local right = {
        min = section["min"] + count,
        max = section["max"]
    }

    -- 假如给点的经纬度值大于右边最小值 则属于右半边区间为1 否则就是左半边区间 0
    binary_array[#binary_array+1] = place > right["min"] and 1 or 0

    -- 如果递归次数已经达到最大值 则直接返回结果集
    if max_recursion_num <= num then
        return binary_array
    end

    -- 下一次递归我们需要传入的经纬度 区间值
    local _section = place > right["min"] and right or left

    return binary(place, binary_array, max_recursion_num, _section, num + 1)
end


local res = binary(113.326059, {}, _base_length_get_nums(4, 1), interval[2], 1)

print(cjson.encode(res))

//打印结果
{"max":180,"min":-180}
{"max":180,"min":0}
{"max":180,"min":90}
{"max":135,"min":90}
{"max":135,"min":112.5}
{"max":123.75,"min":112.5}
{"max":118.125,"min":112.5}
{"max":115.3125,"min":112.5}
{"max":113.90625,"min":112.5}
{"max":113.90625,"min":113.203125}
[1,1,0,1,0,0,0,0,1,0]

--- @desc 根据指定编码长度获取经纬度的 二分层数
--- @param int $length 编码精确度
--- @param int $type 类型 0-纬度；1-经度
--- @return mixed
local function _base_length_get_nums(length, typ)
    -- 第一种方法写死
    local list = { {2, 3}, {5, 5}, {7, 8}, {10, 10}, {12, 13}, {15, 15}, {17, 18}, {20, 20}, {22, 23}, {25, 25}, {27, 28}, {30, 30} }
    
    -- 第二种通过规律计算纬度位数组合成list
    local cycle_num = 12
    local list_res  = {}
    local lat, lng  = 0, 0
    for i = 1, 12, 1 do
        lat = i % 2 == 0 and lat + 3 or lat + 2
        lng = i % 2 == 0 and lng + 2 or lng + 3
        list_res[#list_res + 1] = {lat, lng}
    end
   
    return list[length][typ]
end

整体的计算方式：
latitude的范围是：-90° 到 90°
longitude范围是：-180° 到 180°
地球参考球体的周长：40075016.68米

/**
 * @desc 编码组合
 * @param $latitude_str 纬度
 * @param $longitude_str 经度
 * @return string
 */
public function combination($latitude_str, $longitude_str)
{
    $result = '';
    //循环经度数字 作为偶数位置
    for ($i = 0; $i < strlen($longitude_str); $i++) {
         // 拼接经度作为偶数位置
        $result .= $longitude_str{$i};
        // 维度存在则拼接字符串
        if (isset($latitude_str{$i})) $result .= $latitude_str{$i};
    }
    return $result;
}
// 结果集
var_dump($geohash->combination('1010000011', '1101000010'));
11100110000000001101

function combination(latitude_arr, longitude_arr)
    local result = ''
    for i = 1, #longitude_arr do
        result = result..longitude_arr[i]
        if latitude_arr[i] then
            result = result..latitude_arr[i]
        end
    end
    return result
end
//结果集
print(cjson.encode(combination({1,0,1,0,0,0,0,0,1,1}, {1,1,0,1,0,0,0,0,1,0})))
11100110000000001101

又会有小伙们问了为啥要去掉(a, i, l, o)这四个字母？ 有没有疑问的，有的请下方扣1！！！！！

11100 = 2^4+2^3+2^2 = 16+8+4 = 28  也就是对应w字符串；看下下面对应的维基百科的字典表

/**
 * @desc 将二进制字符串转为十进制 再转换为对应的编码
 * @param $str
 * @return string
 */
public function encode($str = '')
{
    $string = '';

    // 按照5位分割字符串
    $array    = str_split($str, 5);
    if (!$array) return $string;
    foreach ($array as $va) {
        //二进制转换为十进制
        $decimal    = bindec($va);
        $string .= $this->base_32[$decimal];
    }
    return $string;
}
// 结果集是ws0e
var_dump($geohash->encode('11100110000000001101'));

CREATE TABLE `user_place` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `user_id` int(10) DEFAULT NULL DEFAULT '0' COMMENT '用户id',
  `longitude` double DEFAULT NULL DEFAULT '' COMMENT '经度',
  `latitude` double DEFAULT NULL  DEFAULT ''COMMENT '纬度',
  `create_time` int(10) DEFAULT NULL DEFAULT '0' COMMENT '创建时间',
  PRIMARY KEY (`id`),
  KEY `idx_longe_lat` (`longitude`,`latitude`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

SELECT * FROM `user_place` WHERE (longitude BETWEEN minlng(最小经度) AND maxlng(最大经度)) AND (latitude BETWEEN minlat(最小纬度) AND maxlat(最大纬度))

查询之后结果集之后，通过经纬度计算距离

// 当前自己的经纬度坐标
$latitude  = 23.117596
$longitude = 113.326059
//一系列的复杂计算用到了 mysql中的 三角函数 ASIN函数：反正弦值； POWER函数：用于计算 x 的 y 次方。其他的小伙伴们百度查吧  正弦、余弦
fields = "user_id,ROUND(6378.138*2*ASIN(SQRT(POW(SIN(($latitude*PI()/180-latitude*PI()/180)/2),2)+COS($latitude*PI()/180)*COS(latitude*PI()/180)*POW(SIN(($longitude*PI()/180-longitude*PI()/180)/2),2)))*1000,2) AS distance";

selecet fields from `user_place` having distance <= 10 order by distance asc limit 10

 1、ST_GeoHash(longitude, latitude, max_length -- 生成geohash值
 
mysql> SELECT ST_GeoHash(116.336506,39.978729,10);
+-------------------------------------+
| ST_GeoHash(116.336506,39.978729,10) |
+-------------------------------------+
| wx4ermcsvp                          |
+-------------------------------------+
1 row in set (0.00 sec)
 
 2、ST_LongFromGeoHash() -- 从geohash值返回经度
 
 mysql> SELECT ST_LongFromGeoHash('wx4ermcsvp');
+----------------------------------+
| ST_LongFromGeoHash('wx4ermcsvp') |
+----------------------------------+
|                        116.33651 |
+----------------------------------+
1 row in set (0.00 sec)
 
 3、ST_LatFromGeoHash()  -- 从geohash值返回纬度
 
 mysql> SELECT ST_LatFromGeoHash('wx4ermcsvp');
+---------------------------------+
| ST_LatFromGeoHash('wx4ermcsvp') |
+---------------------------------+
|                        39.97873 |
+---------------------------------+
1 row in set (0.00 sec)
 
 4、ST_PointFromGeoHash() -- 将geohash值转换为point值
 
 mysql> SELECT ST_AsText(ST_PointFromGeoHash('wx4ermcsvp',0));
+------------------------------------------------+
| ST_AsText(ST_PointFromGeoHash('wx4ermcsvp',0)) |
+------------------------------------------------+
| POINT(116.33651 39.97873)                      |
+------------------------------------------------+
1 row in set (0.00 sec)

具体用法其实都差不多的，小伙伴们可以查查相关资料看看！用的不是很多

-- 先添加字段 geohash
alter table `user` add `geohash` varchar(64) NOT NULL DEFAULT NULL COMMENT '经纬度对应geohash码值',
-- 再添加geohash的普通索引
 alter table `user` add index idx_geohash ( `geohash` )
-- 查询sql
select * from `user` where `geohash` like 'geohash%' order by id asc limit 100

-- 例如有一下8个值 geohash1、geohash2、geohash3、geohash4、geohash5、geohash6、geohash7、geohash8
-- 查询sql
select * from `user` where `geohash` regexp 'geohash1|geohash2|geohash3|geohash4' order by id asc limit 100

1、geopos指令：geopos key member [member ...] 获取指定key里返回所有指定名称的位置(经度和纬度)；时间复杂度O(log(n))，n是排序集中的元素数

注意事项：
① geopos命令返回的是一个数组，每个数组中的都由两个元素组成：第一个是位置的经度， 而第二个是位置的纬度。 
② 若给定的元素不存在，则对应的数组项为nil(不要搞错以为是一个空数组)。

2、geodist指令：geodist key member1 member2 [m|km|ft|mi] 获取两个给定位置之间的距离；时间复杂度O(log(n))，n是排序集中的元素数

注意事项：
① member1和member2 为两个地理位置名称，例如用户id标识。
② [m|km|ft|mi]尾部参数：
    m  ：米，默认单位
    km ：千米
    mi ：英里
    ft ：英尺

③ 计算出的距离会以双精度浮点数的形式被返回；位置不存在，则返回nil。

3、georadius指令：georadius key longitude latitude radius [m|km|ft|mi] [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key] 

根据用户给定的经纬度坐标来获取指定范围内的地理位置集合；时间复杂度： O(n+log(m))，n是圆形区域的边界框内的元素数，该元素由中心和半径定界，m是索引内的项数。

注意事项：
① 以给定的经纬度为中心
② [m|km|ft|mi]单位说明
    m ：米，默认单位
    km ：千米
    mi ：英里
    ft ：英尺
③ withdist: 在返回位置元素的同时， 将位置元素与中心之间的距离也一并返回。
④ withcoord: 将位置元素的经度和维度也一并返回。
⑤ withhash: 以 52 位有符号整数的形式，返回位置元素经过原始geohash编码的有序集合分值。这个选项主要用于底层应用或者调试， 实际中的作用并不大。
⑥ count 限定返回的记录数。
⑦ asc: 查找结果根据距离从近到远排序。
⑧ desc: 查找结果根据从远到近排序。

4、georadiusbymember指令：georadiusbymember  key member radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key]
获取指定范围内的元素数据，中心点是由给定的位置元素决定的，不是使用经度和纬度来决定中心点。时间复杂度： O(n+log(m))，n是圆形区域的边界框内的元素数，该元素由中心和半径定界，m是索引内的项数。

注意事项同上面georadius指令！！！

5、geohash指令：geohash key member [member ...] 获取一个或多个位置元素的geohash值；时间复杂度O(log(n))，n是排序集中的元素数

注意事项：
① 该命令返回的是一个数组格式，位置不存在则返回nil
② 数组结果集的值跟给出位置一一对应，说白了就是下标一致

geoadd指令：geoadd key longitude latitude member [longitude latitude member ...] 
添加地理位置的坐标；时间复杂度O(log(n))，n是排序集中的元素数。

注意事项：
① 实际存储的数据类型是zset，member是zset的value，score是根据经纬度计算出geohash
② geohash是52bit的长整型，计算距离使用的公式是Haversine
③ geoadd添加的坐标会有少许的误差，因为geohash对二维坐标进行一维映射是有损耗的

① O(1)解析：

O(1)就是最低的时空复杂度了，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。

② O(n)解析：
比如时间复杂度为O(n)，就代表数据量增大几倍，耗时也增大几倍。比如常见的遍历算法。 

要找到一个数组里面最大的一个数，你要把n个变量都扫描一遍，操作次数为n，那么算法复杂度是O(n).

③ O(n^2)解析：

比如时间复杂度O(n^2)，就代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。 

用冒泡排序排一个数组，对于n个变量的数组，需要交换变量位置次，那么算法复杂度就是O().

③ O(logn)解析：

比如O(logn)，当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度)，二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。 


④ O(nlogn)解析：
O(nlogn)同理，就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。 

/**
 * @desc 添加用户地理位置 可以添加多个 大家可以测试下 修改下方法
 * @param int $user_id
 * @param int $latitude
 * @param int $longitude
 * @return int
 */
public function insert($user_id = 0, $latitude = 0, $longitude = 0)
{
    $result = $this->redis->geoAdd($this->key, $longitude, $latitude, $user_id);

    return $result;
}

/**
 * @desc 搜索附近人结果集
 * @param int $distance
 * @param int $latitude
 * @param int $longitude
 * @return mixed
 */
public function searchNearby($distance = 300, $latitude = 0, $longitude = 0)
{
    $result = $this->redis->georadius(
        $this->key,
        $longitude,
        $latitude,
        $distance,
        'mi',
        ['WITHDIST','count' => 10,'DESC']
    );
    return $result;
}

// 调用 获取结果集
$res = new GeoRedis();
var_dump($res->searchNearby(300, 21.306,-157.858));
array(2) {
  [0]=>
  array(2) {
    [0]=>
    string(4) "1001" //用户id
    [1]=>
    string(8) "104.5615" //距离
  }
  [1]=>
  array(2) {
    [0]=>
    string(4) "1002"
    [1]=>
    string(8) "104.5615"
  }
}

localhost:6379> zrange user:nearby 0 10 withscores
 1) "1001"
 2) "1184565520453603"
 3) "1002"
 4) "1184565520453603"
 5) "1003"
 6) "1231646528010636"
 7) "1004"
 8) "1231732998886639"
 9) "1005"
10) "1235058932387089"

-- 创建索引
db.coll.createIndex({'location':'2dsphere'})

-- 空间查询语法
① 位置相交 db.coll.map.find({'location':{'$geoIntersects':{'$geometry':area}})
② 位置包含 db.coll.map.find({'location':{'$within':{'$geometry':area}})
③ 位置接近 db.coll.map.find({'location':{'$near':{'$geometry':area}})

-- 创建索引  索引的精度通过bits来指定，bits越大，索引的精度就越高
db.coll.createIndex({'location':"2d"}, {"bits":30})

-- 查询语法
① 位置包含  db.coll.map.find({'location':{'$within':[[10,10],[20,20]]})    
② 矩形包含  db.coll.map.find({'location':{'$within':{'$box':[[10,10],[20,20]]}})   
③ 中心包含  db.coll.map.find({'location':{'$within':{'$center':[[20,20],5]}})  
④ 多边形包含 db.coll.map.find({'location':{'$within':{'$polygon':[[20,20],[10,10],[10,18],[13,21]]}})   
⑤ 位置接近 db.coll.map.find({'location':{'$near':[10,20]})

db.user.insertMany([
     {'user_id':1001, 'user_name':'阿沐1', loc:[122.431, 37.773]},
     {'user_id':1002, 'user_name':'阿沐2', location:[157.858, 21.315]},
     {'user_id':1003, 'user_name':'阿沐3', location:[155.331, 21.798]},
     {'user_id':1004, 'user_name':'阿沐4', location:[157.331,22.798]},
     {'user_id':1005, 'user_name':'阿沐5', location:[151.331, 25.798]},
     {'user_id':1006, 'user_name':'阿沐6', location:[147.942428, 28.67652]},
])

db.coll.createIndex({'location':"2d"}, {"bits":30})

db.user.aggregate({
    $geoNear:{
        near: [157.858, 21.306],     // 当前自己坐标
        spherical: true,             // 计算球面距离
        distanceMultiplier: 6378137, // 地球半径，单位是米，默认6378137
        maxDistance: 300/6378137,    // 过滤条件300米内，需要弧度
        distanceField: "distance"    // 距离字段别名
    }
})

//当前结果集为模拟结果，因本机电脑docker没有安装mongo
{ "_id" : ObjectId("4e96b3c91b8d4ce765381e58"), 'user_id':1001, 'user_name':'阿沐1', "location" : [ 122.431, 37.773 ], "distance" : 5.10295397457355 }
{ "_id" : ObjectId("4e96b5c91b8d4ce765381e51"), 'user_id':1002, 'user_name':'阿沐2', "location" : [ 157.858, 21.315 ], "distance" : 255.81213803417531 }

GET api/query/search/
{
  "query": {
    "geo_distance": {
      "distance": "1km",
      "location": {
        "lat": 21.306,
        "lon": 157.858
      }
    }
  }
}