3

I hope my title makes sense, but here is what I a trying to do:

I have n rectangles, each with widths of Wn and heights of Hn that I need to arrange so on a two dimensional (x,y) plane the rectangle that they all fit in takes up the least area. I also need to be able to establish what (x,y) corresponds to what rectangle.

I would prefer something in psuedo-code, but can work with many languages.

Thanks for helping.

moinudin
  • 134,091
  • 45
  • 190
  • 216
Tom
  • 6,947
  • 7
  • 46
  • 76
  • Seem to remember something about this being an NP-hard problem – Callum Rogers Dec 25 '10 at 23:21
  • possible duplicate of [How can I programmatically determine how to fit smaller boxes into a larger package?](http://stackoverflow.com/questions/140406/how-can-i-programmatically-determine-how-to-fit-smaller-boxes-into-a-larger-packa) – moinudin Dec 25 '10 at 23:45
  • I suspect you mean that the rectangles possibly have different widths and heights, in which case it would be clearer to say "I have n rectangles having widths Wi and heights Hi for 1 <= i <= n", or just "I have n rectangles of various given widths and heights". – j_random_hacker Dec 26 '10 at 10:39

4 Answers4

2

This is a difficult problem to be solved optimally, however there are some solutions that are not too hard to implement and that represent a good approximations for many uses (e.g. for textures). Try googling for "rect(angle) packing" ... you will find a lot of code that solves the problem.

6502
  • 112,025
  • 15
  • 165
  • 265
  • Sounds good to me, I'll check soon. I realized that approximations are fine for what I am doing so long as they run efficiently. – Tom Dec 25 '10 at 23:21
  • 1
    A lot of the differences between algorithms is in the details. For example do you have a fixed or maximal width (e.g. you're nesting a roll)? Do you have to work with fixed maximal dimensions in both X and Y (e.g. you're nesting sheets)? Do you allow 90 degree rotations? Must the solution be a guillotine one (a guillotine solution can get your rects by making a sequence of cuts that always run from one side to another)? – 6502 Dec 25 '10 at 23:25
  • My intention is that I cannot break apart any rectangle (no guillotine), I cannot rotate, but I do not have any parameters for container dimensions nor coordinates. – Tom Dec 25 '10 at 23:28
  • I probably wasn't clear enough. See http://i.imgur.com/et7eX.png and suppose that white is the "waste" ... the left solution is not a guillotine one, the right one instead is a guillotine one because if you cut in the sequence red, orange, green, cyan, gray, magenta, yellow you will always cut the remaining rectangle from side to side. In some machining operations this is a must (that is you cannot stop a cut in the middle of the sheet) so if that is the use then solutions like the left one cannot be applied. – 6502 Dec 25 '10 at 23:50
1

Sounds NP-complete to me. Kinda like the knapsack problem. Which means there is no real solution. Only good approximations.

zsalzbank
  • 9,685
  • 1
  • 26
  • 39
1

It's a variant on 2D bin packing. The fact that your container is flexible, allows for more optimization as well making it more challenging (as in difficult). Drools Planner (open source java) can handle this. At least one implementation (see user mailing list) with Drools Planner exists (not open source). If you need an open source example to start from, probably the cloud balance in drools-planner-examples is a good example to start from.

For an overview of the algorithms you can use, see my answer on a similar question.

Community
  • 1
  • 1
Geoffrey De Smet
  • 26,223
  • 11
  • 73
  • 120
0

Your problem is known as the 2D packing problem. Even the 1D problem is NP-hard. See here for a good article on some approaches along with sample C# code.

Also, see the following questions:

Community
  • 1
  • 1
moinudin
  • 134,091
  • 45
  • 190
  • 216
  • 1
    Although it's related, and I suspect NP-hard in its own right, the OP's problem is not quite the 2D packing problem because we aren't dealing with fixed size "stock" rectangles to be cut/packed. (For the same reason, the 1D version of the OP's problem is not NP-hard but in fact trivial -- just sum the lengths required to determine the total length needed.) – j_random_hacker Dec 26 '10 at 10:07
  • @j_random_hacker I'm not so sure now. The question does say W_n and H_n. @Tom Can you clarify? – moinudin Dec 26 '10 at 10:11
  • 1
    I think he meant W_i and H_i (i.e. each rectangle has known dimensions that may be different to the others'), but the key point is that these rectangles don't have to be *fit* into one or more fixed-size "stock" rectangles -- we're free to choose the shape of a single rectangle (e.g. long and skinny or closer to a square) that they will be packed into. – j_random_hacker Dec 26 '10 at 10:42