News Archive
PhpRiot Newsletter
Your Email Address:

More information

aY Optimizing image display using a bin-packing algorithm - Part deux

Note: This article was originally published at Planet PHP on 1 October 2010.
Planet PHP

In the first blog post in this series, I introduced the concept of bin packing and showed how it can be used to optimize the arrangement of an arbitrary group of images so that they occupy the list amount of space possible.

The result, however, is-well, ugly, asAthose who had the guts to give my code a try will have found out. So, good concept, ugly output.

In this second post, I'm going to show you how to improve the quality of the image display and, in the process, we're going to stretch the concept of bin packing a little in order to show that, despite its name, it's not necessarily always about fitting boxes inside a bin.

Images are not boxes

There is a hidden assumption in the very basis of the bin-packing problem that I have not, so far discussed: the fact that all the objects that are to be packed are inflexible1.

This is perfectly normal if you're trying to pack a container full of chairs; images, on the other hand, are not physical objects, and can, therefore, be stretched without any major damage, so long as we (a) don't resample them to a bigger size than the original and (b) we do not change their aspect ratio

By taking advantage of this feature, we could now decide to, say, shrink an image when we cannot find a fit, thus giving our algorithm a better chance at filling the screen. Using such a naAve approach, however, will simply result in an even more grotesque display than the one that came out of the first attempt. This is because our bin-packing algorithm starts from the largest image, which is likely to occupy a large portion of the available real estate; by the time we get to an image that doesn't fit without resizing, we'll have to shrink an already small image, which won't work well.

Stretching in one dimension

What we could do, instead, is to fix the maximum size of an image in such a way as to give them a uniform appearance. This can be easily accomplished by just deciding on a maximum height and then arranging all the images in a row, allowing our page to grow and stretch vertically as the rows get filled optimally.

This, incidentally, opens up a way to simplify our code. Since the height is now fixed, all we really need to do is pack the images horizontally, based exclusively on their width. Thus, we are still solving the bin-packing problem, except that, instead of dealing with two-dimensional objects, we now only have to worry about a single dimension-we are, for all intents and purposes, packing a line segment.

Dealing with a single dimension means that we need to track fewer pieces of data. In fact, as long as the images are packed along the line, we don't really care about their position either-we'll just add them to the horizontal row until it's full, and then move on to a new row.

All in all, what used to be a complex bi-dimensional object whose position and area we were tracking has been reduced to a single, mono-dimensional line segment that is always anchored to a fixed point. This reduces our algorithm to simply tracking the width of each bin; effectively, every time we decide to place an image on a given row, we will just remove a segment from the corresponding bin equal to the image's width.

It's important to keep in mind that, despite the significant simplification to the process, we are still packing bins, which should result in a final arrangement of the images that is as close to optimal as possible (as opposed to, say, just shoving the images one next to the other)2. We have just created some additional constraints that have simplified our algorithm considerably.

Great power, and great separation

With this approach comes an additional consequence that is going to come in very handy in Part 3. The structure that we now use to track the space occupied by each image no longer has any real physical connection with the real estate it represents on the screen. We are tracking a row number and the width that hasn't been used, but, on the screen, we will be drawing bi-dimensional objects that will, in addition to being placed inside some sort of container, have to be arranged so that they are equidistant and properly aligned.

In other words, we have separated the logical representation of a bin from its physical appearance. This means that, given the appropriate set of circumstances, we can now discard the physica

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