快速和肮脏的第一遍解决方案总是一个很好的开始，如果没有其他的比较。

贪心安置由大到小。

把剩下的最大的矩形放入打包区域。如果它放不下任何地方，就把它放在一个尽可能不扩大背包区域的地方。重复这一步骤，直到你完成最小的矩形。

它一点也不完美，但它很简单，是一个很好的底线。它仍然会完美地包装你原来的例子，并为第二个例子提供相同的答案。

看看包装问题。我认为你的属于“2D箱子包装”。你应该能从这个和其他包装问题的解决方案中学到很多东西。

另请参阅:将矩形图像数据打包到正方形纹理中。

我相当确定这是一个np困难的问题，因此，为了获得最优解决方案，您必须实现一个回溯算法，尝试所有可能的组合。

好消息是，由于需要在有限的2D空间中填充2D矩形，你可以在早期删除许多可能性，所以这可能并不是那么糟糕。

关于这个问题有大量的文献。一种好的贪婪启发式方法是将矩形从大到小放置在容器底部和左侧的第一个可用位置上。想象重力把所有的东西都拉到左下角。对于这个谷歌“沙雷左下角包装”的描述。

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

对于您的情况，外部循环应该从最小的边界框向上迭代(宽度和高度依次以2的幂增加)。对于每个包围框，测试一下是否可以为矩形找到一个填充。你会得到一堆“不”的答案，直到第一个“是”的答案，这将保证是最优解。

对于算法的内部循环——对特定大小的边界框回答“是”或“否”的循环，我将查找Huang参考并实现他的算法。他在基本算法的基础上进行了大量优化，但你只需要最基本的部分。由于您希望处理旋转，因此在搜索过程中的每个分支点上，只要同时尝试两个旋转并在两个旋转都没有得到解决方案时回溯即可。

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

快速和肮脏的第一遍解决方案总是一个很好的开始，如果没有其他的比较。

贪心安置由大到小。

把剩下的最大的矩形放入打包区域。如果它放不下任何地方，就把它放在一个尽可能不扩大背包区域的地方。重复这一步骤，直到你完成最小的矩形。

它一点也不完美，但它很简单，是一个很好的底线。它仍然会完美地包装你原来的例子，并为第二个例子提供相同的答案。