How to get minimum-sized rectangle that contains certain rectangles?

Question

Recently I am thinking of an algorithm that can calculate the minimum-sized rectangle that contains certain rectangles.

The goal of this algorithm is to generate a big rectangle that I can put all given smaller rectangles in. One of these smaller rectangles should not partly or entirely overlap another. And before I put smaller rectangles in the big rectangle, I can rotate them 90 degrees or not. The big rectangle should be as small as it can be.

Does anyone have some clues about it?

No. Actually this algorithm is used for atlas merging. The input images cannot be re-shaped. — patronumme
I started this question with "Hi All.\n" but the system deleted "Hi " and line feed. I'm new here and I don't know why it works like this. :-p — patronumme
This is called a "rectangular packing problem". Google it. Since everybody that manufactures something out of sheets of material needs this is some form or another, it's a well-developed area of research. — n. 1.8e9-where's-my-share m.
@n.m. Thanks. I think this is exactly what I want. Now how should I deal with this question? Is there a way to cancel it? or I just do nothing? — patronumme

patronumme patronumme · Accepted Answer · 2014-08-12T15:50:16

I was researching on this issue for some time. And I've come up with a solution reference to some links and articles about this issue. Here are two of the names of articles:,. You can google and download them if you want to read these articles.

It's a pity that none of the articles can exactly solve my problem. Because what I want is neither to check if certain rectangles can be put into a fix-sized large rectangle nor a best area-allocating method that cost long time to result. So I have to balance between time and effect. I do this: 1.I prepare a list of candidate points and add the left-top point to it. 2.I place rectangles one by one into the large rectangle. 3.Every time when I place a rectangle, I check all candidate points to see if I can put the rectangle on the point. And I just keep the best two or three ones(best means minimum-sized if this rectangle is the last one). 4.I choose a candidate point to place the rectangle and replace one point to two points(right-top point and left-bottom one of the rectangle) if they are checked valid to place the next rectangle. 5.I recursively do step 3 to place a next rectangle.

I use C++ language do coding so I can code like this:

void computeMinimunRects(int index, Array objects, Array candidates, RectChecker checker)
{
 if (index == objects.count()){
  checkresult(objects);// finished putting all rectangles
  return;
 }
 int c = 2;// or 3 which based on objects.count()
 SortPoint possibles;// SortPoint sort all input points by total area from small to big.
 for (int i = 0; i<candidates.count(); i++){
  if (checkput(candidates[i], objects[index].size))// check if objects[index].size can put on candidates[i] point
   possibles.insert(candidates[i], objects[index].size);// input all needed value and sort them.
 }
 for(int i = 0; i<c; i++){
  Point pt = possibles[i].pt;
  Size size = possibles[i].size;
  Rect rect(pt, size);
  candidate.remove(pt);// replace point with two ones.
  candidate.add(rect.right_top());
  candidate.add(rect.left_bottom());
  computeMinimunRects(index+1, objects, candidates, checker);// recursively input rectangle
  candidates.remove(rect.right_top());// revert all changes
  candidates.remove(rect.left_bottom());
  candidates.add(pt);
 }
}

How to get minimum-sized rectangle that contains certain rectangles?

1 Answers