Java – given some rectangles that can be rotated, find a closed rectangle with the smallest area

So I'm trying to implement an algorithm that takes many rectangles as input and tries to package them into rectangles with the smallest area Rectangles can be rotated 90 degrees

I realize that this is similar to the bin packing problem, but I can't find a good algorithm to consider rotation I found a paper and discussed it here. Although I understand the article itself, I hope to find something simpler

Any suggestions?

-Edit-

I think I misunderstood the problem earlier We give many rectangles so that each rectangle can rotate 90 degrees We need to find a rectangle that fits all given rectangles so that there will be no overlap between two rectangles and minimize the area of the closed rectangle

The problem I encounter here is that we are asked to find the minimum value instead of giving a closed rectangle and checking whether the given rectangle is suitable or something similar

Solution

I use this algorithm to get good results:

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

Edit:

The algorithm described in the link I provide will give a "yes" or "no" answer about whether a given set of rectangles can be packaged into a specific closed rectangle To find the smallest bounding rectangle, you can run the algorithm repeatedly Basically, the lower and upper bounds of the bounding rectangle are calculated, and then a binary search is performed to find the minimum solution falling within these boundaries I assume that the closed rectangle is of a fixed size in one dimension (i.e., the width is constant, find the minimum length, and vice versa) If the width and length of the enclosing rectangle are allowed to change, it is more difficult, which may not work

A simple (but naive) way to calculate the lower and upper limits is as follows:

Lower bound – at best, all rectangles can be perfectly packed without wasting any space Therefore, sum the areas of all input rectangles and calculate the length of the surrounding rectangle required for the region

Upper limit – in the worst case, each rectangle must be packed on a separate "row", so for each input rectangle, min (width, height) is calculated and summed (that is, pretend that the input rectangles are stacked with the minimum value) the width or height of each input so that the other dimension of the input does not exceed the width of the surrounding rectangle)

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