Flipboard’s layout algorithm

Question

I hope many of you would have heard about Flipboard. One of the most amazing things about this iPad app is the way it lays out the content which changes dynamically based on orientation of iPad & based on the streaming content.

So given a set of articles what algorithms would one use to have the best layout. The definition of best could be - most efficient layout (as in circuit design) or the most aesthetically looking layout.

Anybody know of any such algorithms? or the basic approach to such problems? Does this fall under "computational geometry" ?

Answer 1

Based on the screenshots and theories in the blog post linked to by Jason Moore in his answer, I would say that there are ten-or-so predefined block sizes into which content is placed. What size box a piece of content is placed in is based on various different parameters — something that many people retweet or like may be considered higher priority and therefore get a larger box, and items with pictures, videos or lots of text may also be prioritized. These boxes (preferably with well thought-out sizes) are then packed optimally on the pages (though this is not a simple problem, and even Flipbook seems to fail as evidenced by the strange whitespace in the second render of the Facebook stream from the previously linked blog post).

From the looks of the rendered Facebook feed, Flipbook has (at least) the following predefined box sizes (width and height given as percentage of full width/height):

Designation | Width | Height | Example                         
---------------------------------------------------------------
full page   | 100%  | 100%   | #12                             
2/3 page    | 100%  | 67%    | #1                              
1/3 note    | 50%   | 33%    | #3, #11                         
1/9 quote   | 50%   | 11%    | #2, #8, #10, #15, #17, #18, #22
1/2 note    | 50%   | 50%    | #16, #19                       
2/3 note    | 50%   | 67%    | ?

Some of these have fairly obvious grouping patterns (1/9 quotes are always stacked three at a time to form a block the same size of a 1/3 note, for example), while others can be more freely packed. Similar analysis of the rendered Twitter feed show some additional boxes.

Summary

So, in summary the algorithm appears to be fairly simple. Start with a couple of predefined (sensibly selected) box sizes. When new feeds are rendered, do the following:

1. Assign each item a box whose size depends on certain properties such as popularity, wether it contains images, etc.
2. Pack the boxes optimally (this is in essence the bin packing problem, an NP-hard problem for which there appears to be no efficient algorithms; a greedy approximation algorithm would do fine)

Emphasis here should be put on step 1, as well as on crafting the predefined boxes.

To clarify: The predefined box sizes I talk about here are defined for the portrait orientation. For landscape, a different set of box sizes would be used as evidenced by the picture in the question.