geohash、google s2、uber h3三种格网系统

三种算法格子的区别：

三种格子系统中，geohash用了矩形+正方形格子的方式（由于base32编码，中间的一级会变矩形），google s2采用了正方形格子，uber h3采用了六边形格子。同样uber h3对多级覆盖也做了一些优化，每层的格子旋转了19.1°，以近似进行覆盖下一级格子。

Geohash

Geohash是一种地址编码，它能把二维的经纬度编码成一维的字符串，Geohash 就常常被用来作为唯一标识符。用在数据库里面可用 Geohash 来表示一个点。Geohash 这个公共前缀的特性就可以用来快速的进行邻近点的搜索。越接近的点通常和目标点的 Geohash 字符串公共前缀越长

Geohash有以下几个特点：

• Geohash用一个字符串表示经度和纬度两个坐标。在数据存储时可以简化为只为一列做索引。
• Geohash表示的并不是一个点，而是一个矩形区域。使用者可以发布地址编码，既能表明自己大致位置，又不至于暴露自己的精确坐标，有助于隐私保护。
• Geohash编码的前缀可以表示更大的区域。例如wx4g0ec1，它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索。

Geohash的应用点：

geohash的最大用途就是附近地址搜索了。不过，从geohash的编码算法中可以看出它的一个缺点：位于格子边界两侧的两点，

虽然十分接近，但编码会完全不同。实际应用中，可以同时搜索当前格子周围的8个格子，即可解决这个问题。

由于GeoHash是将区域划分为一个个规则矩形，并对每个矩形进行编码，每个精度等级对应的规则矩形大小为：

Google S2算法

S2其实是来自几何数学中的一个数学符号 S²，它表示的是单位球。S2 这个库其实是被设计用来解决球面上各种几何问题的。

S2 与 Geohash 对比

• Geohash 有12级，从5000km 到7cm。中间每一级的变化比较大。有时候可能选择上一级会大很多，选择下一级又会小一些。这种情况选择多长的 Geohash 字符串就比较难选。选择不好，每次判断可能就还需要取出周围的8个格子再次进行判断。S2 有30级，从 0.7cm² 到 85,000,000km² 。中间每一级的变化都比较平缓，接近于4次方的曲线。所以选择精度不会出现 Geohash 选择困难的问题。
• Geohash 需要 12 bytes 存储。S2 的存储只需要一个 uint64 即可存下。
• S2 库里面不仅仅有地理编码，还有其他很多几何计算相关的库。地理编码只是其中的一小部分。本文没有介绍到的 S2 的实现还有很多很多，各种向量计算，面积计算，多边形覆盖，距离问题，球面球体上的问题，它都有实现。

S2 主要能用在以下 8 个地方：

• 涉及到角度，间隔，纬度经度点，单位矢量等的表示，以及对这些类型的各种操作。
• 单位球体上的几何形状，如球冠（“圆盘”），纬度 - 经度矩形，折线和多边形。
• 支持点，折线和多边形的任意集合的强大的构造操作（例如联合）和布尔谓词（例如，包含）。
• 对点，折线和多边形的集合进行快速的内存索引。
• 针对测量距离和查找附近物体的算法。
• 用于捕捉和简化几何的稳健算法（该算法具有精度和拓扑保证）。
• 用于测试几何对象之间关系的有效且精确的数学谓词的集合。
• 支持空间索引，包括将区域近似为离散“S2单元”的集合。此功能可以轻松构建大型分布式空间索引。
• 最后一点空间索引相信在工业生产中使用的非常广泛。
• S2 目前应用比较多，用在和地图相关业务上更多。Google Map 就直接大量使用了 S2 ，速度有多快读者可以自己体验体验。Uber 在搜寻最近的出租车也是用的 S2 算法进行计算的。场景的例子就是本篇文章引语里面提到的场景。滴滴应该也有相关的应用，也许有更加优秀的解法。现在很火的共享单车也会用到这些空间索引算法。
• 最后就是外卖行业和地图关联也很密切。美团和饿了么相信也在这方面有很多应用，具体哪里用到了，就请读者自己想象吧。
• 当然 S2 也有不适合的使用场景：
• 平面几何问题（有许多精细的现有平面几何图库可供选择）。
• 转换常见的 to/from GIS格式（要阅读这种格式，请使用OGR等外部库）。

不同级别可以代表的网格的面积：

Uber H3

H3是一个针对地球的空间划分和空间索引系统。

H3地理空间索引系统是一个离散的全局网格系统，该系统由具有层次结构索引的球形多精度六边形拼贴组成。在球形外接二十面体的平面上创建六边形网格系统，然后使用反面为中心的多面体结构投影将网格单元投影到球体的表面

H3的主要应用是什么？

• 优化乘车价格和调度(动态定价)
• 地图空间数据可视化和挖掘
• 用于整个市场的分析和优化

为什么用H3？

GEOHASH存在一些不足

• 不同精度下网格的形状不一且精度的变化幅度时小时大
• 在不同维度的地区会出现地理单元单位面积差异较大的情况
• 存在8邻域到中心网格的距离不相等问题

 

详细的精度数据如下：

唯一索引数就是在整个地球中当前解析度中有多少个格子

 

参考资料

• 空间索引之GeoHash
  https://www.biaodianfu.com/geohash.html
• 空间索引之 Google S2
  https://www.biaodianfu.com/google-s2.html
• 高效的多维空间点索引算法 — Geohash 和 Google S2
  https://halfrost.com/go_spatial_search/#toc-25
• 空间索引之Uber-h3

       https://www.biaodianfu.com/uber-h3.html