(Rectangle) Packing Problem

Introduction

I wondered how to combine rectangles of different sizes inside a larger area while minimizing the amount of space wasted. In technical terms, the problem is referred to as the rectangle packing problem or, in short, the packing problem.
Solving this problem would not only satisfy my curiosity, it also served a practical purpose; I wanted to combine several smaller images, or sprites, into one single image.

Solving the rectangle packing problem reasonably

At first, solving the problem seemed impossible to me, so the journey could have ended by just asking myself the question. However, this didn't happen.
It is not possible to completely solve the problem because of the number of possible combinations. The number of rectangles keeps increasing, so the number of combinations is humongous.

Even with today's computing power, you cannot possibly calculate all the combinations.
If you put all the rectangles in a straight line, the number of combinations increases rapidly.
Ifyou have 3 rectangles, you can combine them in 6 possible ways. Six is the result of 3 factorial (written as 3!) and is calculated as follows: 3 x 2 x 1.
Higher numbers result in much bigger numbers (see table).

Anagram

I figured out that an anagram could help me solving the packing problem.
In an anagram, the letters of a word are re-arranged using all the original letters exactly once. For example, the anagram of my name 'arjan' results in the following combinations:

arjanarjnaarajnaranj arnjaarnajajranajrna ajarnajanrajnraajnar aarjnaarnjaajrnaajnr aanrjaanjranrjaanraj anjraanjaranarj...

Now I use numbers instead of characters. Each (unique) number refers to a specific rectangle.
An anagram based on numbers results in a long list of all the possible combinations in which all the original numbers - read rectangles - are used exactly once.

01234012430132401342 01423014320213402143 02314023410241302431 031240314203214...

The result of the anagram with numbers can be used to find all the combinations in which rectangles can be positioned in a straight line.

Solution

I didn't want to calculate all the combinations of rectangles put in a straight line. The rectangles should be positioned in an area; two dimensions instead of one.
In order to calculate the best possible way to combine rectangles in an area, I needed to find a way to position them.
The first step in the process starts with the first anagram combination.
The first number which refers to a specific rectangle is positioned.

Every positioned rectangle has two possible connection points for the next rectangle; the top right position (A) and the left bottom position (B).
By using more positions per rectangle the number of calculations increases dramatically ,so I chose to use only two positions, which proved to be enough.

The position used is the position which has the lowest calculated surface based on the right bottom position of the newly added rectangle.
The surface of both positions is calculated, the one with the lowest surface is used (in this example the right one).

The position used - in the example position B - is removed from the possible positions and replaced by the right top position of the newly added rectangle. Position B of the newly added rectangle is added to the list of possible positions as Position C.

The position of the next added rectangle is one of the three possible positions A, B or C.
>An extra rule is added to the positioning rule; if the right bottom position of the newly added rectangle is inside the area which encloses all present rectangles, this position is used.

Once added, the possible positions are updated and if a new rectangle needs to be positioned, the whole process is repeated again.
Once all the rectangles are positioned, the overall surface is calculated. Once this is done, the order in which the rectangles are positioned is changed based on the anagram outcome and the whole process is repeated.

As soon as the overall surface of a specific combination is larger than the previously established overall minimum surface, no more rectangles are being positioned, since the outcome is not relevant.
The order in which the rectangles are positioned, is changed again.
At some point, the best possible solution, the combination with the lowest overall surface, will appear.

Some extra features are used - among other things memorization - to speed up the process. But it goes beyond the scope of this small how-to tutorial to explain this feature in detail.

Conclusion

Even though not all the combinations can be calculated and the best found combination with this approach is not necessarily the best possible option, the result is quite good; a solution is found within a reasonable amount of time.