青岛建站公司流程,seo百度刷排名,做网站需要哪些费用支出,深圳做网站比较好天涯一、Geohash 算法简介 GeoHash是空间索引的一种方式#xff0c;其基本原理是将地球理解为一个二维平面#xff0c;通过把二维的空间经纬度数据编码为一个字符串#xff0c;可以把平面递归分解成更小的子块#xff0c;每个子块在一定经纬度范围内拥有相同的编码。以GeoHash方…一、Geohash 算法简介 GeoHash是空间索引的一种方式其基本原理是将地球理解为一个二维平面通过把二维的空间经纬度数据编码为一个字符串可以把平面递归分解成更小的子块每个子块在一定经纬度范围内拥有相同的编码。以GeoHash方式建立空间索引可以提高对空间poi数据进行经纬度检索的效率。Geohash 属于空间填充曲线中的 Z 阶曲线Z-order curve的实际应用。 Geohash是一种地址编码它能把二维的经纬度编码成一维的字符串Geohash 就常常被用来作为唯一标识符。用在数据库里面可用 Geohash 来表示一个点。Geohash 这个公共前缀的特性就可以用来快速的进行邻近点的搜索。越接近的点通常和目标点的 Geohash 字符串公共前缀越长
1.Z曲线 上图就是 Z 阶曲线。生成它只需要把每个 Z 首尾相连即可。 Z 阶曲线同样可以扩展到三维空间。只要 Z 形状足够小并且足够密也能填满整个三维空间。Geohash算法 的理论基础就是基于 Z 曲线的生成原理。 2.Geohash基础 Geohash 能够提供任意精度的分段级别。一般分级从 1-12 级。 可以利用 Geohash 的字符串长短来决定要划分区域的大小。这个对应关系可以参考上面表格里面 cell 的宽和高。一旦选定 cell 的宽和高那么 Geohash 字符串的长度就确定下来了。这样我们就把地图分成了一个个的矩形区域了。 地图上虽然把区域划分好了但是还有一个问题没有解决那就是如何快速的查找一个点附近邻近的点和区域呢 Geohash 有一个和 Z 阶曲线相关的性质那就是一个点附近的地方(但不绝对) hash 字符串总是有公共前缀并且公共前缀的长度越长这两个点距离越近。 由于这个特性Geohash 就常常被用来作为唯一标识符。用在数据库里面可用 Geohash 来表示一个点。Geohash 这个公共前缀的特性就可以用来快速的进行邻近点的搜索。越接近的点通常和目标点的 Geohash 字符串公共前缀越长但是这不一定也有特殊情况下面举例会说明 3.Geohash 编码形式——base 32 和 base 36
①base 32 (十进制与字符对应关系) ②base 36 base 36 的版本对大小写敏感用了36个字符“23456789bBCdDFgGhHjJKlLMnNPqQrRtTVWX”。 二、Geohash 实际应用举例 以 base-32 为例。举个例子。假设需要查询距离美罗城最近的餐馆该如何查询
1.地图网格化编码规则 利用 geohash。通过查表我们选取字符串长度为6的矩形来网格化这张地图。经过查询美罗城的经纬度是[31.1932993, 121.43960190000007]。
①将经纬度转换为二进制 先处理纬度。地球的纬度区间是[-90,90]。把这个区间分为2部分即[-90,0)[0,90]。31.1932993位于(0,90]区间即右区间标记为1。然后继续把(0,90]区间二分分为[0,45)[45,90]31.1932993位于[0,45)区间即左区间标记为0。一直划分下去。 再处理经度一样的处理方式。地球经度区间是[-180,180] ②将经纬度的二进制编码合并 纬度产生的二进制是101011000101110经度产生的二进制是110101100101101按照偶数位放经度奇数位放纬度的规则重新组合经度和纬度的二进制串生成新的111001100111100000110011110110 ③将合并后的二进制数做Base32编码 最后一步就是把这个最终的字符串转换成字符对应需要查找 base-32 的表。11100 11001 11100 00011 00111 10110转换成十进制是 28 25 28 3 7 22查表编码得到最终结果wtw37q。
我们还可以把这个网格周围8个各自都计算出来。 从地图上可以看出这邻近的9个格子前缀都完全一致。都是wtw37。可以看到中间大格子的 Geohash 的值是 wtw37q那么它里面的所有小格子前缀都是 wtw37q。可以想象当 Geohash 字符串长度为5的时候Geohash 肯定就为 wtw37 了。
位于格子边界两侧的两点虽然十分接近但编码会完全不同。实际应用中可以同时搜索当前格子周围的8个格子即可解决这个问题。 2.Geohash和Z曲线的关系 x 轴就是纬度y轴就是经度。经度放偶数位纬度放奇数位就是这样而来的。 3.精度问题 如果递归的次数越大则生成的二进制编码越长因此生成的geohash编码越长位置越精确。 4.Geohash的意义 GeoHash用一个字符串表示经度和纬度两个坐标, 比直接用经纬度的高效很多而且使用者可以发布地址编码既能表明自己位于某位置附近又不至于暴露自己的精确坐标有助于隐私保护。 编码过程中通过二分范围匹配的方式来决定某个经纬坐标是编码为1还是0因此某些邻近坐标的编码是相同的因此GeoHash表示的并不是一个点而是一个矩形区域。GeoHash编码的前缀可以表示更大的区域。例如wm3vzg它的前缀wm3vz表示包含编码wm3vzg在内的更大范围。这个特性可以用于附近地点搜索。 如果把某个区域或整个地图上的地理位置都按照Geohash编码则会得到一个网格编码递归粒度越细网格的矩形区域越小geohash编码的长度越大则Geohash编码越精确。 5.邻近网格位置推算 根据Geohash的编码规则将经纬度分解到二进制结合地理常识中心网格在南北上下方向上体现为纬度的变化往北则维度的二进制加1往南则维度的二进制减1在东西左右方向上体现为经度的变化往东则经度的二进制加1往西则减1可以计算出上下左右四个网格经纬度的二进制编码再将加减得出的经纬度两两组合计算出左上、左下、右上和右下四个网格的经纬度二进制编码从而就可以根据Geohash的编码规则计算出周围八个网格的字符串。 三、Geohash 的优缺点 Geohash 的优点很明显它利用 Z 阶曲线进行编码。而 Z 阶曲线可以将二维或者多维空间里的所有点都转换成一维曲线。在数学上成为分形维。并且 Z 阶曲线还具有局部保序性。 Z 阶曲线通过交织点的坐标值的二进制表示来简单地计算多维度中的点的z值。一旦将数据被加到该排序中任何一维数据结构例如二叉搜索树B树跳跃表或具有低有效位被截断哈希表 都可以用来处理数据。通过 Z 阶曲线所得到的顺序可以等同地被描述为从四叉树的深度优先遍历得到的顺序。
这也是 Geohash 的另外一个优点搜索查找邻近点比较快。
Geohash 的缺点之一也来自 Z 阶曲线。Z 阶曲线有一个比较严重的问题虽然有局部保序性但是它也有突变性。在每个 Z 字母的拐角都有可能出现顺序的突变。 看上图中标注出来的蓝色的点点。每两个点虽然是相邻的但是距离相隔很远。看右下角的图两个数值邻近红色的点两者距离几乎达到了整个正方形的边长。两个数值邻近绿色的点也达到了正方形的一半的长度。
Geohash 的另外一个缺点是如果选择不好合适的网格大小判断邻近点可能会比较麻烦。
