2

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?

Community
  • 1
Julia
  • 111
  • 1
  • 2
  • 7
  • 2
    Is that different from this question ? http://gis.stackexchange.com/questions/4828/algorithm-to-place-maximum-number-of-points-within-constrained-area-at-a-minimum – Kirk Kuykendall Oct 28 '11 at 02:04
  • Sounds like a geometric knapsack problem. – Ragi Yaser Burhum Oct 28 '11 at 01:24
  • 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 02 '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 02 '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 02 '11 at 21:30
  • They say it is this http://gis.stackexchange.com/questions/4828/algorithm-to-place-maximum-number-of-points-within-constrained-area-at-a-minimum I think it is this: http://stackoverflow.com/questions/6864382/packing-arbitrary-polygons-within-an-arbitrary-boundary – Ragi Yaser Burhum Nov 02 '11 at 21:37
  • I don't have a certain number of disks I need to fit, just the max number of disks, all of the same one size. Polygons will not be of any regular shape, some may be rectangles and some may be very oddly shaped. – Julia Nov 03 '11 at 16:15
  • @Julia yeah, that is what the second link I added in the comments talks about. Once they are filled, you can stop. – Ragi Yaser Burhum Nov 04 '11 at 00:44

0 Answers0