Packing rectangles into a rectangle

published on January 18, 2015 in Tips and Tricksno 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:

Leave a Reply

Your email address will not be published. Required fields are marked *