If I have a geographic extent, is there any way to find all of the center points of all of the 5km circles that would be needed to cover the entire extent?
I'm working with an API that will return results that occur within a 5km radius of a given latitude and longitude.
I would like to come up with a way to get all of the items occurring within the extent.
This sounds like a type of packing problem. Here is a Python implementation of the circle packing in a rectangle variation: https://gist.github.com/CnrLwlss/4572781
See also this closely related question: algorithm to place maximum number of points within constrained area at a minimum spacing
However, you need to consider that there can be many if not infinite number of solutions so you will need to consider what the API you are using is outputting vs. what the packing solution is outputting.
What API are you using?
Perhaps you could use a hexagonal grid as discussed in these questions:
The centroid of each hexagon with radius = 5km should be a good enough approximation. There will of course be some overlap since a 5km circle is larger than a 5km hexagon.
This StackOverflow question offers an algorithm to generate an "almost, but not quite hexagonal lattice", with the answers offering optimizations: Efficiently generate a lattice of points in python
This ArcGIS Geoprocessing Sample purports to be able to create a hexagonal polygon feature class: Create Hexagons
This Math.SE answer suggests there is no optimal solution to the "cover a rectangle with circles" problem, but that the hexagonal lattice approach is likely good enough.
One more thing to consider is that since you are working with geographic coordinates that what you are actually looking for is a Geodesic Grid, not a hexagonal lattice. The answers on this SO question have some good information as well: Covering Earth with Hexagonal Map Tiles
However it may be easiest to work in Euclidean space until geographic coordinates are needed (those of your centroids), and simply project into geographic coordinates at that time. To do this of course you will need a projection engine or algorithm.
Here's a Python module to find the centroids of 50km hexagons to tile a bounding box (I'm using it to query the Google Places API.)
As hexagons have the greatest number of sides on any regular polygon that can tile, they provide a useful approximation of a circle for covering an area. The circles that circumscribe the hexagons can cover an area with minimal overlap and full coverage.
