Positioning squares on a circle with minimum diameter

Question

Given n squares with edge length l, how can I determine the minimum radius r of the circle so that I can distribute all squares evenly along the perimeter of the circle without them overlapping? (Constraint: the first square will always be positioned at 12 o'clock.)

Followup question: how can I place n identical rectangles with height h and width w?

Answer 1

I would calculate an upper bound of the minimum radius, by working with circles enclosing the squares instead of with the squares themselves.

My calculation results in:

Rmin <= X / (sqrt(2) * sin (180/N) )

Where: X is the square side length, and N is the required number of squares.

I assume that the circles are positioned such that their centers fall on the big circle's circumference.

-- EDIT --

Using the idea of Dave in the comment below, we can also calculate a nice lower bound, by considering the circles to be inside the squares (thus having radius X/2). This bound is:

Rmin >= X / (2 * sin (180/N) )

Answer 2

As already noted, the problem of positioning n points equally spaced round the circumference of a circle is trivial. The (not-terribly) difficult part of the problem is to figure out the radius of the circle needed to give a pleasing layout of the squares. I suggest you follow one of the other answers and think of the squares being inside a circular 'buffer' big enough to contain the square and enough space to satisfy your aesthetic requirements. Then check the formula for the chord length between the centres of neighbouring squares. Now you have the angle, at the centre of the circle, subtended by the chord between square centres, and can easily compute the radius of the circle from the trigonometry of a triangle.

And, as to your follow up question: I suggest that you work out the problem for squares of side length min(h,w) on a circle, then transform the squares to rectangles and the circle to an ellipse with eccentricity h/w (or w/h).

Answer 3

You start with an arbitrary circle (e.g., with a diameter of (* n l)) and position the squares evenly on the circumference. Then you go through each pair of adjacent squares and:

• calculate the straight line connecting their mid points,

• calculate the intersection of this line with the intervening square sides (M1 and M2 are the mid points, S1 and S2 the corresponding intersections with the square side:

                  S2         S1
  M1--------------*----------*---------------M2
  
  
  ------------------------
  |                      |
  |                      |
  |                      |
  |                      |
  |          M1          |
  |           \          |
  |            \         |
  |      -------*------- +--------
  |      |       \       |       |
  |      |        \      |       |
  -------+---------*------       |
         |          \            |
         |           M2          |
         |                       |
         |                       |
         |                       |
         |                       |
         -------------------------
  

• calculate the scale factor you would need to make S1 and S2 fall together (simply the ratio of the sum of M1-S1 and S2-M2 to M1-M2), and

finally scale the circle by the maximum of the found scale factors.

Edit: This is the exact solution. However, a little thought can optimize this further for speed:

• You only need to do this for the squares closest to 45° (if n is even) resp. 45° and 135° (if n is odd; actually, you might prove that only one of these is necessary).
• For large n, the optimal spacing of the squares on the circle will quickly approach the length of a diagonal of a square. You could thus precompute the scaling factors for a few small n (up to a dozen or so), and then have a good enough approximation with the diagonal.

Answer 4

I would solve it like this:

To find the relation between the radius r and length l let's analyze dimensionless representation

• get the centres on a circle (x1,y1)..(xn,yn)
• from each center get lower right corner of the i-th square and upper left corner of the i+1-th square
• the two points should either have equal x or equal y, whichever yields smaller l
• procedure should be repeated for each center and the one that yields smallest l is the final solution.

This is the optimal solution and can be solved it terms of r = f(l). The solution can be adapted to rectangles by adjusting the formula for xLR[i] and yUL[i+1].

Will try to give some pseudo code.

EDIT:
There's a bug in the procedure, lower right and upper left are not necessary closest points for two neighbouring squares/rectangles.