geoHash算法入门学习总结

简介: geoHash算法

一。geoHash简介
geohash的思想是将二维的经纬度转换成一维
的字符串,geohash有以下三个特点:
1.字符串越长,表示的范围越精确。编码长度为8时,精度
在19米左右,而当编码长度为9时,精度在2米左右。
2.字符串相似的表示距离相近,利用字符串的前缀匹配,
可以查询附近的地理位置。这样就实现了快速查询某个
坐标附近的地理位置。
3.geohash计算的字符串,可以反向解码出原来的经纬度。
4.geoHash表示的并不是一个点,而是一个区域;
二。GeoHash算法的步骤
1.地球纬度区间是[-90,90], 北海公园的纬度是39.928167,可以通过
下面算法对纬度39.928167进行逼近编码:
1)区间[-90,90]进行二分为[-90,0),[0,90],称为左右区间,可以确定
39.928167属于右区间[0,90],给标记为1;
2)接着将区间[0,90]进行二分为 [0,45),[45,90],可以确定39.928167属
于左区间 [0,45),给标记为0;
3)递归上述过程39.928167总是属于某个区间[a,b]。随着每次迭代区
间[a,b]总在缩小,并越来越逼近39.928167;
4)如果给定的纬度x(39.928167)属于左区间,则记录0,如果属于
右区间则记录1,这样随着算法的进行会产生一个序列1011100,序列
的长度跟给定的区间划分次数有关。
同理,地球经度区间是[-180,180],可以对经度116.389550进行编码。
通过上述计算,纬度产生的编码为10111 00011,
经度产生的编码为11010 01011。偶数位放经度,奇
数位放纬度,把2串编码组合生成新串:11100
11101 00100 01111。

    最后使用用0-9、b-z(去掉a, i, l, o)这32个字母

进行base32编码,首先将11100 11101 00100 01111
转成十进制,对应着28、29、4、15,十进制对应
的编码就是wx4g。
同理,将编码转换成经纬度的解码算法与之相反。

   这样就可以理解字符串越长的编码越精确,因为它经过多次逼近,

更接近于实际值;越相似的字符串他们之间的距离也就越近。

    可以看出,当geohash base32编码长度为8时,精度在19米左右,

而当编码长度为9时,精度在2米左右,编码长度需要根据数据情况
进行选择。
将二进制编码的结果填写到空间中,当将空间划分为四块时候,编码的顺序
分别是左下角00,左上角01,右下脚10,右上角11,也就是类似于Z的曲线,当我
们递归的将各个块分解成更小的子块时,编码的顺序是自相似的(分形),每一
个子快也形成Z曲线,这种类型的曲线被称为Peano空间填充曲线。

三。举例说明
北京9个区域的GeoHash字符串,分别是WX4ER,WX4G2、WX4G3等等,
每一个字符串代表了某一矩形区域。这个矩形区域内所有的点(经纬度坐标)都共
享相同的GeoHash字符串,又比较容易做缓存。

实际应用:利用geo_Hash可以实现电单车点聚合效果

注意事项
由于GeoHash是将区域划分为一个个规则矩形,并对每个矩形进行编码,这样在查询附
近信息时会导致以下问题,比如红色的点是我们的位置,绿色的两个点分别是附近的两个
目标,但是在查询的时候会发现距离较远餐馆的GeoHash编码与我们一样(因为在同一个
GeoHash区域块上),而较近目标的GeoHash编码与我们不一致。

    这个问题往往产生在边界处。解决的思路很简单,我们查询时,除了使用定位点的

GeoHash8GeoHash编码进行匹配外,还使用周围8个区域的GeoHash编码,这样可以避免这个问题。

相关文章
|
20天前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
33 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
1天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
17天前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
38 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
17天前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
46 2
动态规划算法学习三:0-1背包问题
|
1天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明