Uber-H3索引系统

Posted on Edited on In Views:

h3_level_0

Uber H3是Uber实现的一个基于正六边形，分层空间索引系统。

H3：

  • 功能-世界分割成正六边形的网格
  • 本质是一个分层网格系统
  • 支持全球，把世界划分为平米级的网格

使用正二十面体投影

h3选择以正二十面体做为投影，通过把地球坐标映射到正二十面体的20个面上，然后再针对每个面做进一步的切分。正二十面体如下图所示：
正二十面体 google_h3_20

正二十面体每个面都是一个等边三角形，映射之后，在地球这一球体上的映射如上图右所示。为方便理解，动态git图如下所示：

img

以上，可以注意到正二十面体，一共有12个顶点，每个顶点都是一个凸起，为了更好的模拟球面，可以对这个12个顶点进行截角处理，这样每个角被截后，就变成了一个正五边形。因此，地球被映射后，其实变成了20个正六边形+12个正五边形构成的近似球体。如下图所示，其实我们日常生活中常见到的足球正是这种形状的。

足球

使用正六边形做网格

在地球被正二十面体，投影到20个面之后，就考虑每个面怎么做网格切分的问题。H3使用的是正六边形做层次网格。下面来看正三角形如何做六边形切分。

img

h3以上图这种形式进行，正六边形切分，专业术语称为(aperture=4)。每个面有4个完整的正六边形，同时还有3个不完整的正六边形。通过这个单面的分析，我们可以计算出，第0层，地球可以被切分为5.5X20=110个正六边形，然后再加上12个(共12个顶点)正五边形，一共122个网格。

需要注意的是，有些网格是跨越多个面的，同时有正五边形的存在。正五边形的存在会对整个网格的切分有一定的影响，如何消除正五边形的影响呢。

首先，需要明确的是随着正六边形不断的切分，正五边形的个数始终都是12个，同时这个正五边形的面积也是不断的减小，直到变成一个足够小的面积。

另外，可以通偏移，把12个顶点五边形放置到大海中(R. Buckminster Fuller提出的方案，把其中一个顶点放在11.25°E, 58.2825°N)，从而避免对实际的陆地业务产生影响。

h3_level_0

上图展示了，h3网格切分，左侧是level 0，右侧是level 1。可以很清楚的看到五边形越来越小，并且12个顶点都被巧妙的分布在了大海之上, 避免对实际的业务产生影响(轮船、快艇实际上可能受到影响)。

网格坐标系

关于如何标识一个网格，怎么定位呢？

H3使用了一种称为CoordIJK坐标系作为定位系统。

img

使用这种(i,j,k)三元组坐标，来为每个六边形网格编号。可以注意到两个坐标系之间的夹角是120°。比较类似于三维坐标系，不过这个是在二维平面上的。

H3使用FaceIJK坐标系，来表示二十面体不同面上的坐标。它是由面的编号(0~19)和对应的CoordIJK坐标构成。

随着网格的不断细分，ijk坐标系是有一定的偏转的，大概是19.1°。不过并不是一直往一个方向进行偏转，而是不断的左右偏转的。实际上不同的层，只有2种类型：

img

这里的Class II和Class III就是这2种类型，名字是R. Buckminster Fuller定义的专业术语。当然并不存在所谓的Class I，Class IV. 这里只是一种名字而已。针对base cell, 也就是0层的网格，他的类型就是Class II。

Hex2d坐标，是一个关联CoordIJK的笛卡尔坐标系。Hex2d的坐标原点与CoordIJK一样，x轴与与CoordIJK的I轴是对齐一致的。单位距离1.0的大小是CoordIJK两个相邻网格中心点之间的距离。

Hex2d在代码内是使用Vec2d来表示的。

Local IJ坐标，是用来摆脱不同面或者不同base cell限制的一个概念。这个坐标只有2个夹角为120°的轴，坐标原点也是和H3 Index一样。

Local IJ坐标只有在同一原点坐标下才具有可比性；Local IJ坐标，只在原点附近是有效的；Local IJ坐标有可能由于五边形的存在而导致的失真。同一个索引有可能有多个Local IJ坐标，原点也可能不是(0，0)。

LocalIJ坐标在代码内使用CoordIJ和一个关联的原始H3Index表示。

H3 Index 计算

H3为每一个网格生成一个唯一的标识。每层(resolution)的网格，都是从第0层计算出的基础网格编码(cell number)开始的。 基础网格编码是固定下来的的（0121），其余层次的坐标都是从这个基础网格编码来定位的。子网格的06分布，如下图所示：

正六边形切分

从上可以看出，其实octal就是通过3bit的ijk坐标来算出来的。

由于有12个五边形，五边形是细分成6个子网格，并不是7个。所以直接把编号为1的网格给去掉了。

H3Index是一个64位的整形来表示的。它有3种类型：

  • 1代表六边形网格
  • 2 代表单向边(六边形A—>六边形B)
  • 3 代表双向边(六边形A<—>六边形B)

H3Index实际上只使用了64位的低63位。具体格式如下图所示：

H3Index格式

需要注意的是，如果Resolution没有到15层的话，那么置对应bit为全1，也就是7(111)，标志没有使用到。

比如83001dfffffffff, 对应的二进制为：

1
2
3
4
5
0 0001 000 0011 0000000 000 011 101
                        111 111 111
                        111 111 111
                        111 111 111
                        111 111 111

所以，可以解读如下：

index mode=1索引的是正六边形类型；

Resolution层数=3；

Base Cell=0；

Resolution1的网格编号是0；

Resolution2的网格编号是3；

Resolution3的网格编号是5。

其余为是1，代表没有那么resolution。

H3 Resolution 范围误差

H3 Resolution 平均六边形面积 (平方千米) 平均六边形边 (千米) Number of unique indexes
0 4,250,546.8477000 1,107.712591000 122
1 607,220.9782429 418.676005500 842
2 86,745.8540347 158.244655800 5,882
3 12,392.2648621 59.810857940 41,162
4 1,770.3235517 22.606379400 288,122
5 252.9033645 8.544408276 2,016,842
6 36.1290521 3.229482772 14,117,882
7 5.1612932 1.220629759 98,825,162
8 0.7373276 0.461354684 691,776,122
9 0.1053325 0.174375668 4,842,432,842
10 0.0150475 0.065907807 33,897,029,882
11 0.0021496 0.024910561 237,279,209,162
12 0.0003071 0.009415526 1,660,954,464,122
13 0.0000439 0.003559893 11,626,681,248,842
14 0.0000063 0.001348575 81,386,768,741,882
15 0.0000009 0.000509713 569,707,381,193,162

从上表可以知道，在Resolution=15的时候，平均面积已经在0.9平方米，边长也为0.5米了，完全满足常见的网格需求。

参考文档：

https://uber.github.io/h3/#/documentation/overview/introduction