⇥ Optimized image display using a bin-packing algorithm – Part one

I am currently working on a project that requires (among other things) the ability to display a series of images, whose size is unknown at design time, in such a way that as many of them are visible on the screen at any given time.

This is an interesting problem for a number of reasons: first, the solution can be applied to a number of different problems that have nothing to do with images; second, a little tweaking makes this problem a great gateway to building a cool image-display system; and third, it is a very simple—but very impressive—example of how math doesn’t have to be hard to be useful.

I’ve broken this post in three parts: in the first one, I will mostly focus on the problem and its solution; in the second, I will worry about making adjustments to guarantee the best possible solution; and in the third, I will make things look good.

The problem: packing bins

This is not unlike the problem that one faces when packing a bag—the solution, in that case, is to start with the big, bulky items and then fit the smaller objects in the nooks and crannies until no more objects can be placed and you reach for a new piece of luggage over the loud complaints of your spouse. We have to do the same thing—only in two dimensions instead of three.

As it turns out, this is a very well research problem that is usually referred to as the “bin packing problem.” It applies to a large number of very practical scenarios that vary from the obvious (packing a container full of IKEA furniture so that as little unused space as possible is left on a ship or truck) from the esoteric, like defragmenting a hard disk.

Despite its simple premise, the optimal solution to this problem is impossible to find without essentially going through all the possible permutations and checking the individual efficiency of each one¹. Therefore, we need to find an algorithm that is both efficient and practical.

Solutions

But let’s go back to the problem of packing a bag or a trunk: you start by putting all the objects in front of you, mentally separating the big ones from the small ones. Next, you pick the largest object and place it in bag in the best possible position (say, the top-left corner), continuing in this fashion until you either have no more objects to fit or no more space to fit them into.

Interestingly, this intuitive—or heuristic—solution (called best-fit) is very efficient: math proofs have demonstrated that it varies, at most, by 22 percent from an optimal arrangement, which other math proofs has shown is the maximum theoretical efficiency that can be guaranteed by a heuristic solution is… 22 percent²!

The problem of “best”

The obvious answer is that a particular space is the “best fit” for a given object if, and only if:

• Its area is at least the same, or bigger than the object
• Its width and height are at least the same, or bigger than those of the object
• The difference between its area and the area of the object is less than or equal than the difference between the object and any other available space in the bin

It’s the third conditions that fulfills the best-fit requirement by imposing a requirement that is not necessary for a fit to occur. Luckily, the area is a good measure of efficiency if the relationship between the height and width of the bin is relatively close to one; in other cases, you will have to use different way of measuring the “best fit.” For example, if you are fitting into a bin that has one infinite dimension (say, the height of a page that can scroll indefinitely), then it’s much better to measure the efficiency of a fit based on the relationship between the width of an object and the width of the bin³.

The algorithm in practice

1. Sort out all the available images in descending order of area
2. Let bins be an array of bins containing a bin whose width and height are the same as the client area to fill
3. For each image:
   1. Let bestBin be null
   2. For each bin in bins:
      1. If the bin is the best fit for the image, let bestBin equal the current bin
   3. If bestBin is not null
      1. Position the image in the top-left corner of bestBin
      2. Create two new bins from the unused portions of bestBin and add them to bins
      3. Remove bestBin from bins

As you can see, for the purposes of our algorithm there is no difference between a “bin” and a “space inside a bin.” Any amount of available space is considered a bin and added to the bin array for reuse.

The algorithm in code

The images are loaded into an object of the class Boxer (I know, I’m great at naming things), where they are then run through our packing algorithm:

protected function fitImagesInClientArea():void {

	// Create the main bin

	var bins:Array = [new Bin(0, 0, width, height)];

	// Sort the images

	boxes.sort(function(a:Box, b:Box):int {
		if (a.area > b.area) {
			return -1;
		}

		if (b.area > a.area) {
			return 1;
		}

		return 0;
	});

	// Iterate through each image, finding the best possible
	// bin for it based on its area.

	for each (var box:Box in boxes) {
		var bestFit:Bin = null;

		for each (var bin:Bin in bins) {
			if (bin.width > box.width && bin.height > box.height) {
				// The box fits in the area of the bin. But is
				// it a better fit?

				if (!bestFit || (bestFit.area - box.area > bin.area - box.area)) {
					bestFit = bin;
				}
			}
		}

		if (bestFit) {

			// Position the box in the bin and add it to the screen

			addChild(box);

			box.left = bestFit.x;
			box.top = bestFit.y;

			// Split the bin to reclaim any unused space

			bins.push(new Bin(bestFit.x + box.width, bestFit.y, bestFit.width - box.width, box.height));
			bins.push(new Bin(bestFit.x, bestFit.y + box.height, bestFit.width, bestFit.height - box.height));

			bins.splice(bins.indexOf(bestFit), 1);
		} else {
			trace("Unable to fit box with width: " + box.width + " and height: " + box.height);
		}
	}

}

Note that the Bin class is little more than a rectangle (in fact, later on we will replace it with the built-in flash.geom.Rectangle). You can download the entire (working) project from GitHub (tag raw-fit for this version) and try it out yourself—or you can also give it a try online.

Problems that need solving

As you can see if you give it a try, this algorithm works—but the results look depressingly ugly. In particular, there are a number of issues to take care:

• The images are all squished together, so that the unused space is not evenly distributed.
• If an image can’t fit, it’s simply discarded. In practice, this is unacceptable.
• The images are not presented in a visually enticing way
• The code cannot deal with more than eight images (which is the maximum that Google will return at one time)
• The code cannot deal with images as they are being loaded (in other words, it needs to know the dimensions of every image in order to apply the algorithm to them)