看了下geohash的过程,原以为是一个新的索引过程,发现本质上是一个QuadTree。
不同点是,geohash仅保留了每一个四叉树节点的KEY,而不需要计算四叉树本身的索引。换句话说,如果我们建立一棵四叉树,建立过程如果为每一个节点都生产KEY,{00,01,10,11}表示4个节点。那么也就生产了一个geohash的KEY。
如同四叉树一样,
(0)每一个四叉树节点都是一个区域(网格),因此,geohash也是一个区域,四叉树的深度,对应geohash的精度。
(1)四叉树中访问当前节点的子节点是容易的,所以geohash可以通过KEY找到当前区域的子区域。
(2)四叉树访问一个节点的父节点是容易的,所以geohash也可以通过KEY的特点访问包含当前节点的区域的父节点区域。
(3)四叉树查询当前同一个父节点的另外3个兄弟节点是容易的,geohash可以找到其他3个相邻的区域。
(4)四叉树寻访<X,Y>中的周围一定区域的所有Items,是不容易的。同理,geohash要查找<X,Y>一个Items也是不容易的。
因为在(2)中,只能容易访问当前节点的兄弟节点,而不是所有周边节点。
四叉树一般是通过结合前面3条来逐层搜索。
geohash的优势:
个人觉得,对于不习惯建立四叉树索引、或者不手动写空间索引的人有优势外,如使用mysql或者其他数据库存储方便等。
顺便提下,大规模经纬度数据中的统计热点问题。
(0)如果是分布式,就用网格索引的KEY(可以看成是一个满四叉树的geohash的KEY),因为可以保证每台机器上不同数据,但都是同样的KEY结构。
(1)如果是单个文件,文件不太大就用四叉树索引;文件较大,用geohash;四叉树因为存储了大量的节点信息。如果还是太大,结合(0)方式,构建一个N*N叉树,每N*N个网格作为一组存放在一个文件中。
N一般选取,2,4,8
- 结果图
先留个坑,过几天填上
- 结论
无论使用什么样的hash方式,只要对二维或者多维数据进行hash算法,都不可避免的遇到邻接边问题。解决这个问题的办法,要么吧周边邻近的块搜索下,要么不用hash,而改用树。QuadTree是存储平面坐标点比较有效的办法。
相关推荐
发布的代码有详细的程序解析,能够实现基于四叉树对某图像进行网格划分的功能,划分网格的数量由自己决定。
四叉树网格是计算流体力学中常用的非结构化网格,本程序用Fortran语言编写
#资源达人分享计划#
如何找到周围8个区域的GeoHash编码, java版本的。
八毫克octree-mg库在四叉树/八叉树网格上实现了并行几何多重网格方法,可用于求解椭圆形PDE,例如Poissons方程。 所提供的求解器可以在采用四叉树/八叉树网格的现有自适应网格细化(AMR)框架中使用。 该代码被详细...
下载easyui后使用其中的css和js,从一个treegrid树形网格资源 往另一个空的树形网格拖放数据,支持添加子节点、删除、编辑、保存、取消编辑、刷新、更新数据等功能
多相五方程模型的2D笛卡尔四叉树自适应网格细化(AMR)。 此源代码是基于QTAdaptive 开发的,以编译此源代码,您需要将QTAdaptive和2D_CARFIVE下载到同一文件夹中。 笛卡尔自适应五方程模型 作者:VAN-DAT THANG ...
该算法采用自底向上的机制,对目标位置的Geohash编码进行字符串模糊查询来确定组成匿名区域的[k-1]个近邻,在扩大扫描区域时,对请求用户所在网格以及周边网格跨域扫描,然后再进行层级的递归,同时使用[Lmax]和[Lm...
RecyclerView控件三大布局(列表/网格/瀑布流)的实现代码,具体的代码解析和使用可参照我的博客文章《RecyclerView控件的实用指南》,网址:http://blog.csdn.net/zhengchu321/article/details/70155134,若有疑问...
* $hash //geohash_encode后的值 * 返回 array // Array * ( * [latitude] => 39.416916975752 * [longitude] => 100.92223992571 * [north] => 39.416917059571 * [east] => 100....
四叉树Python 在Python3中实现四叉树算法。
libsvm交叉验证与网格搜索(参数选择)
针对传统的尺度均一概率栅格地图表达法在大尺度未知环境下地图创建过程中海量数据存储和相关量计 算问题, 提出一类基于四叉树的栅格大小自适应地图创建算法. 利用四叉树理论, 根据地图不同区域环境障碍物密度 ...
网格的多分辨率层次结构存储为不重叠的固定大小网格的复合结构,这些结构作为叶子存储在四叉树或八叉树的森林中。 基于高度可扩展的网格划分库p4est() 提供了针对双曲线PDE的求解器,包括Clawpack 4.x,Clawpack ...
ProximityHash:接近度中的Geohash(可以选择使用进行压缩) Geohash是Gustavo Niemeyer发明的地理编码系统,已被置于公共领域。 它是一种分层的空间数据结构,可将空间细分为网格状的桶,这是所谓的Z阶曲线(通常...
基于多分辨率地形模型的四叉树构建过程,首先针对四叉树优化采用的3个判断标准———包围体剔除、背面剔除和屏幕投影误差分别进行相应的网格优化,然后在LOD地形中漫游时,随着视点移动而呈现出的不同细节程度的需要,...
针对mike21fm开发的辅助工具,可实现mike21fm网格地形前处理,比如工程开挖,筑坝等,可实现sms网格转换为mike网格,闭边界无需指定,智能自动判断,可读取dfsu结果文件,可将结果文件转换到sms中,利用sms显示,...
网格哈希网格给定一个边界框,流出哈希网格npm install geohash-grid -g用法geohash - grid 53.639554 - 113.654585 53.440018 - 113.349715 并且输出将是NDJSON像{"hash":"c3x25bw","row":145,"col":199}{"hash":...
网格是一致的,可以被视为四叉树网格的推广。 出于本研究的目的,我们将平面应变极限分析的主要兴趣限制在 von Mises 型材料上,但完全有可能将其扩展到范围广泛的其他固体力学问题和材料。 为了避免体积锁定,我们...
本篇文章主要介绍了JAVA实现空间索引编码——GeoHash的示例,如何从众多的位置信息中查找到离自己最近的位置,有兴趣的朋友可以了解一下