Flipboard的布局算法

Question

我希望你们中的许多人都能听说过Flipboard.关于这个iPad应用程序最令人惊叹的事情之一就是它根据iPad的方向和基于流媒体内容来布置动态变化的内容.

因此,给定一组文章可以使用哪种算法来获得最佳布局.最佳定义可能是 - 最有效的布局(如电路设计)或最美观的布局.

有谁知道任何这样的算法？或者解决这些问题的基本方法？这属于"计算几何"吗？

Answer 1

基于Jason Moore在他的回答中链接的博客文章中的屏幕截图和理论,我会说有十个左右的预定义块大小放入其中.放置一块内容的大小是基于各种不同的参数 - 许多人转推或喜欢的东西可能被认为是更高的优先级,因此获得更大的盒子,带有图片,视频或大量文本的项目也可以优先考虑.然后将这些框(最好具有深思熟虑的大小)打包在页面上(虽然这不是一个简单的问题,甚至Flipbook似乎也失败了,因为Facebook流的第二次渲染中的奇怪空白来自之前的链接博客文章).

从渲染的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音符的块),而其他模式可以更自由地打包.对渲染的Twitter Feed的类似分析显示了一些额外的框.

摘要

因此,总之,算法看起来相当简单.从一些预定义(合理选择)的盒子尺寸开始.呈现新Feed时,请执行以下操作:

1. 为每个项目分配一个框,其大小取决于某些属性,如受欢迎程度,它包含图像等.
2. 最佳地打包盒子(这实质上是垃圾箱包装问题,一个似乎没有高效算法的NP难问题;贪婪的近似算法会很好)

这里的重点应放在第1步,以及制作预定义的方框.

澄清一下:我在这里谈到的预定义的盒子大小是为纵向定义的.对于风景,将使用一组不同的框尺寸,如问题中的图片所示.

Answer 2

我已经尝试了很多了解flipboard的布局安排.以下是我提出的https://github.com/reefaq/FlipView

它背后没有复杂的算法,也没有复杂的代码,只是一个简单的代码,对所有人来说都是可以理解的.

实现了一些功能

• 多翻(幻觉)
• 如果方向改变像Flipboard那样的视图排列
• 选择随机布局

希望它能帮助你:)

Answer 3

声音与Knapsack算法有关.另请参阅Wikipedia网站打包问题.