How to obtain the minimal covering of a circle with H3 hexagons?

Question

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.

Answer 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.