# Method for finding circle center points that cover an extent

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.

• Is the extent arbitrary shape? Is it a polygon or rectangle? Feb 19, 2013 at 1:35
• Can you post an image of what you'd like to achieve?
– Fezter
Feb 19, 2013 at 2:55
• This StackOverflow question offers some images of what I imagine the OP is looking for: Fully cover a rectangle with minimum amount of fixed radius circles Feb 19, 2013 at 10:33
• BradHards, the extent is a rectangle. Fetzer, blah238 is right. I need to be able to find the lat/long of the center of circles that look like the pic in his link, and the circles can max a maximum radius of 5km. Thanks all! Feb 19, 2013 at 12:48

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.

• I'm using the Instagram API. One thing I'll need to do is have the circles overlap so that there are no gaps, which I think is contrary to the packing problem descriptions I've seen. Feb 19, 2013 at 3:24
• Is this the endpoint you are using? instagram.com/developer/endpoints/locations/… Feb 19, 2013 at 3:38
• No, I'm using this one: instagram.com/developer/endpoints/media. The locations endpoint returns places, like businesses. The media endpoint lets one search by a given point, returning all images within a 5km radius. Feb 19, 2013 at 12:45

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.

• Given the preceding discussion, which covers at length how to approach the problem, but offers no solution, I don't have much more to add, other than code that actually accomplishes what the OP is looking for. :) Dec 29, 2013 at 21:23