专栏首页仙士可博客空间索引-geohash算法实现

空间索引-geohash算法实现

算法简介

geohash是实现空间索引的一种算法,其他实现空间索引的算法有:R树和其变种GIST树、四叉树、网格索引等

算法基本原理

geohash算法将地球理解为一个二维平面,将平面递归分解成更小的子块,每个子块在一定经纬度范围内拥有相同的编码,这种方式简单粗暴,可以满足对小规模的数据进行经纬度的检索

通过对经纬度的分割,将地球分割成无数的小正方形,每个区域,就是个geohash编码

Geohash其实就是将整个地图或者某个分割所得的区域进行一次划分,由于采用的是base32编码方式,即Geohash中的每一个字母或者数字(如wx4g0e中的w)都是由5bits组成(2^5 = 32,base32),这5bits可以有32中不同的组合(0~31),这样我们可以将整个地图区域分为32个区域,通过00000 ~ 11111来标识这32个区域。第一次对地图划分后的情况如下图所示(每个区域中的编号对应于该区域所对应的编码):

如图:

算法实现(php)

  1. 以经纬度值:(118.6197800000,24.88849)进行算法说明,对纬度24.88849进行逼近编码 (地球纬度区间是[-90,90])
  2. 纬度区间[-90,90]进行二分为[-90,0],[0,90],命名为左右区间,坐标属于右区间记为1,左区间为0,24.88849为右区间,记为1
  3. 对所在区间进行再次划分[0,90]二分为[0,45],[45,90],24.88849属于左区间,左区间记为0
  4. 以下是php的纬度区间算法函数:
  5. /**  * @param float $num经度或纬度  * @param string $str递归字符串  * @param int $i 递归次数  * @param int $max_separate_num递归总次数  * @param array $data 区间值  * @return string  */ function separate( $num = 24.999,$str='',$i=1,$max_separate_num=20,$data = array('min' => -90, 'max' => 90)) {     $count   = ($data['max'] - $data['min']) / 2;     $limit_0 = array(         'min' => $data['min'],         'max' => $data['min'] + $count     );     $limit_1 = array(         'min' => $data['min'] + $count,         'max' => $data['max']     ); //    var_dump($limit_0,$limit_1);     $str.=$num > $limit_1['min']?1:0;     if($i>=$max_separate_num){         return $str;     }else{         return separate($num,$str,$i+1,$max_separate_num,$num > $limit_1['min']?$limit_1:$limit_0);     } }
  6. 由此,纬度24.88849可得字符串为10100011011001011001
  7. 经度118.6197800000,经度分为东经和西经,区间为[-180,180],由此可得字符串11010100010110100001
  8. 组合2个字符串,偶数放经度位,奇数放纬度位,php代码实现
  9. /**  * @param $latitude_str 纬度  * @param $longitude_str 经度  */ function combination($latitude_str, $longitude_str) {     $str = '';     for ($i = 0; $i < strlen($longitude_str); $i++) {//根据精度表,可发现纬度>=经度         $str .= $longitude_str{$i};         if(isset($latitude_str{$i})){             $str .=  $latitude_str{$i};         }     }     return $str; }
  10. 每隔5位取出一串,转为10进制,最后使用[0-9][b-z]去掉a, i, l, o这32个字符进行编码.php代码实现
  11. function geohash_encode($str) {     $arr     = ['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'];     $str_arr = str_split($str, 5);//按5位分割字符串     $str     = ''; //    var_dump($str_arr);die;     foreach ($str_arr as $va) {         $decimal = bindec($va);         $str.=$arr[$decimal];     }     return $str; } 这样,就得到了一串'wskme6b3'字符串了,该字符串就表示了一个区域

geohash算法使用:

根据附录精度,传入经纬度生成geohash编码,存入数据库,例如:

当需要查询附近某个区域块点时,只需要,就可以查出该区域块所有数据

select * from dm_gps where geohash like "wskme%" (记得加索引)

用法补充:

当碰到需要渲染一整个地图,而数据量大的时候怎么办?总不可能把几千万的点全部查出来渲染吧?

可以新增一个大区域块统计表,将精度更小的数据进行分组并且统计总数,例如:

gps_id无用字段,请忽略

查出精度为2的数据:

当地图放大时:可相应的查出:level=3,level=4.....等等数据

精度bug

一:如图:

当查询红点所在区域时,数据库只能查询到该区域块右下角的点,而找不到离他更近的上面的绿点

该bug可通过查询周围8个区域块进行再次比对,或者增加精度到厘米级别,就可忽略该bug

附录:geohash精度

php扩展

php已经实现了对geohash的扩展,

其他补充

等有时间,将会把geohash解码算法发出来

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • js格式化字符串自动补位

    PHP的sprintf()函数可以格式化字符串并且自动补位,而js是没有这个函数的,可以自己自定义一个

    仙士可
  • 空间索引-geohash编码解码类

    算法实现原理请看:http://www.php20.cn/article/125

    仙士可
  • mysql存储过程下分割字符串函数

    MySQL存储过程可以用于分割字符串,下面就为您详细介绍这种MySQL存储过程的用法,供您参考学习之用。     现有一段字符串,如apple,banana,o...

    仙士可
  • 介绍一些Python str类的方法

    上面的代码正确的返回了'0.333333',但是当x = 1 / 2时,由于小数只有一位,这个方案的结果就是'0.5'了,而不是预期中的'0.500000'。

    ★忆先★
  • C语言函数传值的相关问题

    上述输出为null,其实不小心犯了个低级错误,那就是: 调用getmem时是值传递,str本身在getmem之后并没有获得相应空间,原因即getmem中的*p ...

    ZONGLYN
  • LintCode 旋转字符串题目分析代码

    样例 对于字符串 "abcdefg". offset=0 => "abcdefg" offset=1 => "gabcdef" offset=2 => ...

    desperate633
  • Python过滤不可见字符

        for i in range(0,32):         str = str.replace(chr(i),'')

    py3study
  • python学习总结五(python序列

    成员关系符就是判断一个字符是否属于这个字符串,再就是这个字符串是否属于这个元组,或者列表。返回值也是布尔值(True,Flase)。

    py3study
  • 去除字符数组中指定的字符

    Winter_world
  • js格式化字符串自动补位

    PHP的sprintf()函数可以格式化字符串并且自动补位,而js是没有这个函数的,可以自己自定义一个

    仙士可

扫码关注云+社区

领取腾讯云代金券