Javascript jQuery

Simple packing algorithm – part 1

The problem is quite simple to express : optimizing box packing in a container.

There are tons of solutions, litterature, thesis or reports to be found on the web, but I couldn’t lay my hands on the particular problem I have been needing to solve. It’s fairly basic though – maybe that’s why I can’t find an answer to it ! – so the solution I finally came up with might be too specific to be used in other cases.

This is what I need to do – you’ll see later, perhaps in an upcoming post, why I need to : I have a container with a fixed width, and variable height, I need to pack any number of boxes inside it. To make things a little neater and easier, the boxes will only have 2 diffrent heights – one is twice the other – and the widths will all be a multiple of a given number (the container’s width also being a multiple of this number). I will add the following constraint though : I want as little overlapping as possible, if not any at all. oh, and I also need to pack the boxes filling one row after the other – in other words, the problem has to be entirely solved before I actually start placing the elements. The latter requirement is only because the boxes will eventually end up being simple floating DOM elements, stacked next to each other. I’ll implement with javascript/jQuery for this very same reason.

pack1

Ok, so let’s start simply with boxes of all the same height, as in the above example. The boxes were generated randomly with a choice of 3 different possible widths. As you can see, there’s some rearranging to be achieved. It’s not that much of a mess, and I’m not such a maniac for order, but just for the sake of it, I’ll give it a try.

The structure is something like this :

The basic idea I want to implement, is to start packing with the biggest boxes first, and complete rows with smaller elements if necessary and possible. To avoid overlapping, I’ll use the first row – the top row – as a reference, and try to fit the following rows in the same way.

So, what I need to do first is sort all the elements and store them in an apropriate array.

The main loop would look something like the following – where pack_line is a function that finds the combination of elements that fit a given width. The first row must fit our container, the next rows are split to match the first row.

And here’s for the pack_line function. I’m not exactly happy with it, as it could probably use a good deal of optimizing, but it gets the job done, so I’ll stick to it for now.

Well, we supposedly found our packed solution to the problem, we just need to place the elements accordingly, easily done :

And here’s the result :

pack2

That’s exactly what I was aiming at : nice optimized packing with no overlapping what so ever ! The next step will be to get the same kind of result with elements of various heights… well, as I said in the beginning, only 2 different heights, and one being twice the other, just to keep packing nice and neat.

Leave a comment