# (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).

number of rectangles |
number of combinations |

1 | 1 |

2 | 2 |

3 | 6 |

4 | 24 |

5 | 120 |

6 | 720 |

7 | 5.040 |

8 | 40.320 |

9 | 362.880 |

10 | 3.628.800 |

11 | 39.916.800 |

12 | 479.001.600 |

13 | 6.227.020.800 |

14 | 87.178.291.200 |

15 | 1.307.674.368.000 |

16 | humongous |

## 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.