# insert maximal number of circles into polygons [duplicate]

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.

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

## 1 Answer

Sounds like a geometric knapsack problem.

-
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