algorithm - 打包正方形和矩形的算法是什么？

Question

类似Windows 8 Slate的界面，如何在不留空洞的情况下用正方形和长方形漂亮地填满屏幕？

假设:

• 一个矩形基本上是两个相连的正方形
• 矩形可以是水平的也可以是垂直的
• 屏幕宽度是正方形宽度的3倍
• 屏幕从上到下填满
• 这样屏幕的最低部分可能不会完全对齐
• 矩形和正方形的顺序是随机的(但可以在小缓存中重新排序，然后再放到屏幕上，缓存大小是有限的，比如 12)

例如:

  +---++---++---+
  |   ||   ||   |
  +---++---+|   |
  +---++---+|   |
  |   ||   ||   |
  +---+|   |+---+
  +---+|   |+---+
  |   ||   ||   |
  +---++---++---+
  +--------++---+
  |        ||   |
  +--------+|   |
  +---++---+|   |
  |   ||   ||   |
  |   |+---++---+
  |   |
  |   |
  +---+

Answer 1

我相信这是 Packing Problems 的一个子集.

解决这个问题的一种算法是使用 Linear Programming .

定义确保矩形不重叠的约束，然后解决这个问题。然后对算法进行加权以支持屏幕的上/左角和最窄的宽度/高度。还要对算法进行加权，以支持间隔出更大的矩形。

由于您有目标屏幕分辨率，您可以添加宽度和高度的约束，如果算法无法找到解决方案，则放宽高度约束。

不过，这是相当重量级的。您可能会使用不太健壮的算法来简化问题，但仍然会得到不错的结果。例如:

Take items in order of display preference
Start at the top-left
For each item:
    Try to stack horizontally, going right ("favoring" left)
    if it won't fit on the screen:
        try to stack on the next row
        when trying to stack on the next row:
            if any "gaps" exist in the current row:
                see if you have a less "regular" rectangle that will fit in the gap
            else
                "favor" placing it farther left

编辑:

我在发布此答案后阅读了您现有的限制条件。

矩形具有相同尺寸的事实可能会让您优化问题 - 例如使用位数组和索引而不是一些基于树的空间容器。

它可能会让你走捷径和特殊情况下某些决定 - 例如放置所有 1x1 的正方形，然后放置双倍高的位移正方形，然后放置双倍宽度的位移正方形和矩形。反之亦然，因为拟合较小的矩形总是比拟合较大的矩形更容易。只需确保以可能令人赏心悦目的/有点随机的方式隔开大矩形，并首先计算音量，这样您就不会强制滚动，而不必发生这种情况。