creating circles from rectangles

August 17, 2008 6:49 AM

Math filter: How many equally sized rectangles will fit into a circle, and how should I arrange them in order to make the best-looking approximation?

I want to create an approximate circle from a number of equally-sized rectangles. How do I do this for an arbitrarily sized rectangle or circle?

For example, suppose I have 100 rectangles of size 5x6 (or generally LxW). I want to create the best approximation of a circle using these rectangles. How can I calculate what the resulting radius of the circle will be, and how do I arrange the rectangles to achieve the best approximation?

The inverse question is also useful: If I want to create an approximate circle with a radius of 31, how many rectangles of size 5x6 (or LxW) do I need, and how should I arrange them?

The general formula / strategy / algorithm would be most useful. But, if you have the answer for 100 rectangles of size 5x6, that would be good too. I'm also interested in the answering the same question for 25-30 rectangles of size 11x11.

posted by brandnew to science & nature (9 comments total)

This is a variant on bin packing (see also: packing problem) and is NP-complete, so unless you have some other constraints to simplify the problem, it's generally not solvable by any quick or easy analytic means. Humans tend to be decent at eyeballing these hard optimization problems, so that might be your best bet, though 100 is a lot to manage.

If you want to get started with a stochastic solution, you should begin by defining what you mean by the "best" approximation: Are rectangles allowed to exceed the bounds of the actual circle? If so, is overlap worse than underlap? Do we care more about % of the circle covered, or minimizing the largest distance from the edge of the circle?
posted by 0xFCAF at 7:07 AM on August 17, 2008

I'm looking for a subjective best-looking approximation (this is for an art project).

So, to guess what I mean is that I want the individual overlap or underlap at any point of the circle to be as minimal as possible.
posted by brandnew at 7:32 AM on August 17, 2008

5x6, eh? Are you working with Legos, by some coincidence? If so, your question may be simpler than you think, depending on what you're actually trying to do. Also, approximating a circle with rectangles of size 11x 11 is exactly the same as approximating a circle with squares of size 1x1, so you should think about that as well.

Depending on your application, there are probably a lot of constraints you haven't mentioned. Can the rectangles be at any orientation, or do they all have to be parallel to each other (or possible perpendicular)? Can there be any gaps between the rectangles?

The easiest way to at least estimate the radius of a circle approximable by n LxW rectangles is to figure out the area you have to work with. You've got n*L*W units^2 of area in rectangles, so if you melted them down and poured them into a circle, its area would also be nLW = pi*r^2, and thus it would have a radius of r = sqrt(n*L*W/pi). In the case of 100 rectangles of size 5x6, that radius would (coincidentally?) be almost 31 units. 25-30 squares of width 11 would get you a circle of radius roughly 31-34 units.
posted by ErWenn at 7:35 AM on August 17, 2008

I've been to talks on this exact problem, and 0xFCAF is right in that it's basically sphere packing in reverse. Cube/square packing is very hard (and the result isn't symmetric by any means), but honestly if you have specific limitations on the problem your best best is to actually build a physical model (like a narrow plexiglass box), toss in your bricks, shake, and then take some pictures. In other words, if you don't need a general solution then physics will solve your problem (and by 'solve' I mean get a good enough solution) faster than your brain will.

I actually tossed around writing some code with a physics simulator to do this exact thing awhile back, but from a pure math perspective it wouldn't be as interesting as a general solution so I didn't pursue it. Besides, I have my own thesis to worry about, but you've kindled the spark again, so thanks!
posted by monkeymadness at 8:05 AM on August 17, 2008

you want to be careful here. it's very easy to say this is similar to bin packing and so can't be solved, but it's not bin packing - in that case the objects are of different sizes. the same "argument by vague analogy" would say it's like close packing of spheres, which is pretty close to having a solution.

i agree it's probably hard (and i certainly don't know of the answer), but i see nothing here that is anything close to guaranteeing it's np.
posted by not sure this is a good idea at 8:31 AM on August 17, 2008

Well...folks have looked at this problem.

If we start with the "simpler" problem of 1x1 squares, you can see that there is a standard regular packing (see packings for 31 and 32) which will give you a ratio of areas of about 1.25 (area of your squares/area of circle) If we extend this to 100 squares we get an area of 125, or a radius of about 6.36.

I'm also interested in the answering the same question for 25-30 rectangles of size 11x11.

So, that question is now answered. The answer is sqrt(121N*1.25/PI) where N is the number of rectangles.

Arbitrary rectangles are trickier since these are of a different shape than squares and so they will pack differently. A 5x6 rectangle of course can be reduced to 30 1x1 squares but the latter is more flexible. But that still places a bound on the best you can do. That is you wont be able to make a circle smaller than a radius of sqrt(30N*1.25/PI) although depending on your packing you may get close.
posted by vacapinta at 9:26 AM on August 17, 2008 [2 favorites]

Hmm... my approach would be to pretend the rectangles were pixels and draw a filled circle with them according to your favourite computer graphics algorithm. This works for 1x1 and n x n rectangles (AKA squares).

For non-square rectangles, in proportion 1:m, you shrink the circle according to the inverse proportion 1/m, so it's an ellipse. Then you fill the ellipse with squares, then stretch the ellipse back out so it's a circle, and so the squares it's filled with are stretched out to become rectangles of the right size.
posted by cogat at 5:24 PM on August 17, 2008

btw - my approach would look good to a human as the OP requested, but is almost certainly not the mathematically optimal solution.
posted by cogat at 5:26 PM on August 17, 2008

...er, because a mathematically optimal solution is likely not to have all the rectangles aligned at the corners, which my approach would.
posted by cogat at 5:28 PM on August 17, 2008