有没有一种适用于矩形容器（而不是正方形）和旋转的C++源代码/库来解决2D装箱问题？

Question

8

如标题所述，我需要C/C++源代码或库来解决二维矩形形状的装箱问题，其中箱子也是矩形的，并且为了更好地适应，矩形还会被旋转90度角。我已经有所有必需的值，所以我不需要在线装箱算法。

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

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

谢谢。

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

PPS：它必须是C或C++，我在stackoverflow上没有找到任何有用的东西...

- HardCoder

几乎是重复的问题：https://dev59.com/WV7Va4cB1Zd3GeqPLqf-#8638099 - user406009

2个回答

5

我几周前发现了这个帖子，在阅读答案中的PDF并尝试使用作者的代码后，我进行了重写以更符合我的需求（纹理图集打包）。

如果有其他人感兴趣... https://github.com/chris-stones/BinPack2D - 允许用户将数据结构与提交的矩形捆绑在一起（原始文件名等） - 打包多个bin（用于2d纹理图集数组-GL_EXT_texture_array）

此外，我跟踪和排序自由左上角，而不是跟踪拆分和加入自由矩形。我发现这样实现更简单，结果同样好。

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

- user2035147

很棒的实现，Chris。代码非常干净，打包质量也很高。然而，暴力交集测试会消耗相当多的性能。使用某种Kd树来减少测试数量可能会有益。另一种提高性能的方法是简单地使用较小的画布尺寸来减少每个画布中矩形的数量。 - Paul Houx

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user406009 · Accepted Answer

你可能能够修改其中一个算法以满足你的需求。我怀疑旋转是不必要的，因为这些算法已经非常先进了。

你可能需要在算法的顶部进行修改，当选择下一个要使用的矩形时。简单地让它也查看矩形的不同方向，并循环整个列表。