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.

Possible Duplicate:
algorithm to place maximum number of points within constrained area at a minimum spacing

I'm trying to fit as many 30ft diameter circles into polygons of certain land cover classes without any overlap, neither with one another nor with adjacent classes. I'm trying to fit the maximum number possible.

I'm having two problems, I can't figure out how to drop circles and I can't figure out how to maximize the number of them.

Any thoughts?

share|improve this question

marked as duplicate by underdark Oct 28 '11 at 6:31

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2  
Is that different from this question ? gis.stackexchange.com/questions/4828/… –  Kirk Kuykendall Oct 28 '11 at 2:04

1 Answer 1

Sounds like a geometric knapsack problem.

share|improve this answer
    
In some sense the geometric knapsack problem is "dual" to the one stated: we are already given the points and wish to find a polygon that maximizes a certain objective. It is not apparent, though, how one might transform this into the problem stated here. –  whuber Oct 28 '11 at 14:44
    
I must be interpreting differently, but we need a slighty better explanation of the problem before we elaborate :) –  Ragi Yaser Burhum Oct 28 '11 at 16:04
    
I am trying to determine how many trees can be planted in certain areas of a map. After classifications we will have, say, a polygon that's classified as bare soil and could be used for tree plantings. If we assume one tree size, 30ft diameter crown, I'd like to know how many fit into that polygon; maximal. I can manually fit circles representing 30ft-diameter trees into the polygon but it would be nice if that could be done automatically. And, of course, there cannot be any overlap with polygon boundaries. –  Julia Nov 2 '11 at 19:20
    
I should add to this that polygons have various shapes and sizes so I cannot create them based on a grid . –  Julia Nov 2 '11 at 19:31
    
Can anybody help me find the question my questions is a duplicate of? I can't seem to locate it. –  Julia Nov 2 '11 at 21:30

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