Packing fixed-size rectangles inside a circle with the biggest "zoom"

Question

I need an algorithm to place a set of N rectangles inside a circle of radius R, so that they are scaled up to the biggest possible size that doesn't exceed the border of the circle. I'm still working on it so If I find the answer I'll post it here...

Answer 1

If I would do this I would probably do it through a binary search using a function testing whether the problem is solvable for a given N, R and rectangle_scale.

The test function should probably be something like:

testfunction(R, rectangle_scale)

1. Fit as many rectangle as possible along the diameter
2. Fit as many as possible above the diameter adjacent to the rectangle on top of the diameter (e.g. 2*R/rectangle_scale*side) or something like that)
3. Repeat (placing above the rectangles you just place. Do this until no more rectangles can be fit
4. return the number of rectangles that fit

The binary search would then be standard:

while(upperbound-lowerbound > limit) {
   new_bound = (upperbound+lowerbound) / 2;
   num_fit = testfunction(N, R, new_bound);
   if(num_fit > N) {
      upperbound = new_bound;
   } else {
      lowerbound = new_bound;
   }
}

Ideally you would of course want to do this mathematically. If an approximation is fine for you, you could maybe do it through areas. A proximation would be (rectangle_area*scale*N = pi*R^2) => scale = scale = pi*R^2 / N / rectangle_area.

However, if you need accuracy I would only use the area approximation for setting the initial lower/upper bounds in an intelligent way.

Hope this helps!