RectanglePacking is a utility class to pack smaller rectangles within larger container rectangle efficiently. Built is efficiency in mind, the algorithm can pack 500 rectangles in 1-2ms on a decent computer. The implementation uses the concept of “free rectangles” within the main rectangle. The packed rectangles are always placed in the top left corner of some free rectangle that they completely fit into.

Initially there is only one “free rectangle” that is the main rectangle itself. After packing the first rectangle, the original free rectangle is removed and zero to two new free ones are added. If the packed rectangle is as big as the container there are no more free rectangles. If the packed rectangle is as wide or as tall as the container there is one free rectangle either below or on the right side of it and if the packed rectangle is smaller there is one free rectangle below it and one on it’s right side. The library is especially useful when generating big textures containing many sub textures, which can be used to create a texture atlas, for instance.

Sample

var mScalingBox:ScalingBox = new ScalingBox(BOX_MARGIN, Y_MARGIN, WIDTH - (BOX_MARGIN*2), HEIGHT - (Y_MARGIN + (BOX_MARGIN*2)));
var mPacker:RectanglePacker = new RectanglePacker(mScalingBox.newBoxWidth, mScalingBox.newBoxHeight, padding);

var mRectangles:Vector. = new Vector.();
mRectangles.push(new Rectangle(0, 0, 20, 30));
mRectangles.push(new Rectangle(0, 0, 80, 90));

mPacker.insertRectangle(mRectangles[0].width, mRectangles[0].height, 0);
mPacker.insertRectangle(mRectangles[1].width, mRectangles[1].height, 1);

mPacker.packRectangles();