Uber H3 index 地图索引思考

H3 是 uber 设计的六边形空间索引，go 语言操作包是 h3-go，可以通过经纬度获取所在的 h3 六边形边界，每个经纬度对应的六边形都是确定的，每个六边形唯一对应了一个 h3index。在业务开发中，我们可以通过 h3index 来对地理空间中的对象做聚合，本质还是将经纬度查询转换成了 h3index 的查询。

维度

不同维度的 h3index 表示不同大小的地理空间，我们可以查看官方介绍来了解对应关系。h3 有 16 个维度，维度越高，表示的面积越小，也就越是精确。下图的对应关系，表示不同维度的h3index 表示地球的组成。

拿维度 15 来说，已经是 h3 能表示的最小单元了。用这个维度来表示地球的话，需要存储 569,707,381,193,162 个该维度的 h3index 索引。后面又列举了其中六边形（hexagon）和五边形（pentagon）的组成个数。为什么组成中还会有五变形呢？ 我们应该从设计的根源上去探索解释。

使用 h3-go 包，我们通过指定经纬度、以及维度就可以获取到对应的 h3index 索引。还可以通过 h3index 获取所在六边形的组成点。下面代码中 FromGeo 就返回了对应的 h3index。

geo := GeoCoord{Latitude:  37.775938728915946,Longitude: -122.41795063018799,
}
resolution := 9
fmt.Printf("%#x\n", FromGeo(geo, resolution))

想比较 h3index 能表示的最小单元格个数而言，我们最关心的还是单元格所能表示的面积大小，不同维度的 h3index 究竟能表示多大的范围。

H3 设计

将真实世界的 3 维地理空间映射到 2 维的网格体系，是每个地图索引都需要面对的问题。H3 通过球心投影的方式将地球抽象成一个空间正20 面体，但地球本身也不是极致的圆形，抽象肯定会牺牲一部分准确性。

正20面体的每个面都是一个三角形平面，抽象到地图上的话，每个平面应该都是二维的平面。然后就变成了一个圆形的正20面体，就正好可以接受地图的投影。而且，如果把正 20 面体的每个面进行编码，我们可以通过选择正 20 面体，将合适的面对应到合适的地理区域上。

正 20 面体展开到二维平面，就是地球的投影，下面就是其中的一种展开方式。因为有陆地和海洋的区别，而我们要分析的地理数据基本都是在陆地上的。所以，正 20 面体通过合理的转动，可以将它的顶点都落在海洋的区域。为什么要特别处理这些顶点数据呢？

H3网格索引没有直接利用正 20 面体，而是在每个面的基础上继续做了网格拆分。为什么最终选择使用正六边形作为拆分的单元呢，还有没有别的多边形可以选择呢？其实还可以有三角形和正方形，GeoHash 采用的就是正方面的网格，那么正方形网格和正六边形有什么区别吗？

假设一个 n 面体，多面体的内角和计算公式为 (n-2)*180，假设 m 个正多边形在任意顶点出拼接形成一个 360 度才能形成网格，最终计算的表达式：(n-2)*180/n*m=360。如果 n 表示三角形，就需要有 6 个面拼接；如果 n 是正方形，就需要 4 个面拼接，如果 n 是六边形，就需要 3 个面拼接。

如果按照三角形或者四边形的拆分方式，某一个网格单元和临边的网格单元的中心距离是不相同的，如上图。但采用正六边形，网格单元和临边的其它网格单元是相同的。那么，在网格体系中，我们如何获取某个网格单元周边的网格呢？

H3 网格独立于现实中的区域，真实世界的区域边界往往会发生一些变化，区域的边界形态各异，经常还会发生变动调整，如果保持现实地理的区域跟踪，保证区域边界数据动态更新难度可想而知。试想一下，如果我们根据北京的每个区、每个街道进行数据统计，复杂性是非常大的。

而 H3 是在地球基础上的网格系统，它不用关心现实的街道、区域边界变化，无论现实中的地域如何变化，H3 都不会发生变化，也就是将地图上的某一个区域固定化了。如果要统计某个区域的维度信息，只需要先获取该区域的所有 H3 网格，汇总所有网格的信息就可以了。


在 0 级索引下，每个面包含了 10 个单元，如上图，其中边界线上的一些单元会被多个平面共同包含，这个面总共包含了 5.5 个六边形和 3 个三角形。上文提到的，正20面体所包含的 110 个六边形和 12 个五边形就是这么计算的出来的。正20面体包含有 20 个面、30条边、12 个顶点，其中的 12 个顶点就正好对应了这 12 个五边形。

上图形象的描述了，2个等级 H3 网格的大小关系，高级别的 H3 网格大概需要 7 个接近一个低级别的网格，两个级别之间不是完全的包含关系。

参考文章：

1. Uber’s Hexagonal Hierarchical Spatial Index
2. h3geo文档