288

我有一堆矩形对象，我需要将它们打包到尽可能小的空间中（这个空间的尺寸应该是 2 的幂）。

我知道各种打包算法可以尽可能地将物品打包到给定的空间中，但是在这种情况下，我需要算法来计算出该空间应该有多大。

例如说我有以下矩形

  • 128*32
  • 128*64
  • 64*32
  • 64*32

它们可以打包成128*128的空间

_________________
|128*32 |
|________________|
|128*64 |
| |
| |
|________________|
|64*32 |64*32 |
|________|________|

但是，如果还有 160*32 和 64*64 的，则需要 256*128 的空间

________________________________
|128*32 |64*64 |64*32 |
|________________| |_______|
|128*64 | |64*32 |
| |_______|_______|
| | |
|________________|___ |
|160*32 | |
|____________________|_______|

有哪些算法能够打包一堆矩形并确定容器所需的大小（到 2 的幂，并且在每个维度的给定最大大小内）？

4

7 回答 7

104

有关解决方案的调查，请参阅ARC 项目的此页面，在实现复杂性/时间和最优性之间进行权衡，但有多种算法可供选择。

这是算法的摘录：

  1. 首次拟合递减高度 (FFDH) 算法
    FFDH 将下一个项目 R（在非递增高度中）打包在 R 适合的第一层。如果没有级别可以容纳 R，则创建一个新级别。
    FFDH 的时间复杂度：O(n·log n)。
    近似比：FFDH(I)<=(17/10)·OPT(I)+1；17/10 的渐近界是紧的。

  2. Next-Fit 递减高度 (NFDH) 算法
    如果 R 适合，NFDH 会在当前级别上打包下一个项目 R（非递增高度）。否则，当前关卡将“关闭”并创建一个新关卡。
    时间复杂度：O(n·log n)。
    近似比：NFDH(I) <= 2·OPT(I)+1；2 的渐近界是紧的。

  3. 最佳拟合递减高度 (BFDH) 算法
    BFDH 在能够容纳 R 的项目中，将水平上的下一个项目 R（非递增高度）打包，其中剩余水平空间最小。如果没有级别可以容纳 R，则创建一个新级别。

  4. 左下角 (BL) 算法
    BL 不增加宽度的一阶项目。BL 将下一个项目尽可能靠近底部包装，然后尽可能靠近左侧而不与任何包装项目重叠。请注意，BL 不是面向级别的打包算法。
    时间复杂度：O(n^2)。
    近似比：BL(I) <= 3·OPT(I)。

  5. Baker 的上下 (UD) 算法
    UD 结合了 BL 和 NFDH 的泛化。条带和项目的宽度被归一化，以便条带具有单位宽度。UD 以非递增宽度对项目进行排序，然后将项目分为五组，每组宽度在 (1/2, 1], (1/3,1/2], (1/4,1/3) 范围内], (1/5,1/4], (0,1/5]. 条带也分为五个区域 R1,···, R5. 基本上一些宽度在 (1/i+ 1, 1/i], 对于 1 <= i <= 4, 被 BL 打包到区域 Ri. 由于 BL 在条带右侧从上到下留有宽度递增的空间, UD 首先利用这个优势j = 1,···,4（按顺序）从上到下将物品打包到Rj。如果没有这样的空间，则将物品由BL打包到Ri。最后，大小最多为1/5的物品通过（广义）NFDH 算法将它们打包到 R1、···、R4 中的空间。
    近似比：UD(I) <= (5/4)·OPT(I)+(53/8)H，其中H是物品的最大高度；5/4 的渐近界是紧的。

  6. 反向拟合 (RF) 算法
    RF 还对条带和项目的宽度进行归一化，使条带具有单位宽度。RF首先堆叠所有宽度大于1/2的物品。其余物品按非递增高度排序，大于 1/2 的物品将在高度 H0 以上进行包装。然后RF重复以下过程。粗略地说，RF 从左到右包装物品，底部沿着高度 H0 线，直到没有更多空间。然后从右到左，从上到下（称为反向层）打包物品，直到总宽度至少为 1/2。然后反向水平下降，直到（至少）其中一个触及下面的某个项目。下拉以某种方式重复。
    近似比：RF(I) <= 2·OPT(I)。

  7. Steinberg 算法
    Steinberg 算法，在论文中表示为 M，估计了打包所有项目所需的高度 H 的上限，从而证明输入项目可以打包成一个宽度为 W 和高度为 H 的矩形。然后他们定义七个过程（有七个条件），每个过程将一个问题分成两个较小的问题并递归解决它们。已经表明，任何可处理的问题都满足七个条件之一。
    近似比：M(I) <= 2·OPT(I)。

  8. Split-Fit 算法（SF） SF 将项目分为两组，L1 的宽度大于 1/2，L2 最多为 1/2。L1的所有物品首先由FFDH包装。然后将它们排列成宽度大于 2/3 的所有项目都低于宽度最多 2/3 的项目。这将创建一个宽度为 1/3 的矩形空间 R。然后使用 FFDH 将 L2 中的剩余项目打包到 R 和与 L1 打包的项目上方的空间。在 R 中创建的水平被认为低于在 L1 的包装之上创建的水平。
    近似比：SF(I) <= (3/2) ·OPT(I) + 2；3/2 的渐近界是紧的。

  9. Sleator 算法
    Sleater 算法包括四个步骤：

    1. 所有宽度大于 1/2 的物品在条带底部相互叠放。假设 h0 是最终打包的高度所有后续打包将发生在 h0 之上。

    2. 其余项目按非增加高度排序。沿着高度 h0 的线从左到右包装一个级别的项目（以非递增的高度顺序）。

    3. 然后在中间画一条垂直线，将条带切成相等的两半（注意这条线可能会切割部分包装在右半部分的物品）。画两条长度为一半的水平线段，一条穿过左半边（称为左基线），另一条穿过右半边（称为右基线），尽可能低，以使两条线不穿过任何项目。

    4. 选择高度较低的左侧或右侧基线，并将一层物品装入条带的相应一半，直到下一个物品太宽。

    形成一个新的基线，并在较低的基线上重复步骤 (4)，直到所有项目都被打包。
    时间复杂度：O(n·log n)。
    Sleator 算法的逼近比是 2.5，这很严格。

于 2010-11-24T07:47:32.823 回答
74

快速而肮脏的第一次通过解决方案总是一个很好的开始，作为比较，如果没有别的。

从大到小贪婪放置。

将剩余的最大矩形放入包装区域。如果它不适合任何地方，请将其放置在尽可能少地扩展背包区域的地方。重复直到你完成最小的矩形。

它一点也不完美，但它很简单，而且是一个不错的基线。它仍然会完美地打包您的原始示例，并为您提供第二个相同的答案。

于 2009-07-31T16:33:45.570 回答
21

看看包装问题。我认为您的属于“二维装箱”。您应该能够从解决该问题和其他包装问题的解决方案中学到很多东西。

另请参阅：将矩形图像数据打包成方形纹理。

于 2009-07-31T16:16:40.520 回答
19

关于这个问题有大量的文献。一个好的贪心启发式方法是将矩形从最大区域到最小区域放置在容器底部和左侧的第一个可用位置。想象一下重力将所有物品拉到左下角。有关此谷歌“Chazelle 左下包装”的描述。

为了获得最佳解决方案，最先进的技术可以在几秒钟内打包 20 多个矩形。Huang 有一个算法，可以将寻找最小包围框的问题与确定一组矩形是否可以放入特定大小的边界框的问题分开。你给他的程序一组矩形，它会告诉你打包它们所需的最小封闭边界框。

对于您的情况，您的外部循环应该从可能的最小边界框向上迭代（宽度和高度依次增加 2 的幂）。对于这些边界框中的每一个，测试您是否可以找到矩形的包装。你会得到一堆“否”的答案，直到第一个“是”的答案，这将保证是最佳解决方案。

对于您的算法的内部循环 - 对特定大小的边界框回答“是”或“否”的那个，我会查找 Huang 参考并实现他的算法。他在基本算法的基础上做了很多优化，但你真的只需要基本的肉和土豆。由于您要处理旋转，因此在搜索过程中的每个分支点，当两种旋转都没有产生解决方案时，只需尝试旋转和回溯。

于 2010-06-22T02:00:27.383 回答
10

我相当肯定这是一个 NP-hard 问题，因此，为了获得最佳解决方案，您必须实现一个回溯算法来尝试所有可能的组合。

好消息是，由于需要在有限的 2D 空间中打包 2D 矩形，您可以在早期修剪很多可能性，因此可能还不错。

于 2009-07-31T16:04:53.193 回答
6

您需要的是 https://github.com/nothings/stb/blob/master/stb_rect_pack.h

样本：

stbrp_context context;

struct stbrp_rect rects[100];

for (int i=0; i< 100; i++)
{
    rects[i].id = i;
    rects[i].w = 100+i;
    rects[i].h = 100+i;
    rects[i].x = 0;
    rects[i].y = 0;
    rects[i].was_packed = 0;
}

int rectsLength = sizeof(rects)/sizeof(rects[0]);

int nodeCount = 4096*2;
struct stbrp_node nodes[nodeCount];


stbrp_init_target(&context, 4096, 4096, nodes, nodeCount);
stbrp_pack_rects(&context, rects, rectsLength);

for (int i=0; i< 100; i++)
{
    printf("rect %i (%hu,%hu) was_packed=%i\n", rects[i].id, rects[i].x, rects[i].y, rects[i].was_packed);
}
于 2016-09-22T17:24:53.117 回答
3

一个通用的解决方案是不平凡的（数学说明完全不可能）
通常人们使用遗传算法来尝试可能的组合，但你可以通过首先放置最大的形状然后尝试不同的位置来做得相当好下一个最大的等等。

于 2009-07-31T16:18:18.957 回答