PhpRiot
News Archive
PhpRiot Newsletter
Your Email Address:

More information

aY Optimized image display using a bin-packing algorithm - Part one

Note: This article was originally published at Planet PHP on 30 September 2010.
Planet PHP

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

At its most basic, the problem is very simple: we receive a bunch of images in input, and we must arrange them in such a way that as many pictures fit in a given space as possible. In other words, we have a bunch of rectangles that need to be placed inside another rectangle in an optimal way.

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 aobin packing problem.a 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 one1. Therefore, we need to find an algorithm that is both efficient and practical.

Solutions

There are a number of solutions to the bin packing problem. The most obvious is to simply take each item as it comes along and shove it in the first available location that's big enough to contain it. This approach (which is how I pack my bags)Ais called aofirst-fita and it is, as you would expect, quite inefficient-in fact, Wolfram MathWorld says that first-fit algorithms can be as much as 70 percent less efficient than an optimal solution.

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)Ais 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 isa 22 percent2!

The problem of aobesta

A big issue at play here is what aobesta means in the context of a best-fit algorithm. The answer to this question is actually quite complex-given the simplicity of the algorithm itself, I'd say it's probably the most difficult part of the puzzle we're trying to solve.

The obvious answer is that a particular space is the aobest fita 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 interesting to note that the first two conditions are necessary in order for the fit to occur at all-if the object is bigger, longer or wider than the space we're considering, it simply will not fit. Therefore, with only those two first conditions we have a first-fit algorithm.

It's the third conditions that fulfills the best-fit requireme

Truncated by Planet PHP, read more at the original (another 7561 bytes)