(Slowed down adding the rectangles to see the algorithm in action)

## Bin Packing Algorithm

With the bin packing problem, objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used. In computational complexity theory, it is a combinatorial NP-hard problem. The decision problem (deciding if a certain number of bins is optimal) is NP-complete.

The algorithm performs 'discrete online rectangle packing into a rectangular bin' by maintaining a binary tree of used and free rectangles of the bin. There are several variants of bin packing problems, and this packer is characterized by:

• It solves the 'online' version of the problem, which means that when adding a rectangle, there is no information of the sizes of the rectangles that are going to be packed after this one.
• The rectangles packed are not rotated. I.e. the algorithm will not flip a rectangle of (w,h) to be stored if it were a rectangle of size (h, w).
• The packing is done in discrete integer coordinates and not in rational/real numbers (floats).

The bin packing solution is strongly based on the C++ algorithm by Jukka Jylänki. Here is the core part of the algorithm:

``````
function insert( node, width, height )
{
// If this node is an internal node, try both leaves for possible space.
// (The rectangle in an internal node stores used space, the leaves store free space)
if( node.left || node.right )
{
var newNode = null;

if( node.left )
{
newNode = insert( node.left, width, height );

if( newNode != null )
{
return newNode;
}
}
if( node.right )
{
newNode = insert( node.right, width, height );

if( newNode != null )
{
return newNode;
}
}

// Didn't fit into either subtree!
return null;
}

// This node is a leaf, but can we fit the new rectangle here?
if( width > node.width || height > node.height )
{
return null; // Too bad, no space.
}

// The new cell will fit, split the remaining space along the shorter axis,
// that is probably more optimal.
var w = node.width - width;
var h = node.height - height;

node.left = new BinNode;
node.right = new BinNode;

if( w <= h ) // Split the remaining space in horizontal direction.
{
node.left.x = node.x + width;
node.left.y = node.y;
node.left.width = w;
node.left.height = height;

node.right.x = node.x;
node.right.y = node.y + height;
node.right.width = node.width;
node.right.height = h;
}
else // Split the remaining space in vertical direction.
{
node.left.x = node.x;
node.left.y = node.y + height;
node.left.width = width;
node.left.height = h;

node.right.x = node.x + width;
node.right.y = node.y;
node.right.width = w;
node.right.height = node.height;
}

// Note that as a result of the above, it can happen that node.left or node.right
// is now a degenerate (zero area) rectangle. No need to do anything about it,
// like remove the nodes as "unnecessary" since they need to exist as children of
// this node (this node can't be a leaf anymore).

// This node is now a non-leaf, so shrink its area - it now denotes
// *occupied* space instead of free space. Its children spawn the resulting
// area of free space.
node.width = width;
node.height = height;

return node;
}
``````