algorithm - Flipboard的布局算法

Question

<分区>

Answer 1

基于the blog post linked to by Jason Moore中的截图和理论在 his answer ，我会说有十个左右的预定义 block 大小用于放置内容。将内容放在什么大小的框内取决于各种不同的参数——许多人转发或点赞的内容可能被认为具有更高的优先级，因此得到一个更大的框，带有图片、视频或大量文本的项目也可能被优先考虑.然后将这些框(最好是经过深思熟虑的尺寸)以最佳方式打包在页面上(尽管这不是一个简单的问题，甚至 Flipbook 似乎也失败了，正如先前链接的博客文章中 second render of the Facebook stream 中的奇怪空白所证明的那样).

从rendered Facebook feed的外观来看, Flipbook 具有(至少)以下预定义框尺寸(宽度和高度以全宽/高度的百分比给出):

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

其中一些具有相当明显的分组模式(例如，1/9 引号总是一次堆叠三个以形成与 1/3 音符大小相同的 block )，而其他则可以更自由地打包。 rendered Twitter feed的类似分析显示一些额外的框。

总结

因此，总而言之，该算法似乎相当简单。从几个预定义的(明智选择的)框大小开始。呈现新提要时，执行以下操作:

1. 为每个项目分配一个框，其大小取决于某些属性，例如受欢迎程度、是否包含图像等。
2. 最优地打包盒子(这本质上是 bin packing problem，一个似乎没有有效算法的 NP-hard 问题；贪心近似算法会很好)

此处的重点应放在步骤 1 以及制作预定义框上。

澄清一下:我在这里讨论的预定义框尺寸是为纵向方向定义的。对于横向，将使用一组不同的框大小，如 the picture in the question 所示。 .