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;
}