CODEWITHSUNDEEP
bit-manipulationh3
Lance Pollard
Lance Pollard

Reputation: 79268

Is it possible to map the H3 indexing structure to an incrementing integer start from 0?

I am having some trouble understanding all the info in the H3 indexing docs. For those who are new to H3, it is a "Hexagonal hierarchical geospatial indexing system" recently released from Uber. Here is the key bit of info for this question:

H3 Cell Index​

An H3 Cell index (mode 1) represents a cell (hexagon or pentagon) in the H3 grid system at a particular resolution. The components of the H3 Cell index are packed into a 64-bit integer in order, highest bit first, as follows:

  • 1 bit reserved and set to 0,
  • 4 bits to indicate the H3 Cell index mode,
  • 3 bits reserved and set to 0,
  • 4 bits to indicate the cell resolution 0-15,
  • 7 bits to indicate the base cell 0-121,
  • 3 bits to indicate each subsequent digit 0-6 from resolution 1 up to the resolution of the cell (45 bits total are reserved for resolutions 1-15)

The three bits for each unused digit are set to 7.

I'm not sure what "indicate the base cell 0-121" means, or the next line "indicate each subsequent digit 0-6" ...

First part of the question (that may help me figure it out on my own) is what those two last bullets mean. But the main question is, is it possible to map an incrementing integer (starting from 0) to every cell within a single resolution level, just based on bit manipulation (i.e. not by using a hash table or map of some sort)? I can't quite tell, and not knowing these last two lines I'm not seeing the approach if it's possible yet.

Upvotes: 2

Views: 887

Answers (1)

nrabinowitz
nrabinowitz

Reputation: 55678

Update

The functionality described below is now available in the core library as cellToChildPos and its corollary childPosToCell.

Original Answer

This breakdown of the bit layout might help (in terms of understanding the index structure).

  • There are 122 base cells. Every cell in the grid is either one of these base cells or a descendant of one of these base cells, so every index contains the base cell it descends from.
  • The rest of the index is hierarchical, walking down from the base cell. Essentially an address like "Base cell 27 child 2 child 0 child 3...".

It is possible to do what you're describing, purely with bit manipulation, but it requires a fair amount of knowledge of the H3 indexing system. I've done this before, but the code is currently proprietary and I can't share it here :(. As with a lot of H3 code, the pentagons are the hard part.

The solution looks something like this:

  • Determine the cell count at the desired res r for pentagon and non-pentagon base cells. Hex cells have 7^r children, pentagons have 1 + 5 * (7^r - 1) / 6 children (you can use maxH3ChildrenSize for this, but you'll need to know it anyway).
  • You'll need to know the pentagon base cell numbers. These are 4, 14, 24, 38, 49, 58, 63, 72, 83, 97, 107, 117

For a given number n:

  • Start with an "empty" index, 8ffffffffffffff. Set the resolution bits to r.
  • Determine the base cell n is in and the base cell offset (numPrecedingHexBaseCells * hexBaseSize + numPrecedingPentBaseCells * pentBaseSize).
  • Set the base cell bits in the index.
  • Subtract the offset from n. This is your child offset (i.e. the offset of the cell within the list of base cell children).
  • Use the child offset to figure out the index numbers for res 1, res 2, ...res r. I can't easily walk through the logic for this here, but you should be able to derive it from the formulas above for calculating the child counts (e.g. at res 1, a hex base cell has 7 children. At res 2, it has 49 - first figure out which res 1 group n is in with n % 7, then figure out the res 2 number, etc).

This is all pretty complex; we're planning to add it to the library, but it will be a few months at least. If you just need a streaming list of all cells at a res, and the performance isn't a strong requirement, you could use a DFS approach instead - for each base cell, find all children, then find all children of one child at the next res, then one child at the next res, etc until the desired resolution. This would only require keeping 7 * r cells in memory at a time.

Upvotes: 2

Related Questions