多图放置算法 - 拼贴算法

Question

我正在创建一个应用程序，可以同时显示多个视频（比如2-10个视频）。我需要一种算法来帮助在屏幕上放置这些视频。问题在于每个视频可能具有不同的宽高比，因此我需要调整视频大小以使其适应屏幕。但是我希望以一种方式调整大小和适应屏幕，从而最大化屏幕的利用率（并最小化宽高比失真）。另外，我希望用户能够增加一个或多个视频的大小，以便在屏幕上占据更多空间。因此，该算法应该是稳定的，即扩大一个视频不会使所有的放置位置都跳动。

我以一种与语言无关的方式提出这个问题，事实上，使用视频并不重要，这个问题同样适用于静态图像。

那么，有人知道一个放置算法吗？

为了更好地说明，这里举个例子。我有三个视频，大小如下。我希望第一个视频大约占据屏幕的50％，后面两个视频大约占据屏幕的25％。

(464, 336) 50%
(624, 480) 25%
(608, 336) 25%

我该如何将它们放置在屏幕上(1024x800)以实现这个目标？我想先将屏幕分成两半，然后最好的方式是将第一个视频放在上半部分。然后我会将下半部分分成两个，并尽力适应剩余的两个视频。谢谢！

- bramp

---

你为这个例子提出的解决方案有一个问题，如果用户决定将第一个视频恢复到正常大小并放大底部的视频呢？如果你反过来使用相同的布局，视频会跳来跳去，失去“稳定性”。 - Matti Virkkunen

是的，我的建议很简单但不太好。我希望有一种经典算法来解决这种放置问题，而且不是 NP 难的 :) - bramp

这很容易成为面试测试中的一个问题。 - nessence

只是一个简短的评论，它并不是 :) 只是我的个人小项目，我想找到可以解决这个问题的算法类。 - bramp

我认为新的Google图片处理类似的事情（除了调整大小部分）。 - Lazer

Answer 1

我认为你可能需要一个树状图。这里有算法历史的良好描述（点击此处）。有序量子树状图算法更相关于你当前的搜索，可以在（点击此处）找到。希望能对你有所帮助！

- Dr. belisarius

Answer 2

这是一种装箱问题的版本，http://en.wikipedia.org/wiki/Bin_packing_problem，由于其为NP难问题，因此您需要选择一些合理的启发式算法。如果您不希望在调整一个视频大小时其他视频跳动，您需要留下大量额外的空白空间或自动缩小其他视频。

除非您有充分的理由允许它，否则建议要求保持宽高比不变。

建议：首先固定所有视频的高度，然后使用贪心的首次适合算法进行装箱。初始高度应为总屏幕高度的整数分数。如果有人调整了一个视频的大小，则其他所有内容都会以相同的分数值缩小并移动到其他地方以适应。

- Mr Fooz

---

谢谢Fooz先生的建议，认为这是一个装箱问题帮助我找到了适当的文献和算法。 - bramp

Answer 3

平方根 + 基于四舍五入的逻辑。如果平方根的余数小于0.5，则向下舍入结果，使用结果作为行/列，并将1添加到行或列计数；如果平方根的余数大于等于0.5，则向上舍入并将其用作行/列计数。

10 videos = 4x3 (3.16; rounded down, so add 1 row or col)
9 videos = 3x3 (3; abs)
8 videos = 3x3 (2.82; round up)
7 videos = 3x3 (2.64; round up)
6 videos = 3x2 (2.44; round down, so add 1 row or col)
5 videos = 3x2 (2.23; round down, so add 1 row or col)
4 videos = 2x2 (2; abs)
3 videos = 2x2 (1.73; round up)
2 videos = split screen in half vertically or horizontally (however you'd like)
1 video = full screen

现在，这是使所有视频“正方形”的方法，很可能是最好的选择，因为你真的很难考虑到存在于不同分辨率/比例之间的差异（除非对你来说是静态的）。

因此，根据显示分辨率与视频分辨率的比率，网格周围将有填充空间，因此您需要将网格居中。也就是说，一个选项是让您将“填充”空间除以行数（或列数），并将其用作视频之间的缓冲区。

一旦您确定了行/列计数，并且假设所有视频都是相同大小的，则只需将屏幕宽度除以列数，将高度除以行数，即可得到视频尺寸。

然后，在屏幕上平铺视频--显然，在某些情况下，网格上的某些位置可能为空。您可以检测该空间覆盖的网格上的行和列，并将视频居中放置在该特定行上。

如果您希望“最大化”视频，则事先确定“最大化”意味着多少空间。然后，在计算其他视频的大小之前，从屏幕分辨率中减去该像素占用量。如果最大化意味着屏幕的50％，则从网格中的视频数量中减去该视频，并从显示分辨率中减去50％的像素空间。

- nessence