我有一大堆矩形对象,我需要将它们打包到尽可能小的空间中(此空间的尺寸应为2的幂)。
我知道有各种打包算法,这些算法会将项目尽可能地打包到给定的空间中,但是在这种情况下,我需要该算法来计算出该空间也应该有多大。
例如,说我有以下矩形
它们可以包装成128 * 128的空间
_________________ | 128 * 32 | | ________________ | | 128 * 64 | | | | | | ________________ | | 64 * 32 | 64 * 32 | | _______ | ________ |
但是,如果同时有160 * 32和64 * 64,则需要256 * 128的空间
________________________________ | 128 * 32 | 64 * 64 | 64 * 32 | | ________________ | | _______ | | 128 * 64 | | 64 * 32 | | | _______ | _______ | | | | | ________________ | ___ | | 160 * 32 | | | ____________________ | ___________ |
有哪些算法可以打包一堆矩形并确定容器所需的尺寸(2的幂,并且在每个尺寸的给定最大尺寸内)?
快速而肮脏的首过解决方案始终是一个很好的开始,如果没有其他比较的话。
贪婪的放置方式从大到小。
将剩余的最大矩形放入您的打包区域。如果无法将其放置在任何地方,请将其放置在尽可能减少包装区域的地方。重复直到您完成最小的矩形。
它根本不是完美的,但是很简单,并且是一个不错的基准。它仍然可以完美地包装您的原始示例,并为第二个示例提供相同的答案。