Layout Algorithms: Facebook | Google Plus | Lightbox | Lightbox Android | 500px

For the redesign of the Photo Section of Facebook we wanted to highlight some photos by making them bigger. It all started with the following mock by Andy Chung:

Layout

Alternated Blocks

My first shot at the problem was to make a fixed layout where we would alternate big images on the left and on the right.

With this scheme, you have one big image every 9. We started brainstorming about putting the one with the most number of likes and comments there. However, this felt to be very arbitrary.

Emily Grewal, the Product Manager of the project wanted something better: being able to make any (and all) image bigger. Automatic selection of images to be bigger was also discarded as we wanted the user to feel in control of this space.

Big and Small Blocks

In the next iteration, I tried to give more control by reducing the size of the blocks. Now it is either one big image or 4 small ones.

One constraint we had at the time was that the columns could start at an arbitrary height. With this layout, we can make the block display: inline-block; and the browser is going to reorder them automatically as the columns initial height are changing.

However, this wasn't all shiny. One nasty side effect is the fact that the ordering of two small blocks next to each other is awkward. Instead of being from left to right they are in zig-zag. You could linearize those but you would lose the layout from CSS.

Smaller Small Blocks

The next (and final) idea is to shrink the small blocks from 4 to 2 elements. It solves our zig-zag issue and feels more natural.

Algorithm

The idea behind the algorithm is to have temporary blocks that serve as buffer. We iterate over all the input elements and put them into the temporary block of the corresponding size. Once a temporary block is full, we add it into the grid in the smallest column.

Here's an example where we try to layout AbcdEf:

And there's the pseudo-code implementation of the algorithm:

function layout(elements) {
  var columns = [new Column(/*height */ 0), new Column(/*height */ 0)];
  var stash = [];
 
  elements.forEach(function (element) {
    if (element.isBig()) {
      var column = columns.getSmallestColumn();
      column.renderBigBlock(element);
      column.height += 2;
 
    } else /* element.isSmall() */ {
      stash.push(element);
      if (stash.length === 2) {
        var column = columns.getSmallestColumn();
        column.renderSmallBlock(stash[0], stash[1]);
        column.height += 1;
        stash = [];
      }
    }
  });
 
  if (stash.length > 0) {
    var column = columns.getSmallestColumn();
    column.renderSmallBlock(stash[0], stash[1] /* can be undefined */);
    column.height += 1;
  }
}

Conclusion

Check out the Demo!

This is the layout algorithm we ended up using for Facebook photos. We found a way to let the user make all the images he wants bigger minimizing the risk of the result being ugly.

Pros:

  • Can make any/all image bigger
  • No holes
  • Order is mostly respected
  • Need to store only two sizes per image

Cons:

  • All images have the same dimension
  • Cropping required to display both landscape and portrait images
  • Only works for a number of column that is a multiple of 2

If you want to know how reordering works, read the follow-up article ๐Ÿ˜‰

Layout Algorithms: Facebook | Google Plus | Lightbox | Lightbox Android | 500px

Google Plus has a really nice image gallery. They somehow managed to display all the photos without cropping, without reordering and without any holes. We are going to see how they did it in this blog post.

How does it work?

Here we have three images with various sizes and aspect ratio and we want to display them in the page. The layout algorithm is the consequence of one clever trick: all the images of the same row are have the same height.

So the only unknown is H, the height of the row given the three images we want to show. Using some basic math, we can solve the problem!

So now we know how to calculate H, the height of all the images. Since we want to keep aspect ratio, we can also calculate their width. As you can see, it is trivial to generalize the operation to n images.

How many images?

Now the tricky part is to decide how many images we want to put in the row. I came up with a solution that gives similar results to Google Plus but I'm not 100% sure that's how they do it.

One fact you can observe is the fact that few images leads to a huge row while many images lead to a small row.

So the idea is to try adding one image at a time and have a threshold for the maximum height we want. Once the row is smaller than this threshold, we render it!

Conclusion

Check this other article to find where best to place the breaks.
Check out the Demo! Here's a little Pro/Con to know if this technique will fit your needs.

Pros:

  • No cropping
  • No reordering
  • No holes
  • Arbitrary Width

Cons:

  • Portrait images are much smaller than landscape ones
  • All the rows do not have the same height
  • The view feels a bit chaotic with no clear structure
  • Requires dynamic resize of images

Some other implementations I found on the internet:

Layout Algorithms: Facebook | Google Plus | Lightbox | Lightbox Android | 500px

Lightbox.com has a really interesting image layout algorithm. We're going to see how it works and its best use case.

How does it work?

Column based

The algorithm is column based. You pick a number of columns at the beginning. Then every time you want to layout an image, you just place it to the smallest column.

Some facts about this layout: All the images here have the same width. The order is not particularly respected. The end of the stream is not properly aligned.

Bigger Images

The interesting part of Lightbox layout is the ability to make some images bigger. When you are about to layout an image, you look at the height of the neighbor columns. If the column has the same size, then you can to extend the image to take the width of both columns.

Beating the Odds

Having two adjacent columns with the exact same size is rarely going to happen in practice. In order to solve this situation we are going to cheat a little. We draw an invisible grid and every time an image doesn't perfectly align with the grid, we crop it to the nearest line.

The bigger the grid is, the more opportunity you will have to make bigger images but at the same time, the more you will crop your images.

When to make images bigger?

This might be counter intuitive but you don't want to make images bigger every time the opportunity present itself. Every time you make an image bigger, it is going to preserve two adjacent columns of the same height. If you keep adding bigger images on top of those two column, you essentially created a column that has twice the width.

Using a column based layout implies that landscape images are much smaller than the portrait ones. In order to restore balance, Lightbox uses the following heuristic. If the image is landscape, then it has 60% chance to be made bigger, only 10% when it is a portrait.

Conclusion

Check out the Demo!

This layout is very good for random collection of images in an infinite stream. Here's a little Pro/Con to know if this technique will fit your needs.

Pros:

  • Can make some images bigger
  • No holes
  • Need to store only two dimensions per image
  • Arbitrary number of columns

Cons:

  • Landscape images are much smaller than portrait ones
  • Images that can be bigger is very arbitrary
  • Small cropping
  • Order is not respected
  • End of stream is not well aligned

Some other implementations I found on the internet:

In this article, I'm going to guide you through a concrete problem I had to solve. Eventually, we'll see how to use percentage values in the background-position CSS property and how it solves a lot of tough issues.

Usual way

Positioning the image

The usual way to position images inside a container is to specify where the top left of the image is going to be compared to the top left of the container.

Both are really easy to implement in CSS. On the left you can see the code using a <img> tag inside a container, the other one is a container with a background-image attribute.

.container {
  position: relative;
}
 
.container img {
  position: absolute;
  top: 12px;
  left: 20px;
}
.container {
  background-position: 12px 20px;
}

Moving inside container

Now let's say you want to be able to drag the image inside the container and make sure it doesn't go outside of the bounds. You are going to start doing some basic maths to compute the maximum values for top and left.

The left position is going to go from 0 to container_width - image_width. Apply the same formula to calculate the maximum top position.

Image is bigger than container

So far so good. Now let's say our image is bigger than the container. We're going to extend our definition of inside the container. All the container must be filled with the image.

Again, using simple math we can compute the bounds of the left offset. Again, it is 0 and container_width - image_width. Except that container_width - image_width is negative this time.

You are now going to handle positive and negative values. The values now also get really counter intuitive. When you see 12px 20px you have a rough idea of how the image will be positioned. -12px -20px is really harder to conceptualize.

Invariants

So great, now you have written all your reposition interface and have stored the perfect position the user entered. Now, for some reason, instead of a rectangular container, you want a square one. You are in a not so comfortable position.

The values we computed can no longer be used because they no longer have the same meaning. The within bound constraint no longer holds true and the position is completely off. It is the same if you attempt to scale the image and container.

Background Image Percentage

Definition

Instead of using the previous definition of the image position, we can use another one. When the left border of the image is on the left border of the container, left is equal to 0%. When the right border of the image is on the right border of the container, left is equal to 100%.

Here's what the two values 0% and 100% looks like in the two examples:

To find the intermediate steps, we just do a linear interpolation between the two values.

left = (container_width - image_width) * percentage

Bound check

The first obvious advantage is that we no longer have to do math to compute if an image is within the bounds of the container. It is if and only if the value is between 0 and 100.

Invariants

Another way to think about this positioning is to draw two axis, one for the image on for the container. If we set the value to be 60%, then the position is going to be where the 60% mark on the two axis is the same point.

As you can see, this new definition works well with different ratios and scaling.

Horizontal and Vertical

If you pay close attention, you notice that if the image is the same size of the container, the value is ignored. The two axis will be perfectly aligned so all the points will match. Setting 30% or 80% doesn't matter.

If you don't believe the picture, just look at the math.

left = (container_width - image_width) * percentage
left = 0 * percentage
left = 0

The takeaway here is that you need the user to set two values. One when the image is going to scroll vertically. One when the image is going to scroll horizontally.

Conclusion

At first, I didn't understand how percentage values for the background position were working. I was really confused because this is not the way intuitively you would have used percentage.

However, once I tried to implement a robust reposition tool, I realized that this definition of percentage was convenient. It solves in an elegant way many of the issues we had with the usual positioning method.

I hope that you learned something here ๐Ÿ™‚