是否有一个c ++ source/lib来解决带有矩形bin(非正方形)和旋转的2D Bin Packing？

Question

正如标题所说,我需要C/C++源代码或一个库,我可以使用它来解决二维矩形形状的Bin Packing问题,其中bin也是矩形,矩形也旋转了90°角以更好地适应.我已经拥有了所有必需的值,所以我不需要在线打包算法.

我只找到一个lib来处理一个方形箱而没有旋转,这对我的需求来说不够高效.

我真的很感激任何处理矩形bin和旋转的C/C++.

谢谢.

PS:计算所需的时间并不重要,只有结果.

PPS:它必须是C或C++,我没有找到任何有用的搜索stackoverflow ...

Answer 1

http://clb.demon.fi/files/RectangleBinPack.pdf是关键.这是2d bin包装的参考.

您可以修改其中一种算法以满足您的需求.我怀疑需要轮换,算法非常先进.

这(https://github.com/Lalaland/PixelPacker/blob/master/src/algoMaxRects.cpp)是如何实现MaxRects算法的示例.

在选择要使用的下一个矩形时,您可能必须进行的修改位于算法的顶部.简单地说,它还可以查看矩形的不同方向以及在整个列表中循环.

Answer 2

我几周前找到了这个帖子,在浏览了答案中的PDF并阅读了作者代码之后,我做了一个更适合我需要的重写(纹理图集包装)

如果有人有兴趣... https://github.com/chris-stones/BinPack2D

• 允许用户使用提交的矩形(orig文件名等)捆绑数据结构
• 打包多个箱(用于2d纹理图集阵列 - GL_EXT_texture_array)

此外,我不是跟踪分裂和连接自由矩形,而是跟踪和排序自由左上角.我发现它实现起来要简单得多,同样效果也不错.

没有文档,请参阅头文件顶部的ExampleProgram().