Open AltaherPresto opened 1 year ago
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.
Copying my answer from https://github.com/uber/h3-py/issues/291:
My suggestion would be:
gridDisk(cell, 1)
) are in the set.This is a O(n)
algorithm, and should be straightforward to implement.
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?
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.
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.
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.
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.
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.
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?