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.

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 :

1 2 3 4 5 6 |
<div id="container"> <div class="box" id="box-0"></div> <div class="box" id="box-1"></div> <div class="box" id="box-2"></div> ... </div> |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
var divs = new Array(); //an array containing the jQuery objects var elems = new Array(); //an array containing indexes of the divs array sorted by element widths var widths = new Array(); //an array containg the different widths $('#container div.box').each(function(index) { divs.push($(this)); wi = $(this).outerWidth(true); if (!elems[wi]) elems[wi] = new Array(); elems[wi].push(index); if ($.inArray(wi,widths)<0) { k=0; while ((k<widths.length) && (widths[k]>wi)) k++; widths.splice(k,0,wi); } }); |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
nbleft=divs.length; lines[0] = pack_line(container_width); nbleft -= lines[0].length; line=1; tmp = new Array(); while (nbleft>0) { lines[line] = new Array(); for(i=0;i<lines[0].length;i++) { tmp = pack_line(divs[lines[0][i]].outerWidth(true)); for (k=0;k<tmp.length;k++) { lines[line].push(tmp[k]); } } nbleft -= lines[line].length; if (lines[line].length==0) nbleft=0; line++; } |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
function pack_line(availablewidth) { var sum = 0; //current occupied width var iix = 0; //index of the widths array var exit = false; //exit loop flag var retlist = new Array(); //return array var ptest = true; //test smaller elements flag while (!exit) { //we covered all possible widths, so exit the loop if (iix>=widths.length) { exit=true; } else { //does the next element fit the space if ((sum+widths[iix]) <= availablewidth) { //max is the next biggest element if (elems[widths[iix]].length>1) max=widths[iix]; else if (iix<(widths.length-1)) max=widths[iix+1]; else max=0; spaceleft=availablewidth-sum-widths[iix]; //space left after we try fitting the current element //if an element fits exactly the space left, we're done ! if (((ind=$.inArray(spaceleft,widths))>=0) && ((iix!=ind) || (elems[widths[ind]].length>1))) { w1 = widths[iix]; w2 = widths[ind]; retlist.push(elems[w1].splice(0,1)[0]); retlist.push(elems[w2].splice(0,1)[0]); if (elems[w1].length==0) { widths.splice(widths.indexOf(w1),1); } if ((w1!=w2) && (elems[w2].length==0)) { widths.splice(widths.indexOf(w2),1); } exit=true; } //nothing fitted, but maybe if we try a smaller current element else if (ptest && (spaceleft>0) && (max>=spaceleft)) { iix++; if (iix>=widths.length) { iix=0; ptest=false; } } //well, no combination was found, so loop from begining again else if (ptest && (max==0)) { iix=0; ptest=false; } //place the current element in the row else { w1 = widths[iix]; retlist.push(elems[w1].splice(0,1)[0]); sum += w1; if (sum==availablewidth) { exit=true; } if (elems[w1].length==0) { widths.splice(widths.indexOf(w1),1); } } } else { //the element is too big so jump to the next smaller one iix++; } } } return retlist; } |

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

1 2 3 4 5 6 |
$('#container').html(''); for (i=0;i<lines.length;i++) { for (j=0;j<lines[i].length;j++) { $('#container').append(divs[lines[i][j]]); } } |

And here’s the result :

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.