在固定矩形容器中组织矩形的算法 [英] Algorithm to organize rectangles in the fixed rectangular container

问题描述

我的问题与 2D Knapsack 问题非常相似，或者切割库存，但有一个例外......适合容器的矩形可以调整大小和裁剪.但不允许旋转.

My problem is pretty similar to 2D Knapsack problem, or cutting stock with one exception... the rectangles that fit into the container can be resized and cropped. No rotation is allowed though.

面临的挑战是尽可能少地种植作物并填满整个容器(没有任何间隙).

The challenge is to make as little crops as possible and fill entire container (no gaps whatsoever).

有没有人遇到过可以做类似事情的算法.任何链接，非常感谢伪代码.

Has anyone encountered an algorithm that would do something similar. Any links, pseudo code much appreciated.

使问题保持​​通用，但我想应用它来组织固定大小页面上的照片.

Kept the question generic, but I'd like to apply it to organise photos on a fixed size page.

非常感谢

推荐答案

在我写这篇文章的时候，我们试图优化的确切标准还没有确定.但无论最终决定何种标准，以下启发式(即一般次优)方法可能会有用:

At the time I write this, the exact criterion we are trying to optimise hasn't been settled on. But whatever criterion is eventually decided on, the following heuristic (i.e. generally suboptimal) approach might be useful:

仅考虑将少量矩形组合成一个更大矩形的少量布局".然后递归地研究将这些新矩形组合成更大矩形的方法，仅使用相同的几个布局，直到只剩下一个矩形.

Consider only a small number of "layouts" for combining a small number of rectangles into a single larger rectangle. Then recursively look at ways of combining these new rectangles into even larger rectangles, using just the same few layouts, until only a single rectangle remains.

这并不能保证最佳解决方案，因为某些照片子集被限制为在最终解决方案中形成子矩形.但它似乎很可能会提供合理质量的解决方案.

This doesn't guarantee an optimal solution, because some subsets of photos are constrained to form subrectangles within the final solution. But it seems likely that it will give reasonable-quality solutions.

例如，对于 3 个矩形 A、B 和 C，请考虑以下 4 种布局:

For example, for 3 rectangles A, B and C, consider the following 4 layouts:

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 中的每一个的理想缩放和裁剪量不受结果矩形的缩放程度的影响，因此这不应该是问题.)

Cropping will only occur in the first round, when we are combining groups of 3 photos. For this step, every subset of 3 photos should be considered under each of the 4 layouts above, and the optimal scaling and cropping determined for each, bearing in mind that the resulting rectangle could be scaled up or down by later steps. (A good choice of optimality criterion should have the property that the ideal amount of scaling and cropping for each of A, B and C under a particular layout is not affected by how much the resulting rectangle is scaled, so this shouldn't be a problem.)

随后的组合轮将表现类似，但不考虑任何裁剪.对于完整的解决方案，第 2 轮将涉及尝试组合第 1 轮生成的所有 3 个矩形集，其中所有 9 张照片都是不同的，但是遵循这种方法将导致指数爆炸.为每个照片子集保留最好的几个安排就足够了.请注意，每张照片至少出现在每轮生成的 1 个矩形中很重要.

Subsequent combining rounds will behave similarly, but without considering any cropping. For a full solution, round 2 would involve trying to combine all sets of 3 rectangles produced by round 1 in which all 9 photos are distinct, however following this approach will lead to an exponential blowup. It should suffice to keep just the best few arrangements for each subset of photos. Note that it's important that each photo appear in at least 1 of the rectangles produced by each round.

这篇关于在固定矩形容器中组织矩形的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！