空间索引-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个区域。第一次对地图划分后的情况如下图所示(每个区域中的编号对应于该区域所对应的编码):

如图:

image.png


算法实现(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的纬度区间算法函数:

/**

 * @param float $num经度或纬度

 * @param string $str递归字符串

 * @param int $i 递归次数

 * @param int $max_separate_num递归总次数

 * @param array $data 区间值

 * @return string

 */

functionseparate( $num= 24.999,$str='',$i=1,$max_separate_num=20,$dataarray('min'=> -90, 'max'=> 90))

{

    $count   = ($data['max'] - $data['min']) / 2;

    $limit_0array(

        'min'=> $data['min'],

        'max'=> $data['min'] + $count

    );

    $limit_1array(

        '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{

        returnseparate($num,$str,$i+1,$max_separate_num,$num$limit_1['min']?$limit_1:$limit_0);

    }

 

}

  1. 由此,纬度24.88849可得字符串为10100011011001011001
  2. 经度118.6197800000,经度分为东经和西经,区间为[-180,180],由此可得字符串11010100010110100001
  3. 组合2个字符串,偶数放经度位,奇数放纬度位,php代码实现

/**

 * @param $latitude_str 纬度

 * @param $longitude_str 经度

 */

functioncombination($latitude_str$longitude_str)

{

    $str'';

    for($i= 0; $istrlen($longitude_str); $i++) {//根据精度表,可发现纬度>=经度

        $str.= $longitude_str{$i};

        if(isset($latitude_str{$i})){

            $str.=  $latitude_str{$i};

        }

    }

    return$str;

}

  1. 每隔5位取出一串,转为10进制,最后使用[0-9][b-z]去掉a, i, l, o这32个字符进行编码.php代码实现

functiongeohash_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_arrstr_split($str, 5);//按5位分割字符串

    $str     '';

//    var_dump($str_arr);die;

    foreach($str_arras$va) {

        $decimalbindec($va);

        $str.=$arr[$decimal];

    }

    return$str;

}

  1. 这样,就得到了一串'wskme6b3'字符串了,该字符串就表示了一个区域

geohash算法使用:

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

image.png


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

selectfromdm_gps wheregeohash like"wskme%"(记得加索引)

用法补充:

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

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

image.png

gps_id无用字段,请忽略

查出精度为2的数据:

image.png


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


精度bug

一:如图:image.png

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

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



附录:geohash精度

image.png

php扩展

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

传送门:https://www.oschina.net/news/48848/geohash-1-1


其他补充

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

目录
相关文章
|
4月前
|
算法 索引
【算法】二分算法——山脉数组的峰顶索引
【算法】二分算法——山脉数组的峰顶索引
|
7月前
|
存储 算法 物联网
R-Tree算法:空间索引的高效解决方案
【5月更文挑战第17天】R-Tree是用于多维空间索引的数据结构,常用于地理信息系统、数据库和计算机图形学。它通过分层矩形区域组织数据,支持快速查询。文章介绍了R-Tree的工作原理、应用场景,如地理信息存储和查询,以及Python的`rtree`库实现示例。此外,还讨论了R-Tree的优势(如空间效率和查询性能)与挑战(如实现复杂和内存消耗),以及优化和变种,如R* Tree和STR。R-Tree在机器学习、实时数据分析等领域有广泛应用,并与其他数据结构(如kd-trees和quad-trees)进行比较。未来趋势将聚焦于优化算法、动态适应性和分布式并行计算。
236 1
|
4月前
|
算法
计算空间物体包围球的两种算法实现
计算空间物体包围球的两种算法实现
52 0
|
4月前
|
算法 C++
空间中判断点在三角形内算法(方程法)
空间中判断点在三角形内算法(方程法)
65 0
|
4月前
|
算法
空间点与直线距离算法
空间点与直线距离算法
59 0
|
4月前
|
算法 C++
空间直线与球面相交算法
空间直线与球面相交算法
35 0
|
4月前
|
算法 Java 索引
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
38 0
|
6月前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
6月前
|
机器学习/深度学习 算法
五种基于RGB色彩空间统计的皮肤检测算法
五种基于RGB色彩空间统计的皮肤检测算法
43 0
|
6月前
|
存储 算法
数据结构学习记录——图应用实例-六度空间(题目描述、算法思路、伪代码及解读、图解)
数据结构学习记录——图应用实例-六度空间(题目描述、算法思路、伪代码及解读、图解)
66 0