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 😉

If you liked this article, you might be interested in my Twitter feed as well.
 
  • http://www.facebook.com/lokesh.dhakar Lokesh Dhakar

    The illustrations go a long way in helping explain the algorithm -- very clear! Thanks for the write-up.

 

Related Posts

  • July 8, 2012 Image Layout Algorithm – Lightbox (1)
    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 […]
  • August 14, 2012 Image Layout Algorithm – Facebook – Reordering (2)
    In this article, we are going to see how to support dynamic updates to Facebook Image Layout Algorithm. Beware, this is not an easy task and there are many special cases to handle :) Making images bigger To make images bigger we just run the algorithm all over again with the new […]
  • April 5, 2012 Climb – Property-based dispatch in functional languages (1)
    ELS Presentation | A Generic and Dynamic Approach to Image Processing | Chaining Operators & Component Trees | Property-based dispatch in functional languages This is the third (and last) presentation about my work on Climb at the LRDE. During the first one I tackled genericity […]
  • June 13, 2012 Project – Tagging Improvement using Face Detection (3)
    The first non-trivial feature I've done at Facebook is now released :) If you have ever tagged an album, you must know the pain it is to go over all the photos and tag everyone. In order to make this process easier, we can make use of image recognition algorithms to find faces. […]
  • May 10, 2012 Generic Image Processing With Climb – 5th ELS (0)
    ELS Presentation | A Generic and Dynamic Approach to Image Processing | Chaining Operators & Component Trees | Property-based dispatch in functional languages Laurent Senta had the opportunity to go to the 5th European Lisp Symposium to present Climb, the project I've been […]