小编典典

可以使用哪种算法以相当理想的方式将不同大小的矩形打包为最小的矩形?

algorithm

我有一大堆矩形对象,我需要将它们打包到尽可能小的空间中(此空间的尺寸应为2的幂)。

我知道有各种打包算法,这些算法会将项目尽可能地打包到给定的空间中,但是在这种情况下,我需要该算法来计算出该空间也应该有多大。

例如,说我有以下矩形

  • 128 * 32
  • 128 * 64
  • 64 * 32
  • 64 * 32

它们可以包装成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的幂,并且在每个尺寸的给定最大尺寸内)?


阅读 218

收藏
2020-07-28

共1个答案

小编典典

快速而肮脏的首过解决方案始终是一个很好的开始,如果没有其他比较的话。

贪婪的放置方式从大到小。

将剩余的最大矩形放入您的打包区域。如果无法将其放置在任何地方,请将其放置在尽可能减少包装区域的地方。重复直到您完成最小的矩形。

它根本不是完美的,但是很简单,并且是一个不错的基准。它仍然可以完美地包装您的原始示例,并为第二个示例提供相同的答案。

2020-07-28