多图像放置算法 - 拼贴算法

Question

我正在创建一个应用程序来同时显示多个视频（比如说 2-10 个视频）。我基本上是在寻找一种可以帮助将视频放置在屏幕上的算法。我面临的问题是每个视频可能有不同的纵横比，我显然需要调整视频的大小以使它们都适合屏幕。但我想以一种最大限度地利用屏幕（并最大限度地减少纵横比失真）的方式调整它们的大小和适合它们。此外，我希望用户能够增加一个或多个视频的大小，以便在屏幕上占用更多空间。因此算法应该是稳定的，因为放大一个视频不会让所有的展示位置都跳来跳去。

我以一种语言不可知的方式问这个问题，我使用视频的事实无关紧要，这个问题同样适用于静止图像。

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

为了帮助澄清这里是一个例子。我有三个视频，大小如下。我希望第一个视频占据大约 50% 的屏幕，最后两个视频占据大约 25% 的屏幕。

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

我如何将它们放在屏幕上（1024x800）来实现这一点？我想我会先把屏幕一分为二，最适合上半部分的第一个视频。然后我会将下半部分分成两部分，并尽可能地将剩余的两个视频都放在一起。

提前致谢

Answer 1

这是装箱问题 http://en.wikipedia.org/wiki/Bin_packing_problem的一个版本 ，它是 NP 难题，因此您需要选择一些合理的启发式方法。如果您不希望视频在调整视频大小时跳来跳去，则需要留下一堆额外的死区或自动缩小其他区域。

除非您有充分的理由允许它，否则我建议要求纵横比保持固定。

建议：首先固定所有视频的高度，然后使用贪婪首次拟合算法将它们打包。初始高度将是总屏幕高度的整数部分。如果有人调整视频大小，其他所有内容都会缩小相同的分数并移开以适应。