Uber-H3索引系统

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