空间索引-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)
-
以经纬度值:(118.6197800000,24.88849)进行算法说明,对纬度24.88849进行逼近编码 (地球纬度区间是[-90,90])
-
纬度区间[-90,90]进行二分为[-90,0],[0,90],命名为左右区间,坐标属于右区间记为1,左区间为0,24.88849为右区间,记为1
-
对所在区间进行再次划分[0,90]二分为[0,45],[45,90],24.88849属于左区间,左区间记为0
-
以下是php的纬度区间算法函数:
-
/** * @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); } }
-
由此,纬度24.88849可得字符串为10100011011001011001
-
经度118.6197800000,经度分为东经和西经,区间为[-180,180],由此可得字符串11010100010110100001
-
组合2个字符串,偶数放经度位,奇数放纬度位,php代码实现
-
/** * @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; }
-
每隔5位取出一串,转为10进制,最后使用[0-9][b-z]去掉a, i, l, o这32个字符进行编码.php代码实现
-
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的扩展,
传送门:https://www.oschina.net/news/48848/geohash-1-1
其他补充
等有时间,将会把geohash解码算法发出来
- 本文标签: 编程语言
- 本文链接: https://www.php20.cn/article/125
- 版权声明: 本文由仙士可原创发布,转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权