Geohash学习笔记

标签： 程序开发 GIS | 发表时间：2015-10-21 22:04 | 作者：标点符
出处：http://www.biaodianfu.com
什么是Geohash
Geohash是一种地址编码，它能把二维的经纬度编码成一维的字符串。比如，北海公园的编码是wx4g0ec1。
Geohash有以下几个特点：
  • Geohash用一个字符串表示经度和纬度两个坐标。在数据存储时可以简化为只为一列做索引。
  • Geohash表示的并不是一个点，而是一个矩形区域。使用者可以发布地址编码，既能表明自己大致位置，又不至于暴露自己的精确坐标，有助于隐私保护。
  • Geohash编码的前缀可以表示更大的区域。例如wx4g0ec1，它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索。
Geohash的算法
Geohash的最简单的解释就是：将一个经纬度信息，转换成一个可以排序，可以比较的字符串编码。
1、维度拆解
首先将纬度范围(-90, 90)平分成两个区间(-90,0)、(0, 90)，如果目标纬度位于前一个区间，则编码为0，否则编码为1。然后再将(0, 90)分成 (0, 45), (45, 90)两个区间， 以此类推，直到精度符合要求为止，得到纬度39.92324编码为1011 1000 1100 0111 1001。
lat
2、经度拆解
经度也用同样的算法，对(-180, 180)依次细分，得到116.3906的编码为1101 0010 1100 0100 0100。
lon
解码算法与编码算法相反，先进行base32解码，然后分离出经纬度，最后根据二进制编码对经纬度范围进行细分即可。
上文讲了GeoHash的计算步骤，仅仅说明是什么而没有说明为什么？为什么分别给经度和维度编码？为什么需要将经纬度两串编码交叉组合成一串编码？
geohash
如图所示，我们将二进制编码的结果填写到空间中，当将空间划分为四块时候，编码的顺序分别是左下角00，左上角01，右下脚10，右上角11，也就是类似于Z的曲线，当我们递归的将各个块分解成更小的子块时，编码的顺序是自相似的（分形），每一个子快也形成Z曲线，这种类型的曲线被称为Peano空间填充曲线。
peano
这种类型的空间填充曲线的优点是将二维空间转换成一维曲线（事实上是分形维），对大部分而言，编码相似的距离也相近， 但Peano空间填充曲线最大的缺点就是突变性，有些编码相邻但距离却相差很远，比如0111与1000，编码是相邻的，但距离相差很大。
除Peano空间填充曲线外，还有很多空间填充曲线，如图所示，其中效果公认较好是Hilbert空间填充曲线，相较于Peano曲线而言，Hilbert曲线没有较大的突变。为什么GeoHash不选择Hilbert空间填充曲线呢？可能是Peano曲线思路以及计算上比较简单吧，事实上，Peano曲线就是一种四叉树线性编码方式。
3、经纬度合并
接下来将经度和纬度的编码合并，奇数位是纬度，偶数位是经度，得到编码 11100 11101 00100 01111 00000 01101 01011 00001。最后，用0-9、b-z（去掉a, i, l, o）这32个字母进行base32编码，得到(39.92324, 116.3906)的编码为wx4g0ec1。
base32
Geohash的精度
Geohash算法的主要思想是对某一数字通过二分法进行无限逼近。显然的是，不可能让计算机执行无穷计算，加入执行N次计算，则x属于的区间长度为(b-a)/2N+1 ,以纬度计算为例，则为180/2N ，误差近似计算为:err= 180/2N+1 =90/2N ,如果N=20，则误差最大为：0.00009。但无论如何这样表明Geohash是一种近似算法。
Geohash长度对应的精度误差：
geohash1
由于GeoHash是将区域划分为一个个规则矩形，并对每个矩形进行编码，每个精度等级对应的规则矩形大小为：
geohash2
Geohash的应用点
geohash的最大用途就是附近地址搜索了。不过，从geohash的编码算法中可以看出它的一个缺点：位于格子边界两侧的两点，
虽然十分接近，但编码会完全不同。实际应用中，可以同时搜索当前格子周围的8个格子，即可解决这个问题。
参考资料：

相关 [geohash 学习 笔记] 推荐：

Geohash学习笔记

- - 标点符
Geohash是一种地址编码，它能把二维的经纬度编码成一维的字符串. 比如，北海公园的编码是wx4g0ec1. Geohash有以下几个特点：. Geohash用一个字符串表示经度和纬度两个坐标. 在数据存储时可以简化为只为一列做索引. Geohash表示的并不是一个点，而是一个矩形区域. 使用者可以发布地址编码，既能表明自己大致位置，又不至于暴露自己的精确坐标，有助于隐私保护.

[转]GeoHash原理分析

- - tenfyguo的技术专栏
机机是个好动又好学的孩子，平日里就喜欢拿着手机地图点点按按来查询一些好玩的东西. 某一天机机到北海公园游玩，肚肚饿了，于是乎打开手机地图，搜索北海公园附近的餐馆，并选了其中一家用餐. 饭饱之后机机开始反思了，地图后台如何根据自己所在位置查询来查询附近餐馆的呢. 苦思冥想了半天，机机想出了个方法：计算所在位置P与北京所有餐馆的距离，然后返回距离<=1000米的餐馆.

shell 学习笔记

- tiger - 游戏人生
将脚本目录加到 PATH 中. 在 dash 中如何进行字符串替换. 将 rst 格式文档转换为 blog 可用的 html 代码. shell 脚本虽然不是非常复杂的程序, 但对于首次接触的我来讲, 多少还是有些忌惮. 不过, 接触任何新事物都需要勇敢面对, 逐步树立信心. 我是冲着把脚本写好去的, 所以, 我的目标是能够写出友好, 健壮, 优美的脚本..

OAuth学习笔记

- 宋大妈 - FeedzShare
来自: 标点符 - FeedzShare  . 发布时间:2011年08月29日,  已有 2 人推荐. OAuth（开放授权）是一个开放标准，允许用户让第三方应用访问该用户在某一网站上存储的私密的资源（如照片，视频，联系人列表），而无需将用户名和密码提供给第三方应用. OAuth允许用户提供一个令牌，而不是用户名和密码来访问他们存放在特定服务提供者的数据.

Vim学习笔记

- 临池学书 - C++博客-首页原创精华区
最近在学习Vimtutor中的相关内容，Vim的使用博大精深，很多命令一旦不使用就会忘记，下面把其中的没有使用到的相关命令做一个简单的总结，供以后复习使用. 至于常见的保存，插入等等命令，则不予记录，在以后的使用中加深练习即可. To change until the end of a word, type  ce (ce + 修正的单词).

OAuth学习笔记

- jiaosq - 标点符
OAuth（开放授权）是一个开放标准，允许用户让第三方应用访问该用户在某一网站上存储的私密的资源（如照片，视频，联系人列表），而无需将用户名和密码提供给第三方应用. OAuth允许用户提供一个令牌，而不是用户名和密码来访问他们存放在特定服务提供者的数据. 每一个令牌授权一个特定的网站（例如，视频编辑网站)在特定的时段（例如，接下来的2小时内）内访问特定的资源（例如仅仅是某一相册中的视频）.

HTML学习笔记

- - CSDN博客推荐文章
超文本标记语言（ 英文：HyperText Markup Language，HTML）是为“ 网页创建和其它可在 网页浏览器中看到的信息”设计的一种 标记语言. HTML被用来结构化信息——例如标题、段落和列表等等  点击打开链接. w3schools  点击打开链接 {语法大全，超赞.

jQuery学习笔记

- - ITeye博客
什么是jQuery,它能为我们做什么. jQuery是一个javascript类库或称之为javascript框架. 无需刷新页面从服务器获取信息. 简化常见的javascript任务. 为什么会如此流行或说得到大量用户群的支持：. 多重操作集于一行（避免使用临时变量或不必要的重复代码）. jQuery利用了CSS选择符的能力，在DOM中快捷而轻松地获取元素或元素集合.

JdbcTemplate学习笔记

- - SQL - 编程语言 - ITeye博客
1、使用JdbcTemplate的execute()方法执行SQL语句. 2、如果是UPDATE或INSERT,用update()方法.    JdbcTemplate将我们使用的JDBC的流程封装起来，包括了异常的捕捉、SQL的执行、查询结果的转换等等. spring大量使用Template Method模式来封装固定流程的动作，XXXTemplate等类别都是基于这种方式的实现.

Disruptor 学习笔记

- - 开源软件 - ITeye博客
Disruptor 是一个高性能异步处理框架，也可以认为是一个消息框架，它实现了观察者模式. Disruptor 比传统的基于锁的消息框架的优势在于：它是无锁的、CPU友好；它不会清除缓存中的数据，只会覆盖，降低了垃圾回收机制启动的频率. Disruptor 为什么快. 通过内存屏障和原子性的CAS操作替换锁.