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?

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.

  • Sounds like a geometric knapsack problem. – Ragi Yaser Burhum Oct 28 '11 at 1:24
  • 2
    Is that different from this question ? gis.stackexchange.com/questions/4828/… – Kirk Kuykendall Oct 28 '11 at 2:04
  • 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

Browse other questions tagged or ask your own question.