Given the number of rectangles you can rotate, find the rectangle with the smallest area

Question

So, I'm trying to implement an algorithm that takes a series of rectangles as input, and tries to pack them into a rectangle of a minimal area. All rectangles can be rotated 90 degrees.

I understand this seems like a bin packaging problem, but I can't find a good algorithm that takes rotation into account. I found an article that discusses this in detail here , and although I understand this article, I was hoping to find something simpler.

Any suggestions?

-Edit -

I think I used to be wrong. We are given a series of rectangles, each of which can rotate 90 degrees. We need to find a rectangle that matches all of the specified rectangles so that none of the two rectangles overlap, while minimizing the area of ​​the enclosing rectangle.

The problem I am facing here is that we will be asked to find the minimum, and not give a rectangle with a rectangle and check if the given rectangles or something like that correspond.

Answer 1

I had good results using this algorithm:

http://www.intechopen.com/articles/show/title/a_greedy_algorithm_with_forward-looking_strategy

Edit:

The algorithm described in the link will give you an answer of "Yes" or "No" as to whether this set of rectangles can be packed into a specific rectangle. To find the minimum rectangle, you can run the algorithm again. Basically, calculate the lower bound and the upper bound for the enclosing rectangle, then do a binary search to find the minimal solution that falls within these bounds. I assume that the enclosing rectangle is a fixed size in one dimension (i.e. Width is constant looking for minimum length or vice versa). If the width and length of the enclosing rectangle can vary, then this is more complicated, and this may not work.

A simple (but naive) approach to calculating the lower bound and the upper bound will be as follows:

Bottom line. The best case is that all rectangles can be completely packed without any wasted space. So, we summarize the area of ​​all input rectangles and calculate the length of the rectangle required for this area.

Upper bounds. The worst case is that each rectangle must be packed in a separate "line", so for each input rectangle, calculate min(width, height) and sum them up (that is, pretend that the input rectangles stack on top of each other using a minimum the width or height of each input, so that the other size of the input signal does not exceed the width of the enclosing rectangle).

If you work a little harder, you can significantly improve the lower and upper bounds to reduce the search space, but this should give you a starting point.