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

通解是非平凡的(数学上讲完全****ing不可能) 通常人们使用遗传算法来尝试可能的组合，但你可以把最大的形状放在前面，然后在不同的地方尝试下一个大的形状，以此类推。

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

贪心安置由大到小。

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

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

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

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

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

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

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