6
$\begingroup$

I have a fixed rectangle of size X x Y. I also have a bunch of rectangles of different sizes.

I want to check if these rectangles can fit in the larger X x Y rectangles knowing that one can rotate any one of them by 90°.

Any great algorithm to do this ?

I know that some packing algorithm exists and several threads discuss it but it's not exact and it does not support rectangle rotation, therefore I cannot apply it to find a minimum rectangle and compare it afterwards to the given X x Y rectangle.

$\endgroup$
  • 2
    $\begingroup$ Related (but I don't think has an answer to your question): stackoverflow.com/q/1213394/781723, codeproject.com/Articles/210979/…, www.aaai.org/Papers/ICAPS/2003/ICAPS03-029.pdf $\endgroup$ – D.W. Feb 23 '18 at 16:57
  • $\begingroup$ Sounds quite difficult... $\endgroup$ – Yuval Filmus Feb 23 '18 at 17:07
  • $\begingroup$ Just curious, but does this problem fall within any of the NP or NP-complete spaces? Feels like it... $\endgroup$ – selbie Feb 23 '18 at 17:32
  • $\begingroup$ If you suspect the answer to a particular instance is "NO" but only have available an algorithm that never rotates rectangles, you can use it in the following way: (1) Decompose every rectangle into squares (e.g. by chopping the longer edge to the length of the shorter, then recursing); (2) Pass the resulting set of squares to the algorithm. If it says "NO", the answer to the original problem is definitely "NO". (But if it says "YES", we can't be sure.) $\endgroup$ – j_random_hacker Feb 23 '18 at 17:51
  • $\begingroup$ Similarly, if you "grow" the shorter side length of each rectangle until it equals the longer side length (and thereby becomes a possibly larger square), and the non-rotating algorithm says "YES", then you can definitely say "YES" too. (This and my previous comment will probably only be useful when most rectangles are already close to being squares.) $\endgroup$ – j_random_hacker Feb 23 '18 at 18:02
2
+25
$\begingroup$

As mentioned in the comments, this problem is known to be NP-hard. So, the only fast algorithms you're going to get will be approximation algorithms or heuristic. As this is a common practical problem (packaging for logistics, for example), there are many heuristic algorithms, both general and with more assumptions.

A lot approaches ignore rotation, but can be expanded fairly easily to support it. As you seem to be aware of approaches without rotation, I'll focus on the rotating part.

A good resource is 'One thousand ways to pack the bin', by Jukka Jylänki. It covers many heuristic algorithms, and considers rotation part of the problem. Most of the rest of this post summarizes this paper.

While rotation makes the problem a lot harder to solve exactly, it doesn't make most heuristic methods much more complicated, as they cannot afford to make complicated choices and so choose heuristically how to rotate.

Shelf heuristic

For the shelf algorithms, rotation is quite simple:

  1. If the current rectangle starts a new shelf, we rotate such that the shelf height is minimal.
  2. Otherwise, rotate such that the width is minimal while still fitting the shelf (if it fits at all)

Point 2 is actually the best way to rotate given that the rectangle will be packed in the current shelf while for point 1 one could argue to do the opposite and this could indeed be better in some cases. (such as the case that all remaining rectangles are squares with length equal to the long side of the first rectangle of the shelf)

Guillotine heuristic

For the guillotine algorithm, the choice for rotation isn't so clear (perhaps a reason why Jylänki leaves this open), but one reasonable method is to try both orientations to decide whether a rectangle 'fits'. If both fit, one could try to pick the one that matches the split rule (for example, choose the rotation that minimizes the area of the chosen free rectangle when using the Best Area Fit variant)

Other heuristics

For the Maximal rectangle algorithm and the Skyline heuristic, supporting rotation here is similar to the Guillotine case, there aren't really any particular choices other than trying to fit with both orientations and pick the one which makes more 'sense' with respect to the rest of the specific heuristic.

There are more algorithms, but I think this gives a good overview of the ideas of how to support rotation. As you might have noticed, these methods aren't too fancy, that is sometimes the best you're going to get.

$\endgroup$
  • $\begingroup$ Any way to tell if it's possible to put the n rectangles inside the larger rectangle for a small n (e.g less than 20) ? (Maybe even Bruteforce ?) $\endgroup$ – user84880 Feb 28 '18 at 19:49
  • $\begingroup$ @Guru Yes, for small n you could try to bruteforce by simply running your non-rotation algorithm for all $2^n$ possible rotations of the given rectangles. But this is unfeasible for even medium sized n. $\endgroup$ – Discrete lizard Feb 28 '18 at 20:14
  • $\begingroup$ But is there really a non-rotation algorithm which can solve the problem exactly (i.e tell with certainty that the rectangles fit or not) ? Because all the ones above and the ones I've found, if I'm not mistaken, are approximative. $\endgroup$ – user84880 Feb 28 '18 at 20:16
  • $\begingroup$ @Guru Of course there exist exact algorithms. For instance, you can test all possible placements for free rectangles in the Maximal rectangle algorithm, instead of just heuristically picking one. However, this is inefficient and as this problem is NP-hard, efficient exact algorithms are unlikely. $\endgroup$ – Discrete lizard Feb 28 '18 at 20:21
  • $\begingroup$ I would like to have said that if the user84880 is interested in exact solutions, it would be better to ask a new question (if no proper one exists), as there is more to be said about that. But I guess this now falls on deaf ears... $\endgroup$ – Discrete lizard Mar 3 '18 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.