Javascript jQuery

Simple packing algorithm – part 2

In the previous post, I exposed my solution to a simple packing problem. I’m going to mix things up a little now by adding 2 different possible heights to the boxes I want to pack in the container.

As I did previously, I’m going to generate a random sequence of boxes to work with, this is my sample :


If I try to apply the previous algorithm for simple heights, it won’t do, of course. Just for curiosity, though, this it what I end up with :


The blocks are disaligned because they’re floating to the left. For example, the 3 short and fat elements towards the bottom right should actually be aligned on the left, just underneath the long one… well that’s not the only issue, they’re probably find themselves placed elsewhere in the end, so there’s no need to worry about that right now.

Basically, what I’m going to do to handle the diffrent heights is double all my arrays first, so that I can make the difference. I actually add an extra index, so those arrays could be extended to any number of heights.

For example, the sorting algorithm would change in the following way :

As you can see, the arrays are now indexed with [h], which is the height of the element.

The pack_line function doesn’t change either except that the arrays are, again, indexed with the height. I use a global variable ht for this matter, containing the current height of the elements I’m processing.

The major evolution is to be found in the main loop. I need to consider packing on two lines instead of one, as soon as I run out of fat blocks. Well, that is if the row has already started being packed with at least a fat block. On a new row, I’ll just pack normally, but with thinner blocks. The very first row is treated separately as it serves again as a reference for alignment of all the other. I’m not going to give more details, but you have the idea. As I’m writing, it occurs to me that the process is much too specific, and I’d have a hard time extending to any number of possible heights. I’m guessing I’d have to use some kind of recursive function, maybe I’ll explore that sometime.

The main loop :

As you might guess, I’m not very happy with this, but once again, it gets the job done.

The final operation, consisting in placing the elements, requires some specific processing again. I need to create sub-containers when aligning 2 thinner rows to a fat one. I’m not sure there’s a better way to get floating elements to align properly. This is the code I came up with to do so :

And finally, here’s the result, which fullfills my expectations, even though I’m not pleased with the algorithm. Well, there’s a flaw I can see already : I start packing with the fat elements, but what if they’re all short ? My first row is used as a reference, so that can’t do ! This and the possible use of a recursive function to extend to more general cases make me consider re-designing the whole program. Some other time, maybe…


As I now have a pratical way of solving my problem, I’ll most likely show you next time, what it was all intended for…