3

Possible Duplicate:
How to pack squares into circles?

I have a problem where I need to fit a bunch of different sized rectangles within a circle. All the rectangles must fit in the circle without overlapping each other and without overflowing the circle.

Assuming the rectangles can fit inside the circle how would one develop an algorithm to distribute them inside the circle?

All I can think of is to randomly distribute the rectangles over and over and test whether the conditions are met (brute-force).

Community
  • 1
  • 1
George Reith
  • 13,132
  • 18
  • 79
  • 148
  • The problem is closely related to the binpacking problem (on 2d), which is NP Hard - There is no known efficient solution to the question "Will the rectangles fit in the circle?", let alone - find the placement that makes them fit. More specifically, it is almost identical to [this problem](http://stackoverflow.com/q/7342389/572670), which is NPC as well. – amit Oct 04 '12 at 13:14
  • The best approach is going to depend heavily on how tight the packing needs to be. If you need to fit three small rectangles inside a huge circle, then your approach would be simple and effective. As the circle size gets smaller and the number of rectangles gets larger, the algorithm has to become more sophisticated to solve the problem in a reasonable amount of time. – Vaughn Cato Oct 04 '12 at 13:45

2 Answers2

3

It is a classic constraint problem, brute-force is one way to do it but there are other ways that can be better using things such as heuristics to help guide the algorithm to the solution. You would have to look up some constraint programming and bin packing papers on something like Google Scholar for some better algorithms.

Wikipedia has a good overview: http://en.wikipedia.org/wiki/Packing_problem

Sean Dawson
  • 5,587
  • 2
  • 27
  • 34
1

As others have mentioned, an optimal solution (in say minimal area or uniform distriubtion) is likely to be NP-hard. Nevertheless, depending on your needs there are some great algorithms for packing differently sized rectangles into other rectangles. For example: Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites:

This article describes a fast algorithm to pack a series of rectangles of varying widths and heights into a single enclosing rectangle, with no overlap and in a way that minimizes the amount of wasted space in the enclosing rectangle. [...] shows step by step how the algorithm arrives at the optimal enclosing rectangle.

Note that in the above procedure the bounding rectangle is allowed to vary (nor am I convinced that the solution is the optimal enclosing rectangle). You can approximate a circle by breaking it up into discrete rectangles.

While not a complete solution to what you are looking for, I think this may be a good first step.

Hooked
  • 84,485
  • 43
  • 192
  • 261