Rectangle Packing (2D packing)

I’m working on a little thing which I don’t want to speak about just now, lets see if I can get it to do what I want first before making it public. However for that project I needed to pack several small rectangles of varying dimensions into a bigger one without them overlapping.

At first it seem like an easy task but the more I thought about it the more difficult it was. After a bit of research I found out that until today this seems to be a non resolved problem, there are algorithms which offer a pretty decent approximation to the optimal result though. The problem is commonly known as the Bin Packing problem and in this case I needed to work with two dimensional objects (rectangles) so it gets a lot more complicated.

After more googling I found an article by Jim Scott with pseudo code to solve a similar problem, the article explains on how to pack several lightmaps into a single texture. It was the easiest to understand algorithm I had found so I went ahead and implemented it in PHP. I had it in a few minutes but I wanted to fine tune the results by feeding it the rectangles by different sorting criteria, since it seems to be a good way to achieve the best results. Well, I got tired to slowly generating the image in PHP to check the results with every minor variation so I implemented a JavaScript version which allows to see the result in real time.

Here you can see the algorithm implementation or download it below.

/*
Script: RectanglePacker.js
  An algorithm implementation in JavaScript for rectangle packing.
 
Author:
  Ivan Montes <drslump@drslump.biz>, <http://blog.netxus.es>
 
License:
  LGPL - Lesser General Public License
 
Credits:
  - Algorithm based on <http://www.blackpawn.com/texts/lightmaps/default.html>
*/
 
/*
  Class: NETXUS.RectanglePacker
  A class that finds an 'efficient' position for a rectangle inside another rectangle
  without overlapping the space already taken.
 
  Algorithm based on <http://www.blackpawn.com/texts/lightmaps/default.html>
 
  It uses a binary tree to partition the space of the parent rectangle and allocate
  the passed rectangles by dividing the partitions into filled and empty.
*/
 
// Create a NETXUS namespace object if it doesn't exists
if (typeof NETXUS === 'undefined')
  var NETXUS = function() {};
 
 
/*
  Constructor: NETXUS.RectanglePacker
  Initializes the object with the given maximum dimensions
 
  Parameters:
 
    width - The containing rectangle maximum width as integer
    height - The containing rectangle maximum height as integer
 
*/
NETXUS.RectanglePacker = function ( width, height ) {
 
  this.root = {};
 
  // initialize
  this.reset( width, height );
}
 
 
/*
  Resets the object to its initial state by initializing the internal variables
 
  Parameters:
 
    width - The containing rectangle maximum width as integer
    height - The containing rectangle maximum height as integer
*/
NETXUS.RectanglePacker.prototype.reset = function ( width, height ) {
  this.root.x = 0;
  this.root.y = 0;
  this.root.w = width;
  this.root.h = height;
  delete this.root.lft;
  delete this.root.rgt;
 
  this.usedWidth = 0;
  this.usedHeight = 0;
}
 
 
/*
  Returns the actual used dimensions of the containing rectangle.
 
  Returns:
 
    A object composed of the properties: 'w' for width and 'h' for height.
*/
NETXUS.RectanglePacker.prototype.getDimensions = function () {
  return { w: this.usedWidth, h: this.usedHeight };
}
 
 
/*
  Finds a suitable place for the given rectangle
 
  Parameters:
 
    w - The rectangle width as integer.
    h - The rectangle height as integer.
 
  Returns:
 
    If there is room for the rectangle then returns the coordinates as an object
    composed of 'x' and 'y' properties.
    If it doesn't fit returns null
*/
NETXUS.RectanglePacker.prototype.findCoords = function ( w, h ) {
 
  // private function to traverse the node tree by recursion
  function recursiveFindCoords ( node, w, h ) {
 
    // private function to clone a node coords and size
    function cloneNode ( node ) {
      return {
        x: node.x,
        y: node.y,
        w: node.w,
        h: node.h
      };
    }
 
    // if we are not at a leaf then go deeper
    if ( node.lft ) {
      // check first the left branch if not found then go by the right
      var coords = recursiveFindCoords( node.lft, w, h );
      return coords ? coords : recursiveFindCoords( node.rgt, w, h );
    }
    else
    {
      // if already used or it's too big then return
      if ( node.used || w > node.w || h > node.h )
        return null;
 
      // if it fits perfectly then use this gap
      if ( w == node.w && h == node.h ) {
        node.used = true;
        return { x: node.x, y: node.y };
      }
 
      // initialize the left and right leafs by clonning the current one
      node.lft = cloneNode( node );
      node.rgt = cloneNode( node );
 
      // checks if we partition in vertical or horizontal
      if ( node.w - w > node.h - h ) {
        node.lft.w = w;
        node.rgt.x = node.x + w;
        node.rgt.w = node.w - w;
      } else {
        node.lft.h = h;
        node.rgt.y = node.y + h;
        node.rgt.h = node.h - h;
      }
 
      return recursiveFindCoords( node.lft, w, h );
    }
  }
 
  // perform the search
  var coords = recursiveFindCoords( this.root, w, h );
  // if fitted then recalculate the used dimensions
  if (coords) {
    if ( this.usedWidth < coords.x + w )
      this.usedWidth = coords.x + w;
    if ( this.usedHeight < coords.y + h )
      this.usedHeight = coords.y + h;
  }
  return coords;
}

This algorithm can be used for a wide variety of problems, from packaging small sprites in a big image to allocate tasks in complex projects (use the width for the team developers and the height for the time).

A simple usage example could be as follows:

var coords,
    packer = new NETXUS.RectanglePacker( 512, 512 );
 
for (var i=0; i<images.length; i++) {
    coords = packer.findCoords( images[i].width, images[i].height );
    alert( 'Image of ' + images[i].width + 'x' + images[i].height +
         ' allocated at ' + coords.x + 'x' + coords.y
    );
}

I’ve put up a demo so you can try it and see the results with different parameters. Tip: the best results seems to be with the blocks sorted by the magic method and reversed.