Flipboard’s layout algorithm [closed]

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, argu开发者_JS百科ments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. Closed 11 years ago.

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" ?

---

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.

---

I had tried a lot with understanding the layout arrangement of flipboard. Here is what i had come up with https://github.com/reefaq/FlipView

There is no complex algorithm behind it nor a complex code, just a simple code which can be understandable for all.

Implemented some of the features like

• multi flip (illusion)
• Views arrangement if orientation changed like Flipboard
• selection of random layout

Hope it helps u :)

---

Sounds related to the Knapsack algorithm. See also the Wikipedia site packing problem.

---

I was unable to post images because of low reputation karma :-) but here are some notes as a blog post about the layout method.

---

Have a look at this JavaScript Library. Seems interesting

http://masonry.desandro.com

The (0,1) - knapsack approach.

---

I imagine that a greedy algorithm would work just fine. It just depends on the order in which you try to load the data. if you give each section of content a weight or "value", and give it a large amount to pick from, the greedy algorithm can find the optimal layout with the highest value.

Greedy Algorithm

---

My hunch is that the streaming content is sorted into different categories (quotes, articles, photos, etc.). Based upon how many items are in each category and the ranking of each of the items in those categories, the software probably places them into some pre-made layouts.

The following blog entry shows a lot of in depth analysis trying to decipher the Flipboard's dynamic layouts:

Replicating Flipboard Part III – How Flipboard lays out content