Is there a method to validate that a list of hexagon IDs are one contiguous bloc?

[AltaherPresto]

I'm looking for a way to validate if a list of cell id's (all same resolution) is a contiguous bloc (single island of hexagons).
My use case is a map-picker where the user selects multiple hexagons but the selection must constitute one contiguous bloc.
My initial thought was to use h3.are_neighbor_cells (https://uber.github.io/h3-py/api_reference.html#h3.are_neighbor_cells but then I realised that not every cell has to be neighbours with every other cell to satisfy this contiguous bloc requirement.

Is there a method to perform such a check?

[isaacbrodsky]

It looks to me like this would require something like BFS/DFS or a flood fill algorithm. If you only need contiguity yes/no there are some optimizations that can be made, I think using the localIj algorithms in H3 and iterating through in order. This type of algorithm is not available in the H3 library today.

[nrabinowitz]

Copying my answer from uber/h3-py#291:

My suggestion would be:

• Add all cells to a set
• For each cell, assert that at least one of its immediate neighbors (from gridDisk(cell, 1)) are in the set.

This is a O(n) algorithm, and should be straightforward to implement.

[isaacbrodsky]

Copying my answer from uber/h3-py#291:

My suggestion would be:

* Add all cells to a set

* For each cell, assert that at least one of its immediate neighbors (from `gridDisk(cell, 1)`) are in the set.

This is a O(n) algorithm, and should be straightforward to implement.

Would this return true (undesirably) if the cells make up two separate blocs?

[nrabinowitz]

Copying my answer from uber/h3-py#291:
My suggestion would be:

* Add all cells to a set

* For each cell, assert that at least one of its immediate neighbors (from `gridDisk(cell, 1)`) are in the set.

This is a O(n) algorithm, and should be straightforward to implement.

Would this return true (undesirably) if the cells make up two separate blocs?

... yes 🤦

I guess the easy way to determine this, though it feels a bit computationally expensive for the purpose, would be to use cellsToMultiPolygon. If there's only one outer loop, all cells are contiguous.

This also allows for holes, so you could disallow any contiguous set with holes if you choose.

[douglasg14b]

I guess the easy way to determine this, though it feels a bit computationally expensive for the purpose, would be to use cellsToMultiPolygon. If there's only one outer loop, all cells are contiguous.

This is how I currently do this, and it is unfortunately a pretty expensive operation :/

I use it because I disallow holes in my use case, and this makes finding them dead simple, but calls to cellsToMultiPolygon constitute like 80% of the CPU time on paths that use it. If there are alternatives I should be exploring, I'm all ears.

[dfellis]

This is a graph theory problem. Making sure a set of hexagons are all contiguous should be doable relatively cheaply. Also confirming there are no holes is more complex, though.

Without that constraint, we just need to confirm that all hexagons can "reach" some arbitrarily chosen hexagon. I remember reading some biology-inspired algorithm with bacterial culture growth (or something like that) but I can't seem to find it.

1. In any case, take the set of cells, make a hashmap with the key being the cell ID and the value being a boolean indicating that it has been "reached", and make a hashset of the cell IDs (for faster lookup) of ones we are considering.
2. Create a variable array/queue and push one of the cells at random into the queue and mark it as "reached."
3. Enter a do-while loop that executes until the queue is empty.
4. First pop one element off of the queue
5. Compute the k-ring (actual ring, not the disk) of the neighbors of that cell.
6. For each neighbor in the ring, check if it is in the hashset of cells, skipping over any that are not. Then check if it is already marked as "reached" in the hashmap and skip over those, too. Any cells that pass both of those tests get marked as "reached" and have their ID pushed into the queue.
7. Once the loop is done, check if any elements in the hashmap are still false (not "reached"). If all are true, it's one contiguous set, if any is false it is not a contiguous set.

I need to think a bit more on how you'd detect holes, but this could at least be a much faster first-pass filter for now for sets that are disconnected that you absolutely should ignore.

[dfellis]

Oh, and that hashset may or may not be necessary in your language of choice depending on if your HashMap implementation has a hashmap.has(key) method (or equivalent).

The do-while with the queue makes sure that only cells that have a known path to prior checked cells are the ones that are checked, which is how the contiguous nature is kept. The k-ring of 1 calculation makes more work, but it can be considered a higher constant-time for each tested cell, which is why this should still be an O(n) algo.