⇥ Optimizing image display using a bin-packing algorithm – Part deux

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, as those 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

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 naïve 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

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)². We have just created some additional constraints that have simplified our algorithm considerably.

Great power, and great separation

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 physical representation of a row and reconstruct it without any loss of information from the logical data that we have saved. We are not quite there yet, because we are not quite tracking which images we are placing in a particular bin.

In Part 3, we will extend this concept (which separates the model from the view and is at the basis of a model-view-controller architecture) in such a way that we will be able to infinitely extend our real estate vertically while only ever loading as many images as necessary to fill our screen, thereby saving considerable amounts of memory and providing a fast and precise scrolling experience.

May the best fit win

There are two possible solutions here. The first is to perform a complete layout every time an image is added or removed from the list. This always gives us a best-fit optimization, but it has two significant drawbacks: it’s computationally intensive (especially once we have a lot of images to deal with) and it is likely to move existing images around to pack more efficiently, thus confusing the user, who will see things move without their input.

The second solution is to pack each group of images that are downloaded independently of the others, adding a new group to the previous one. This approach has the advantage of being computationally efficient and of avoiding to move images without the user’s intervention, but also the drawback of being only locally efficient—the end result will be a layout that will be less optimized than if we had had all the images from the very beginning. Alas, beggars can’t be choosers, but that’s a problem that we’ll deal with in Part 3.

The code, part deux

protected var binContainer:Array = [];

protected function getBinContainerAtIndex(index:int):HBox {
	while (index >= binContainer.length) {
		var hbox:HBox = new HBox();

		hbox.percentWidth = 100;
		hbox.height = 150;
		addChild(hbox);

		hbox.addChild(safeSpacer());

		binContainer.push(hbox);
	}

	return binContainer[index];
}

As you can see above, we keep an array of row containers (which we don’t currently use, but will in Part 3), which are just properly-size and styled HBoxes. The getBinContainerAtIndex() method grows this array as needed—thus giving us the beginning of our bottomless page display.

Finally, our fitImagesInClientArea() method also has to change to reflect our new packing strategy:

protected function fitImagesInClientArea():void {

	// Create the main bin

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

	// Sort the images

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

		if (b.width > a.width) {
			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) {
				// The box fits in the width of the bin. But is
				// it a better fit?

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

		if (bestFit) {

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

			var hbox:HBox = getBinContainerAtIndex(bestFit.rowNumber);

			hbox.addChild(box);
			hbox.addChild(safeSpacer());

			// Reclaim any unused space
			bestFit.width -= box.width;
		} else {
			trace("Unable to fit box with width: " + box.width + " and height: " + box.height);
		}
	}

}

Here, we have changed the Bin implementation to only track the row number and a width⁴, and the packing algorithm has become similarly simpler—in fact, the bin-splicing operation now only consists of removing the width of the new image from the overall width of the bin.

The results, compared to the Part 1 attempts, are dramatically better. You can try it for yourself, and take a look at the current code in the mono-packing tag of the GitHub repo for the project.

⇥ 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)

⇥ Of paper and electrons

On Twitter, Clay Loveless, who seems to be having a particularly bad day (or maybe he just plain doesn’t like me), has taken issue with the way we price our books. This seems like a good opportunity to explain how we do it, and why.

What is that you’re buying, anyway?

When you “buy” a book, my assumption has always been that you are interested in the contents of the book, rather than the form it comes in. Therefore, “buying a book” really means “licensing the content.” If the content comes on paper, then the paper is simply the medium on which the content is transferred.

When I price a book, therefore, I start by deciding how much we need to charge for the content. That is the money that I want to make from my license of the content to you.

The cost of knowledge

It’s that simple. In fact, if a customer buys the print version of a book, I’m happy for them to download the electronic version as well, at no extra charge.

The sum of all things

Now, you can say that our books are expensive. Perhaps they are. But at least I feel pretty good about the way we determine our pricing.

⇥ LLCs are a good idea, but you can still get sued

On his blog, Joe Stump says that opening your own limited liability company (LLC) is a great way to protect yourself and your assets from unwanted legal attention when you segregate your side projects into it.

He is, of course, absolutely right. An LLC creates a separate legal person for third parties to enter into agreement with without all the complexities of owning and running a corporation. If one of those third parties decides to sue, they’ll have to initiate legal action against the LLC, protecting you and your assets.

If you do decide to open an LLC, however, there are a few things that you need to be aware of.

Note: I am not a lawyer, so take these notes as very high-level and not necessarily accurate. If you are a lawyer and spot inaccuracies, please comment so that I can take care of them.

1. The LLC is a separate person

Piercing the corporate veil is a very difficult thing to do (as it should be), provided that you treat the LLC as a separate person.

In practice, this means that you must conduct the affairs of the LLC separately from yours, establishing that, when you are acting on behalf of the LLC, you do so in the LLC’s best interest as it is your fiduciary duty. This means taking care of a few formalities, like keeping your business license current, opening separate bank accounts and, especially, avoiding commingling your personal funds with the company’s. It also means that you cannot use the company as a shield to commit fraud, and so on, and so forth.

So, no treating the LLC as your personal piggy bank. Make sure you record all financial transactions, and always act in the best interest of the LLC, and not your own.

2. Get a lawyer

There are a couple of reasons for this. First, unlike a service, the lawyer will be able to offer you some advice on whether an LLC is the right thing for you, as well as give you some basic guidance on how to ensure that you run the LLC properly. Second, should you ever get in front of a judge, it looks good if you show that you make it a practice to refer legal works to those who are expert in the field, rather than taking matters into your own hands, not to mention that, if the lawyer screws up, you can go after his or her insurance.

Oh, a final piece of advice: I often hear people complain about lawyers as if they were the scum of the Universe—they’re ignorant, lazy, stupid, greedy, evil… take your pick. That is, in my experience, the best way to ensure that the relationship with your lawyer will be unproductive and expensive.

Lawyers are experts in the law—a field that is often illogical and difficult to understand for the lay person. Which, incidentally, is exactly what non-techies say of programming. So, find a lawyer you can work with and make sure that your relationship is based on mutual respect.

3. Get an accountant

That’s not to say that you need an audit, but it’s always good to get a CPA to double-check your calculations. And, once more, there’s another insurance that you can collect from if they screw up.

4. You can still get sued

Nothing prevents any person from suing your LLC or you personally and, since the legal system works on default, you will have to spend the money to defend that lawsuit, no matter how frivolous.

What the LLC does is to provide you with protection from the results of a legal action. A determined party with deep pockets will still be able to take you to court in an attempt to pierce the corporate veil, make you spend considerable amounts of money and, generally speaking, eating a ridiculous amount of your time for a number of years. Having an LLC in place, provided you’ve behaved properly, will eventually protect you from the consequence of an action, but the process that gets you there will still be long, stressful and extremely expensive. That’s where having a good relationship with your lawyer will come in handy.

⇥ Apple has made pigs fly

What started as a rather ordinary day has turned into a rather extraordinary one, at least for those of us who dip their feet in the world of Apple. The company’s announcement that it is relaxing a number of its App Store policies while publishing the very rules that it uses to decide whether an app can cut muster represents a massive shift in the way the Fruit folk interact with their developer ecosystem.

John Gruber and Jason Snell have already written excellent analyses on what the changes mean from many different perspectives, but I think there are a few more things that can be said.

The tone