Packing rectangles into a rectangle

published on January 18, 2015 in Tips and Tricks3 comments

Once, I have been given the following task: make a JavaScript plugin that allows to fit a variable number of rectangles of different sizes into another rectangle.
Or better, you have a variable number of surfaces to cover with iron, iron is provided in panels of size depending on the factory: calculate the minimum number of panels that you need to fulfill the request. In this calculation, you need to include a margin between the rectangles as well – that corresponds to the line of cut.

It was a quite interesting challenge. Finding the perfect algorithm in a short time was quite difficult. Finally I have realized that you cannot rely on a unique procedure to find the best result, because it will not satisfy any possible combination of differently sized rectangles; so it is reasonable to think that the best way is to use different procedures, or better procedures that inspect the panel in different way (or direction), and then ultimately check the one that is giving the best fit.

The routine

Anyway, all of them need to rely on a recursive routine, because using a simple cycle would make things very difficult to manage.
After deciding the starting point (in our case, let’s say top-left) and the direction (from left to right), the procedure consist in inserting the rectangles recursively, starting from the biggest ones: one of the biggest rectangles is inserted at the top-left, then the remaining space of the panel is divided in two sections (it would be like having 2 new panels to be fitted) and we are going to see if the next rectangle is going to fit in one of them. If not, we pass to the next rectangle (smaller in size) and check for it.
Of course, previously, I had sorted the rectangles in descending order, from the biggest to the smallest.
When a rectangle is too big to fit in the sections, it is left aside for a new check in another panel.
If a rectangle cannot be contained in one panel, then it is split in more panels – or better we are taking pieces of more panels to cover the area occupied by that rectangle.

So, as I said, after fitting one rectangle, the remaining space is divided in 2 ways, like showed in the images: basically, one right area and one inferior area, but with different borders. So I made a routine where the space is divided in horizontal way and a routine where space is divided in vertical way.

dividing_area1   dividing_area2

Every time another rectangle is inserted, the area where is has been inserted is divided again in 2 sections, where we are going check if the next rectangle in our array is fitting. For example, in the next image, where we are performing a division in horizontal sense, we can see the green (new) rectangle is placed in the right area and after that the area is divided in 2 sections: right area and inferior area. In these 2 new areas the routine will try to fit the rest of rectangles.

dividing_area3

A working example of this routine is at the following link: packing rectangles within panels.

Tags:

3 Comments

  1. Anandh Raj says:

    Hey Silvana, it looks like I can use this algorithm. I understand your algorithm but I want to use that algorithm in excel vba. I just need to see your code so that I can understand how you handled four different variables (Rectangle names, length, width and quantities). If you can send me a pseudo code or your program, It would help me use the algorithm in excel vba.

  2. Anandh Raj says:

    I am not getting the idea of how to check individual rectangles and set it aside if it didn’t fit. I am new to coding, so I do not know how to use those sub level arraying. If you can help me that would be great.

    Thanks,

    Anandh

    • silvanasan says:

      Hi, I wrote this function long time ago. Next weekend I will look for the code in my backups and i will let you know, if you are still interested. Let me know if you are still interested.

Leave a reply