7

我正在尝试将几张图像放在一个大图像中，并且正在寻找一种算法来确定最佳位置。图像无法旋转或调整大小，但结果图像中的位置并不重要。

编辑：添加没有调整大小约束

4

6 回答 6

3

可能您正在寻找这样的东西：自动杂志布局。

于 2008-09-24T06:02:14.817 回答
2

显然它被称为“打包问题”，这是游戏编程中经常使用的问题。对于那些感兴趣的人，这里有一些建议的实现：

打包光照贴图、 矩形打包和 矩形放置

于 2008-09-24T08:13:22.083 回答
0

最佳包装很难，但根据您的问题域的详细信息，您可能会得到简化。一些想法：

  1. 如果您可以将位图分割成大小相同的图块，那么打包是微不足道的。然后，根据需要，您将从图块中重新组合位图。

  2. 将图像从大到小排序，然后，对于每个图像，使用贪婪分配器来选择适合图像的第一个可用子矩形。

  3. 使用遗传算法。从几个随机选择的布局开始。根据包装的紧密程度对它们进行评分。混合得分最高的解决方案，并进行迭代，直到获得可接受的分数。

于 2009-05-10T17:02:35.943 回答
0

我为此创建了一个算法，它实际上是NP-Hard Bin 打包问题的一个变体，但具有无限的 bin 大小。

您可以尝试查找一些关于它的文章并尝试优化您的算法，但最终它仍将是尝试所有可能性并尝试最小化生成的 bin 大小的蛮力方法。

如果您不需要最佳解决方案，而只需要一种解决方案，则可以避免暴力破解所有组合。我创建了一个程序，它也做过一次。

描述：

Images: array of the input images
ResultMap: 2d array of Booleans
FinalImage: large image
  1. 对图像数组进行排序，使最大的图像位于顶部。
  2. 计算图像的总大小并初始化 ResultMap，使其大小为图像总大小的 1.5 倍（您可以使这一步更智能，以提高内存使用率和性能）。使 ResultMap 的大小相同，并用 False 值填充它。
  3. 然后在 FinalImage 左侧添加第一个图像，并将 ResultMap 中的所有布尔值设置为 true，从 0,0 到 ImageHeight、ImageWidth。

ResultMap 用于快速检查您是否可以在当前 FinalImage 上适合图像。您可以对其进行优化以使用 int32 并将每个位用于一个像素。这将减少内存并提高性能，因为您可以一次检查 32 位（使用掩码）。但这将变得更加困难，因为您必须考虑为图像边缘制作所需的蒙版。

现在我将描述“算法”的真正循环。

  1. 对于数组中的每个图像，尝试找到一个合适的位置。您可以编写一个循环，该循环将通过 ResultMap 数组查找并查找错误值，然后开始查看它是否在两个方向上都为要放置的图像大小的错误。
    • 如果找到一个地方，将图像复制到 FinalImage 并在 ResultMap 中更新正确的布尔值
    • 如果你能找到一个地方，将 FinalImage 的大小增加得恰到好处（因此请查看需要最少额外空间的边缘）并将其与 ResultMap 同步
  2. 转到 1 :)

它不是最佳的，但它可以以合理的最佳方式解决问题（特别是如果最后有一些较小的图像来填补空白）。

于 2008-09-24T08:04:11.357 回答
-3

以非编程方式，您可以使用 MS Paint 功能“粘贴自”，即将 (JPEG) 文件粘贴到 mspaint 图像区域。使用它，您可以排列单个图像，并创建最终的大图像并将其保存为 JPEG/GIF/Raw-BMP 格式。

-广告。

于 2008-09-24T10:51:07.057 回答