可以使用哪种算法以相当理想的方式将不同大小的矩形打包为可能的最小矩形？ [英] What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way?
问题描述
我有一堆矩形对象，需要将它们包装到尽可能小的空间中（此空间的尺寸应为2的幂）。
Ive got a bunch of rectangular objects which I need to pack into the smallest space possible (the dimensions of this space should be powers of two).
我知道可以将物品尽可能多地打包到给定空间中的各种打包算法，但是在这种情况下，我需要该算法来计算出该空间也应该有多大。
I'm aware of various packing algorithms that will pack the items as well as possible into a given space, however in this case I need the algorithm to work out how large that space should be as well.
例如说我有以下矩形
- 128 * 32
- 128 * 64
- 64 * 32
- 64 * 32
- 128*32
- 128*64
- 64*32
- 64*32
它们可以装在128 * 128的空间中
They can be packed into a 128*128 space
_________________
|128*32 |
|________________|
|128*64 |
| |
| |
|________________|
|64*32 |64*32 |
|_______|________|
但是，如果同时有160 * 32和64 * 64，则需要256 * 128空间
However if there was also a 160*32 and a 64*64 one it would need a 256*128 space
________________________________
|128*32 |64*64 |64*32 |
|________________| |_______|
|128*64 | |64*32 |
| |_______|_______|
| | |
|________________|___ |
|160*32 | |
|____________________|___________|
有哪些算法可以打包一堆矩形并确定容器所需的大小（幂为2，并在给定的每个尺寸的最大尺寸之内）？
What algorithms are there that are able to pack a bunch of rectangles and determine the required size for the container (to a power of 2, and within a given maximum size for each dimension)?
推荐答案
快速而肮脏的首过解决方案始终是一个很好的起点
The quick and dirty first pass solution is always a great one to start with, as a comparison if nothing else.
从大到小的贪心放置。
放置最大的矩形留在您的打包区域。如果无法将其放在任何地方，请将其放置在尽可能减少包装区域的地方。重复该操作，直到完成最小的矩形为止。
Put the largest rectangle remaining into your packed area. If it can't fit anywhere, place it in a place that extends the pack region as little as possible. Repeat until you finish with the smallest rectangle.
这虽然并不完美，但它很简单，而且基线很好。仍然可以完美地包装您的原始示例，并为第二个示例提供相同的答案。
It's not perfect at all but it's easy and a nice baseline. It would still pack your original example perfectly, and give you an equivalent answer for the second as well.
这篇关于可以使用哪种算法以相当理想的方式将不同大小的矩形打包为可能的最小矩形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
