可以使用什么算法以不同的方式将不同大小的矩形打包成最小的矩形？

7 回答

• 19

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

  从大到小的贪婪安置 .

  将最大的矩形保留在您的打包区域中 . 如果它无法放在任何地方，请将其放置在尽可能少地延伸包装区域的位置 . 重复，直到完成最小的矩形 .

  它根本不是完美的，但它很简单，也是一个不错的基线 . 它仍然可以完美地包装您的原始示例，并为您提供相应的答案 .

  回复于 2024-05-03T14:03:02+08:00
• 77

  有关解决方案的调查，请参阅this page on the ARC project，在实现复杂性/时间和最优性之间进行权衡，但有多种算法可供选择 .

  这是算法的摘录：

  • First-Fit Decreasing Height（FFDH）算法
    FFDH在R适合的第一级包装下一个项目R（非增加高度） . 如果没有级别可以容纳R，则会创建一个新级别 .
    FFDH的时间复杂度：O（n·log n） .
    近似比：FFDH（I）<=（17/10）·OPT（I）1; 17/10的渐近界限很紧张 .

  • Next-Fit Decreasing Height（NFDH）算法
    如果R适合，NFDH将当前级别的下一个项目R（非增加高度）打包 . 否则，当前级别为"closed"并创建新级别 .
    时间复杂度：O（n·log n） .
    近似比：NFDH（I）<= 2·OPT（I）1; 2的渐近界是紧的 .

  • 最适合减小高度（BFDH）算法
    BFDH在级别上包含下一个项目R（非增加高度），其中包含可以容纳R的项目，剩余水平空间是最小的 . 如果没有级别可以容纳R，则会创建一个新级别 .

  • 左下（BL）算法
    BL第一个订单项目按非增加宽度 . BL将下一个物品包装在靠近底部的位置，因为它适合，然后尽可能靠近左侧，不会与任何包装物品重叠 . 请注意，BL不是面向水平的打包算法 .
    时间复杂度：O（n ^ 2） .
    近似比：BL（I）<= 3·OPT（I） .

  • Baker的Up-Down（UD）算法
    UD使用BL和NFDH的推广的组合 . 条带的宽度和物品被标准化，使得条带具有单位宽度 . UD以不增加的宽度对项目进行排序，然后将项目分为五组，每组的宽度在范围内（1 / 2,1,1），（1 / 3,1 / 2），（1 / 4,1 / 3） ]，（1 / 5,1 / 4），（0,1 / 5） . 条带也分为五个区域R1，...，R5 . 基本上，一些宽度在范围内的项目（1 / i 1） ，1 <= i <= 4，由BL填充到区域Ri . 由于BL在条带的右侧从顶部到底部留下增加宽度的空间，UD通过首先包装获得此优势从上到下，j = 1，...，4（按顺序）的项目为Rj . 如果没有这样的空间，则项目由BL打包到Ri . 最后，大小为1/5的项目是通过（广义）NFDH算法打包到R1，...，R4中的空间 . 如果这些区域中没有空格，则使用NFDH将项目打包到R5 .
    近似比：UD（I）<=（5/4）·OPT（I）（53/8）H，其中H是项目的最大高度; 5/4的渐近界是紧的 .

  • 反向拟合（RF）算法
    RF还使条带和物品的宽度标准化，使得条带具有单位宽度 . RF首先堆叠宽度大于1/2的所有项目 . 剩余物品按非增加高度分类，并将被填充到大于1/2的高度H0 . 然后RF重复以下过程 . 粗略地说，RF从左到右包装物品，其底部沿着高度线H0，直到没有空间 . 然后从右到左和从上到下（称为反向水平）包装物品，直到总宽度至少为1/2 . 然后降低反向级别直到（至少）其中一个触及下面的某个项目 . 下拉有点重复 .
    近似比：RF（I）<= 2·OPT（I） .

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

  • 分裂拟合算法（SF）SF将项目分为两组，L1宽度大于1/2，L2最多1/2 . L1的所有项目首先由FFDH打包 . 然后将它们排列成宽度超过2/3的所有物品都低于宽度最多为2/3的物品 . 这将创建一个宽度为1/3的矩形空间R.然后将L2中的剩余项目打包到R和使用FFDH打包的L1之上的空间 . 在R中创建的级别被认为低于在L1的打包之上创建的级别 .
    近似比：SF（I）<=（3/2）·OPT（I）2; 3/2的渐近界是紧的 .

  • Sleator的算法
    Sleater的算法包括四个步骤：

  • 所有宽度大于1/2的物品都在条带底部相互堆叠 . 假设h0是所得填料的高度所有后续填料将在h0以上发生 .

  • 剩余物品按非增加高度排序 . 物品等级沿着高度线h0从左到右被打包（以非增加的高度顺序） .

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

  • 选择较低高度的左侧或右侧基线，并将一个级别的项目装入相应的一半条带，直到下一个项目太宽 .

  形成新的基线，并且在下基线上重复步骤（4），直到所有物品都被打包 .
  时间复杂度：O（n·log n） .
  Sleator算法的近似比为2.5，这是紧的 .

  回复于 2024-05-03T14:03:02+08:00
• 17

  看看packing problems . 我认为你的问题属于'2D bin packing.'你应该能够从解决方案和其他包装问题中学到很多东西 .

  另见：Packing rectangular image data into a square texture.

  回复于 2024-05-03T14:03:02+08:00
• 2

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

  为了获得最佳解决方案，最先进的技术可以在几秒钟内打包超过20个矩形 . Huang有一个algorithm，它将找到最小的封闭边界框的问题与决定一组矩形是否适合特定尺寸的边界框的问题分开 . 你给他的程序一组矩形，它告诉你包装它们所需的最小的封闭边界框 .

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

  对于算法的内部循环 - 对特定大小的边界框回答“是”或“否”的循环，我会查找黄色参考并实现他的算法 . 他在基本算法之上包含了很多优化，但你只需要基本的肉和土 beans . 由于您希望在搜索过程中的每个分支点处理旋转，因此只需在两次旋转都不会产生解决方案时尝试旋转和回溯 .

  回复于 2024-05-03T14:03:02+08:00
• 6

  我很确定这是an NP-hard problem，因此，对于最佳解决方案，您必须实现一个尝试每种可能组合的回溯算法 .

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

  回复于 2024-05-03T14:03:02+08:00
• 61

  你需要的是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);
  }
  

  回复于 2024-05-03T14:03:02+08:00
• 0

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

  回复于 2024-05-03T14:03:02+08:00