是否可以将H3索引结构映射为从0开始递增的整数？

Question

我在理解H3索引文档中的所有信息时遇到一些困难。对于那些刚接触 H3 的人来说，它是 Uber 最近发布的“六角形分层地理空间索引系统”。这是这个问题的关键信息：

H3细胞指数

H3 单元索引（模式 1）表示特定分辨率下 H3 网格系统中的单元（六边形或五边形）。 H3 Cell索引的组成部分按顺序打包成64位整数，最高位在前，如下：

• 保留 1 位并设置为 0，
• 4位指示H3 Cell索引模式，
• 保留3位并设置为0，
• 4位表示单元分辨率0-15，
• 7位表示基本单元0-121，
• 3 位用于指示从分辨率 1 到单元分辨率的每个后续数字 0-6（总共 45 位为分辨率 1-15 保留）

每个未使用的数字的三位设置为 7。

我不确定“指示基本单元格0-121”是什么意思，或者下一行“指示每个后续数字0-6”...

问题的第一部分（可能会帮助我自己弄清楚）是最后两个项目符号的含义。但主要问题是，是否可以仅基于位操作（即不使用哈希表或某种映射）将递增整数（从 0 开始）映射到单个分辨率级别内的每个单元格？我不太清楚，并且不知道最后两行，如果可能的话，我还没有看到这种方法。

Answer 1

更新

下面描述的功能现已在核心库中提供为

cellToChildPos

及其推论

childPosToCell

。

原答案

位布局的细分可能会有所帮助（在理解索引结构方面）。

• 有122个基本单元。网格中的每个单元格要么是这些基本单元格之一，要么是这些基本单元格之一的后代，因此每个索引都包含它所源自的基本单元格。
• 索引的其余部分是分层的，从基本单元向下走。本质上是一个类似“Base cell 27 child 2 child 0 child 3...”的地址。

可以纯粹通过位操作来完成您所描述的操作，但它需要对 H3 索引系统有相当多的了解。我以前做过这个，但代码目前是专有的，我不能在这里分享:(。与很多 H3 代码一样，五边形是最难的部分。

解决方案看起来像这样：

• 确定五边形和非五边形基础细胞所需分辨率

  r

  下的细胞计数。六边形单元有

  7^r

  子级，五边形有

  1 + 5 * (7^r - 1) / 6

  子级（您可以使用

  maxH3ChildrenSize

  来实现此目的，但无论如何您都需要知道它）。
• 您需要知道五边形基本单元数。这些是

  4, 14, 24, 38, 49, 58, 63, 72, 83, 97, 107, 117

对于给定的数字

n

：

• 从“空”索引开始，

  8ffffffffffffff

  。将分辨率位设置为

  r

  。
• 确定基本单元

  n

  所在位置以及基本单元偏移量(

  numPrecedingHexBaseCells * hexBaseSize + numPrecedingPentBaseCells * pentBaseSize

  )。
• 设置索引中的基本单元位。
• 从

  n

  中减去偏移量。这是您的子偏移量（即基本单元子子列表中的单元格的偏移量）。
• 使用子偏移量计算出 res 1、res 2、...res

  r

  的索引号。我无法在这里轻松地演练此逻辑，但您应该能够从上面计算子计数的公式中导出它（例如，在 res 1 处，十六进制基本单元有 7 个子项。在 res 2 处，它有49 - 首先找出 res 1 组

  n

  与

  n % 7

  属于哪个组，然后找出 res 2 编号，依此类推）。

这一切都非常复杂；我们计划将其添加到库中，但这至少需要几个月的时间。如果您只需要一个资源中所有单元格的流式列表，并且性能不是一个强要求，您可以使用 DFS 方法来代替 - 对于每个基本单元格，查找所有子单元格，然后查找位于该位置的一个子单元格的所有子单元格下一个分辨率，然后是下一个分辨率的一个子级，依此类推，直到达到所需的分辨率。这只需要一次将

7 * r

个细胞保留在内存中。