`

geohash的原理实际是个四叉树/网格处理

阅读更多

看了下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是存储平面坐标点比较有效的办法。

分享到:
评论

相关推荐

    基于四叉树的图像网格划分

    总的来说,基于四叉树的图像网格划分是计算机视觉和图像处理中的一个重要工具。通过理解四叉树的数据结构及其在图像划分中的应用,我们可以更好地设计和优化相关算法,以解决复杂的问题。这个项目提供的代码和示例为...

    quad.rar_quad_四叉树_四叉树网格_四叉树;CFD_非结构网格

    四叉树(Quadtree)是一种数据结构,常用于地理信息系统、图像处理和计算机图形学等领域,而在计算流体力学(CFD)中,四叉树网格则是构建非结构化网格的一种有效方法。非结构化网格相比传统的结构化网格,具有更大...

    四叉树法网格划分的数据结构及算法设计.pdf

    四叉树法是一种广泛应用于平面网格划分的数据结构和算法。它的基本原理来源于计算几何造型中的空间离散...通过对四叉树数据结构和算法设计的研究,可以加深对空间离散技术的理解,并在实际应用中实现高效率的网格划分。

    如何找到周围8个区域的GeoHash编码

    以上就是关于“如何找到周围8个区域的GeoHash编码”的详细说明,包括GeoHash的基本原理、Java实现以及在实际应用中的用法。通过理解这些概念,你可以在Java项目中有效地处理和查询地理位置数据。

    四叉树_C++_四叉树_

    四叉树是一种特殊的树结构,它在计算机科学中主要用于图像处理、数据索引和地理信息系统等领域。...通过理解和掌握四叉树的原理与实现,我们可以解决各种复杂的问题,特别是在图像处理和地理信息系统等领域。

    geohash:一个解决计算附近距离的php类库

    `geohash`是一个非常实用的技术,它利用了空间数据索引和编码策略,使得在PHP中处理地理位置信息变得高效且简单。本文将深入探讨`geohash`的原理、应用以及如何在PHP中实现。 `geohash`是一种基于坐标的空间数据...

    四叉树 unity实现 源码

    四叉树是一种特殊的树结构,特别适用于处理二维或三维空间中的数据。在Unity游戏引擎中,四叉树常被用于优化空间数据索引和碰撞检测,以提高性能和效率。本资源提供了Unity2017版本下的四叉树实现源码,这对于开发者...

    nodejs geohash

    `ngeohash.bbox(geohash)`返回一个包含四个坐标点(西南角和东北角)的数组,这些点定义了Geohash的边界。 在实际应用中,例如开发一个基于位置服务的Web应用,Node.js和ngeohash库可以协同工作,高效地处理地理...

    C/OC_geohash

    Geohash算法主要基于Base32编码,它将地球表面划分为一系列的网格,然后对每个网格进行编码。通过递归地将每个网格分成相等的四部分(北、南、东、西),直到得到的网格足够小,可以接受一个Base32字符来表示。这样...

    四叉树编码

    四叉树编码是一种在计算机图形学、图像处理和数据存储领域广泛应用的数据结构和编码方法。四叉树是一种扩展自二叉树的数据结构,每个节点有四个子节点,分别代表四个象限:左上、右上、左下和右下。在四叉树编码中,...

    GIS原理课件4.8四叉树编码

    四叉树编码的主要思想是将图像或栅格数据分割成四个小区域,如果某个小区域的所有网格点具有相同的灰度或属性值,则不再分割,否则继续将该区域分割成四个小区域,直到每个小区域都具有相同的灰度或属性值为止。...

    python_geohash-0.8.5-cp312-cp312-win_amd64.whl.zip

    Python Geohash是一个用于处理地理坐标数据的Python库,它实现了地理位置编码和解码功能,主要基于Geohash算法。这个特定的版本是`0.8.5`,专为Python 3.12编译,并且适用于Windows操作系统,64位架构(amd64)。`...

    python_geohash-0.8.5-cp36-cp36m-win_amd64.whl.zip

    标题中的"python_geohash-0.8.5-cp36-cp36m-win_amd64.whl.zip"表明这是一个与Python相关的库,名为`geohash`,版本为0.8.5。它是一个适用于Python 3.6(cp36代表Python 3.6)且构建于Windows AMD64架构(win_amd64...

    encode_geohash.rar_geohash_geohash encode_matlab与geohash

    - **空间索引**:通过比较GeoHash字符串,可以快速判断两个位置是否在同一个网格内,或者它们之间的相对距离。 - **数据压缩**:相比于保存原始的经纬度坐标,GeoHash字符串占用的存储空间更小。 - **查询效率**:...

    python_geohash-0.8.5-cp311-cp311-win_amd64.whl.zip

    1. **GeoHash原理**:GeoHash基于格网编码原理,通过将地球表面划分为多个小网格,并用短字符串表示每个网格的位置,实现了对地理位置的高效编码和解码。这种编码方式可以方便地进行范围查询和附近位置搜索。 2. **...

    geohash经纬度转换包linux

    Geohash编码的过程通常涉及到将地球表面的经纬度网格化,然后递归地将每个网格区域分配一个二进制编码,最后将这些二进制编码转化为base32编码的字符串。 2. **解码(Decoding)**: 反向操作,将Geohash字符串解析...

    基于限制四叉树的大规模地形可视化及其实现.pdf

    《基于限制四叉树的大规模地形可视化及其实现》这篇文献深入探讨了在处理大规模地形数据时,如何利用限制四叉树实现高效、流畅的可视化技术。本文将详细阐述限制四叉树的基本概念,以及其在地形可视化中的应用,同时...

    基于四叉树算法绘制颜色填充等值线图

    ### 基于四叉树算法绘制颜色填充等值线图 #### 一、问题提出与需求分析 ##### 1. 问题及目标 - **问题**:如何使用四叉树算法来绘制颜色填充等值线图? - **目标**: - 利用四叉树的思想,根据给定的数据绘制...

    四叉树与Directx地形技术

    在地形渲染中,四叉树能够有效地将地形分割成多个较小的部分,并根据视点与地形的距离以及地形本身的特征(如起伏程度)来决定每个部分的渲染细节级别。这种方法不仅减少了不必要的计算,还提高了渲染速度。 **LOD...

Global site tag (gtag.js) - Google Analytics