3

Given an EPSG:4326 lon,lat coordinate pair, and a radius r in meters, I want to find the smallest set of H3 hexagons at resolution res that completely covers the circle centered at lon,lat with radius r.

The H3 library has a polygon_to_cells function that returns the set of H3 cells with their center points inside a given polygon.

My current strategy (in Python because that's what I happen to be using) is to approximate a circle with a polygon, by "stepping" through forward azimuths from 0 to 360 degrees and computing the point that is r distance away at each forward azimuth value. I am then using the polygon_to_cells function on that circle-approximating polygon.

Based on some un-rigorous geometric intuition, it seems like if I set the buffer size to r + (2 × res), then I should be able to cover every point in the original circle of radius r with an H3 cell. If I want to find the "minimum" covering set, I can then loop over the resulting list of H3 cells and prune away any that do not intersect the original (approximated) circle.

However this approach seems very ad-hoc and unprincipled. Is there some better algorithm I can use?

Edit: It looks like H3 uses spherical coordinates with the WGS84 authalic radius (source), in case that helps.

1 Answer 1

1

One option would be to calculate your polygon as you are now (though I'd probably use a popular geometry library like Shapely rather than my own circle buffering algorithm), but only with a buffer of r. Then use h3.grid_ring with k = 1, and calculate the intersection of the sets. This isn't very efficient unless you can first limit this to cells that don't already have 6 neighbours (which is possible to work out) or perhaps use grid distance from the cell at the centre as information for how to limit the computation.

A slight frame challenge response might be that if you really care about strict coverage of the circle, then a DGGS might not be the appropriate tool. The basic idea is to approximate geographic objects, in the same way a digital recording of an analogue wave only approximates the original, continuous sound. If you need higher fidelity, you should increase the cell resolution.

1
  • 1
    It turns out that this is how the h3ronpy library does it internally. Thanks! In my case the problem was not a matter of fidelity but of exhaustiveness. For example using H3 index to coarsely filter for matching polygons, followed by a precise intersection check on the filtered data. Commented Nov 30, 2023 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.