【第九章 空间大数据】H3编码原理

GeoHash的原理就是按照区域，把经纬度进行编码，按照不同的网格精度，变成不同位数的编码，在同一区域中的点位编码相同。

问题1：不同精度下网格的形状不一（长方形和正方形）且精度的变化幅度时小时大

问题2：不同纬度地区会出现地理单元单位面积差异较大的情况

问题3：存在8邻域到中心网格的距离不相等的问题

六边形网格索引

H3是一种基于网格的空间索引，但跟普通的矩形网格索引不同的是，他的每一个网格都是正六边形。为啥要选正六边形呢，因为在基于网格的空间索引中，使用的多边形的边数越多，则一个网格越近似圆形，做缓冲区查询、kNN查询什么的也就越方便。而做网格索引又要求空间能够被网格铺满，不能有缝隙。根据初中数学知识，我们知道一个多边形的内角和公式为：

假设正x多边形，y个顶点相接：360 / y = ((x-2)*180) / x

这个等式只有三组整数解：x=3,y=6；x=4,y=4；x=6,y=3。

因此，能够做网格空间索引的形状只有三角形、矩形和六边形，而六边形因为边数最多，最接近圆，所以理论上来说在某些场景下是最优的选择。

上图展示了三种网格到其相邻网格的距离，六边形网格与周围网格的距离有且仅有一个，而四边形存在两类距离，三角形有三类距离。所以，H3就使用六边形作为网格索引的基本单元，实现空间索引。

无变形的投影

全球网格系统通常至少需要两件事：地图投影和放置在地图上的网格。从地球上的三维位置到地图上的二维点需要地图投影 然后将网格覆盖在地图上，形成一个全球网格系统。在GIS领域中，对空间填充曲线熟悉的同学应该知道，不论是GeoHash, Z2或者Hilbert，虽然看起来都是将空间按照经纬度分割成了一个个大小相等的网格，但实际上这些网格的实际面积并不相等。对于靠近极地的网格，虽然经纬度的间隔没变，但由于地球的曲率，这些网格的实际面积远小于靠近赤道的网格。

这种实际面积不相等的网格索引可能会造成一个问题，那就是由于网格大小不一致导致网格内数据量不一致，造成热网格和冷网格。于是，H3干脆摒弃传统的地图投影，直接在地球上铺满六边形。

H3 的前身其实是 DDGS(Discrete global grid systems) 中的 ISEA3H，其原理是把无限的不规则但体积相等的六棱柱从二十面体中心延伸，这样任何半径的球体都会穿过棱镜形成相等的面积cell，基于该标准使得每一个地理单元的面积大小就可以保证几乎相同。然而原生的 ISEA3H 方案在任意级别中都存在12个五边形，H3 的主要改进是通过坐标系的调整将其中的五边形都转移到水域上，这样就不影响大多数业务的开展。

H3实现的方法是：将地球当作一个二十面体，这个二十面体的每一个面都是球面三角形，有12个顶点，称为球形二十面体（spherical icosahedron），在这个球形十二面体的每个面上都有相同排列方式的六边形。由于这个球形二十面体的12个顶点每一个都在地球上的水里，可以保证对于每个面做处理时不会遇到边界的edge case，因为Uber还没有轮船快艇业务，只需要保证在陆地上H3好使就行。这个球形二十面体的示意图见图。

在第0层，这个球形二十面体的每一个面长这样：

可以看到，在一个球面三角形的顶角处有个小三角形，这个小三角形就是H3的一种edge case：在二十面体的顶点处，有五个面交于这个顶点，每个面在这个顶点处都有一个小三角形，所以这些小三角形会形成一个五边形。也就是说，H3并不能保证每个空间单元都是六边形，在一些地方还是会存在五边形，但是这样做也不会造成很大影响，因为根据球形二十面体每个顶点都在水里的特性，这种五边形只会出现在水域周围，不会对Uber的打车和外卖业务造成很大的影响。

因为不可能用六边形完全平铺球体/二十面体，二十面体六边形网格系统在每个分辨率下都必须恰好包含12个五边形，每个五边形的中心为二十面体顶点。

根据这样的索引特性，H3规定在索引的第0层，每个面和上图一样，每个面上有5.5个六边形和3/5个五边形，即第0层一共有110个六边形和12个五边形。H3将这110个六边形称为基网格（base cells）。H3最高可以到15层，也就是说H3有16个层级的空间索引粒度，在粒度最细的第15层中，平均每个网格的大小为0.9平方米，平均边长为0.509713米。在往下一层划分时，每个父网格对应7个子网格，父子网格之间的对应关系是这样的：

可以看到，父子网格之间并没有严密的对齐，父网格和其所对应的7个子网格之间会有一点差异，这种差异也导致了H3并不能表现出很好的层级关系。

详细的精度数据如下：

正六边形格网系统自然具备三条夹角为120度的坐标轴，这个坐标成为ijk坐标系统。如下图所示，IJK坐标使用三维数组进行表达：

H3在二十面体的每个面中心构建ijk坐标系，将基础面的编号和ijk坐标的组合表达为FaceIJK坐标系。每个层级的格网相对于上一个层级的格网都旋转了19.1度，旋转方向在逆时针和顺时针之间交替，所以在所有层级中，六边形的排列方式只有两种类型，称为Class II和Class III。在这两种类型的排列方式中，IJK坐标系的三个轴的方向不太一样，0层使用ClassII，逐层摇摆，交替使用。

那么对于一个面上所有层级的所有六边形，都使用FaceIJK坐标系编码，再加上面的唯一标识符可不可以？答案是可以，但没必要，因为如果这样做，H3编码会更加表示不了层级之间的关系。H3为了突出层级之间的关联性，使用了一种方法：每个六边形都包含其父六边形的坐标。这样只需要规定好每个网格的子网格坐标的计算方法，对于子网格，只需在父网格的坐标后面追加子网格的坐标即可。这样一来，只需关注一个网格的7个子网格如何计算坐标，所有层级的每个网格的坐标都可以递归得到，这7个网格坐标的计算方法见图，为了表述方便，称之为IJK七网格坐标系，五边形拆分中废弃下标1。

一般情况下，H3采用格网面的编码为索引模式，如下图所示：

H3还提供了一种叫做网格有向边（directed edges of grid cells）的东西，格网边的编码为索引模式，其目的是为了网格能够快速地找到其某个邻网格。这种网格有向边分为单向网格有向边和双向网格有向边，比如说，对于两个相邻网格A和B，其相交的边是E，如果E是一条由A->B的单向边，那么只能通过A快速找到邻居B，B不能快速找到邻居A；而如果E是一条双向边，那么A可以快速地找到B，B也可以快速地找到A。

同时，H3也提供3个网格面共享的顶点编码的索引模式，H3顶点被任意指定三个相邻格网单元中的一个作为其“所有者”，用于计算顶点的规范索引和坐标。

H3的编码最多占63个比特位，可以用64位的整型来表示，第一位为保留位取0，其余63位结构如下所示：