我的问题与2D背包问题或切割库存问题非常相似，但有一个例外...适合容器的矩形可以调整大小和裁剪，但不允许旋转。
挑战在于尽可能少地进行裁剪，并填满整个容器（绝对没有间隙）。
有没有遇到过类似的算法？任何链接、伪代码都将不胜感激。
问题是通用的，但我想将其应用于在固定大小的页面上组织照片。
非常感谢。
挑战在于尽可能少地进行裁剪，并填满整个容器（绝对没有间隙）。
有没有遇到过类似的算法？任何链接、伪代码都将不胜感激。
问题是通用的，但我想将其应用于在固定大小的页面上组织照片。
非常感谢。
在固定的矩形容器中组织矩形的算法
6
- beklip
13
我认为调整大小实际上比背包问题更难。如果您可以在不调整大小的情况下最优地解决此问题，则可以将其用于解决背包问题。 - fairidox
2@beklip - 我们需要更好地定义裁剪。这是一个优化问题，我们需要知道我们正在优化什么。裁剪的面积？裁剪的图片数量？我最初问这个问题是因为如果我们可以任意调整图像大小，我们只需将矩形分成n个部分，并沿着该网格调整图像大小。 - dfb
2@beklip：您是指每张图像裁剪的平均面积吗？这不是一个很好的标准，因为例如，如果您有2张10x10的照片要放在一个10x12的矩形中，它不能区分缩小两个照片到10x6和将一个缩小到10x2和另一个缩小到10x10（我认为应该被认为更糟糕）。此外，应如何权衡裁剪和调整大小？在尝试最小化任何东西之前，我们需要一个接受候选解并给出单个数字的函数。 - j_random_hacker
1@j_random_hacker：我认为也许可以将给定图片裁剪的面积百分比最小化？我认为这种方法是公平的，尽管它不能解决一些图片可能被缩小成狭长条带的问题，这似乎不太好。 - Null Set
1@j_random_hacker 我理解为，纵横比的变化实际上是一种裁剪，可能是在调整大小之后进行的。"你不需要保持图像比例"，因为我们有裁剪功能。否则这个问题就没有意义了。我们总是可以通过不进行任何裁剪，只是"调整大小"来适应，从而最小化"裁剪"，而裁剪是他想要最小化的唯一事物。 - Null Set
显示剩余8条评论
3个回答
5
首先，使用确定性的最佳适配减少算法：
按大小从大到小对矩形进行排序
将第一个矩形放入容器中，如果它适合
取下一个矩形并将其放置在容器中最佳的剩余位置而不裁剪（如果它适合其中）。 如果有多个选项，请选择留下最少边缘区域的选项。 重复此步骤，直到容器已满或所有矩形都已使用。
如果容器尚未填满，请按相同顺序遍历未使用的矩形，但这次尝试裁剪。
现在，这并不完美。 您可能会遇到类似于此图像中左侧2个解决方案的情况，在该图像中，即使不需要“无空间”项目，您也会对其进行裁剪：
因此，其次，在第一步的结果上添加元启发式算法，例如Tabu搜索或模拟退火。 如果您正在寻找一个开源库来为您执行此操作，请查看此库。
- Geoffrey De Smet
3
目前为止，我们尚未确定要优化的确切标准。但无论最终决定了什么标准，以下启发式（即通常是次优的）方法可能会有所帮助：只考虑一小组“布局”，将少量矩形组合成单个较大的矩形。然后，递归地查看如何使用相同的几个布局将这些新矩形组合成更大的矩形，直到只剩下一个矩形。这并不能保证最优解，因为某些照片的子集被限制在最终解中形成子矩形。但它似乎很可能会给出合理的高质量解决方案。
例如，对于3个矩形A、B和C，考虑以下4种布局：
裁剪仅在第一轮组合3张照片时发生。对于此步骤，应考虑每个由上述4种布局组成的3张照片子集，并确定每个子集的最佳缩放和裁剪，请记住后续步骤可能会将结果矩形放大或缩小。(优选标准的良好选择应具有这样的属性：在特定布局下，A、B和C的每个理想缩放和裁剪量不受所得到的矩形缩放的影响，因此这不应该是问题)。
随后的组合轮次将类似地进行，但不考虑任何裁剪。对于完整解决方案，第2轮将尝试组合第1轮产生的所有3个矩形集，其中所有9张照片都不同，但按照此方法进行将导致指数级的增长。保留每个照片出现在每轮产生的至少一个矩形中很重要，只保留每个子集的最佳排列即可。
例如，对于3个矩形A、B和C，考虑以下4种布局：
A
B
C
ABC
AB (i.e. A appears on the left)
AC
AA (i.e. A appears on the top)
BC
裁剪仅在第一轮组合3张照片时发生。对于此步骤，应考虑每个由上述4种布局组成的3张照片子集，并确定每个子集的最佳缩放和裁剪，请记住后续步骤可能会将结果矩形放大或缩小。(优选标准的良好选择应具有这样的属性：在特定布局下，A、B和C的每个理想缩放和裁剪量不受所得到的矩形缩放的影响，因此这不应该是问题)。
随后的组合轮次将类似地进行，但不考虑任何裁剪。对于完整解决方案，第2轮将尝试组合第1轮产生的所有3个矩形集，其中所有9张照片都不同，但按照此方法进行将导致指数级的增长。保留每个照片出现在每轮产生的至少一个矩形中很重要，只保留每个子集的最佳排列即可。
- j_random_hacker
1
这是最吸引人的解决方案，考虑到我的编程技能和所需的努力程度。感谢您的反馈。我所需要做的就是定义足够的布局（我喜欢自己对最终结果有一定的控制），包括横向和纵向区域的组合，以最小化所需的裁剪。 - beklip
0
我不会声称这是最优的方法，但以下是一些可能让你尝试的想法。
基于评论，我将重新定义问题。我们有一个$v \times t$大小的矩形X和N个大小各异的矩形。我们希望用这N个矩形完全覆盖矩形X。我们允许按比例调整图像的原始尺寸。我们希望最小化被N个矩形所覆盖并且也不覆盖X矩形区域的面积。
以下是一个想法：
- 如果我们可以找到与原始尺寸成比例的包装，我们可以简单地缩放它，并适配矩形，我们就完成了
- 给定一些装箱算法，执行二进制搜索以找到X的最小缩放常数，使我们可以在箱子中打包所有矩形。
- 扩展和裁剪单个矩形，直到填充空间
不确定它的表现如何，但可以尝试一下。
- dfb
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接