Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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.

share|improve this question
    
Is the extent arbitrary shape? Is it a polygon or rectangle? –  BradHards Feb 19 '13 at 1:35
3  
Can you post an image of what you'd like to achieve? –  Fezter Feb 19 '13 at 2:55
1  
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 –  blah238 Feb 19 '13 at 10:33
1  
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! –  Bret Walker Feb 19 '13 at 12:48

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
1  
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. –  Bret Walker Feb 19 '13 at 3:24
    
Is this the endpoint you are using? instagram.com/developer/endpoints/locations/… –  blah238 Feb 19 '13 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. –  Bret Walker Feb 19 '13 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.

share|improve this answer

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

    
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. :) –  banderkat Dec 29 '13 at 21:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.