c++ - 是否有 c++ 源/lib 来解决 2D Bin Packing 与矩形箱（不是正方形）和旋转？

Question

正如标题已经说的那样，我需要 C/C++ 源代码或库，我可以使用它来解决 2D 矩形形状的装箱问题，其中箱也是矩形的，并且矩形也被旋转 90° 角以更好地适应。我已经有了所有必需的值，所以我不需要在线打包算法。

我只找到了一个处理方形箱且没有旋转的库，这对于我的需求来说效率不够高。

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

谢谢。

PS：计算所需的时间并不重要，重要的是结果。

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

Answer 1

http://clb.demon.fi/files/RectangleBinPack.pdf是关键。这是二维装箱的参考。

您也许可以修改其中的一种算法以满足您的需要。我怀疑是否需要旋转，算法非常先进。

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

选择要使用的下一个矩形时，您可能必须进行的修改是在算法的顶部。只需让它还查看矩形的不同方向以及循环浏览整个列表。

Answer 2

几周前我发现了这个线程，在浏览了答案中的 PDF 并玩弄了作者的代码之后，我做了一个更适合我需要的重写（纹理图集打包）

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

• 允许用户将数据结构与提交的矩形（原始文件名等）捆绑在一起
• 打包多个 bin（用于 2d 纹理图集数组 - GL_EXT_texture_array）

此外，我不是跟踪分割和连接自由矩形，而是跟踪和排序自由左上角。我发现它实现起来要简单得多，结果也同样好。

没有文档，请参阅头文件顶部的 ExampleProgram()。