Given a number of rectangles that can be rotated, find an enclosing rectangle of minimum area
Posted
by
efficiencyIsBliss
on Stack Overflow
See other posts from Stack Overflow
or by efficiencyIsBliss
Published on 2010-12-31T21:14:21Z
Indexed on
2011/01/01
6:54 UTC
Read the original article
Hit count: 234
So, I'm trying to implement an algorithm that takes in a number of rectangles as input and tries to pack them into a rectangle of minimum area. The rectangles can all be rotated by 90 degrees.
I realize that this is similar to the bin packing problem, but I am unable to find a good algorithm that accounts for the rotation. I found a paper that discusses this at length here and while I understand the article itself, I was hoping to find something simpler.
Any suggestions?
-Edit-
I think I misstated the problem earlier. We are given a number of rectangles, such that each can be rotated by 90 degrees. We need to find a rectangle that fits all the given rectangles such that no two rectangles overlap, while minimizing the area of the enclosing rectangle.
The problem I face here is that we are asked to find the minimum, as opposed to being given an enclosing rectangle and checking if the given rectangles fit or something of that sort.
© Stack Overflow or respective owner