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

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.

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.