Flipboard的布局算法

发布于 2024-11-14 03:22:17 字数 339 浏览 3 评论 0 原文

我希望你们中的许多人都听说过 Flipboard。这款 iPad 应用程序最令人惊奇的事情之一是它的内容布局方式会根据 iPad 和 iPad 的方向动态变化。基于流媒体内容。

在此处输入图像描述

因此，给定一组文章，人们将使用什么算法来获得最佳布局。最佳的定义可能是 - 最有效的布局（如电路设计）或最美观的布局。

有人知道这样的算法吗？或者解决此类问题的基本方法？这属于“计算几何”吗？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

汹涌人海 2024-11-21 03:22:17

基于贾森·摩尔 (Jason Moore) 在 href="https://stackoverflow.com/questions/6265995/flipboards-layout-algorithm/6393263#6393263">他的答案，我想说有十个左右的预定义块大小可以放入其中被放置。内容放置在多大的盒子中取决于各种不同的参数——很多人转发或喜欢的东西可能被认为具有更高的优先级，因此会得到更大的盒子，带有图片、视频或大量文本的项目也可能被优先考虑。这些盒子（最好是经过深思熟虑的尺寸）然后以最佳方式包装在页面上（尽管这不是一个简单的问题，甚至 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 显示的类似分析一些额外的盒子。

总结

因此，总的来说，该算法似乎相当简单。从几个预定义的（合理选择的）盒子尺寸开始。当呈现新的提要时，执行以下操作：

为每个项目分配一个盒子，其大小取决于某些属性，例如受欢迎程度、是否包含图像等。
以最佳方式打包盒子（这本质上是装箱问题，一个 NP 难题，似乎没有有效的算法；贪婪的近似算法就可以了）

这里的重点应该放在步骤 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:

Assign each item a box whose size depends on certain properties such as popularity, wether it contains images, etc.
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.