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.


Your Answer

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

Browse other questions tagged or ask your own question.