什么算法可用于以相当优化的方式将不同大小的矩形打包成尽可能小的矩形? [英] What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way?

问题描述

我有一堆矩形物体，我需要把它们塞进尽可能小的空间(这个空间的尺寸应该是 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 的幂，并且在每个维度的给定最大大小范围内)?

解决方案

快速而肮脏的第一遍解决方案总是一个很好的开始，作为比较，如果没有别的.

从大到小的贪婪放置.

将剩余的最大矩形放入您的打包区域.如果它不能放在任何地方，请将其放置在尽可能少地扩展包装区域的地方.重复直到完成最小的矩形.

它并不完美，但它很容易并且是一个不错的基线.它仍然可以完美地打包您的原始示例，并为您提供第二个相同的答案.

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.

Eg say Ive got the following rectangles

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

They can be packed into a 128*128 space

 _________________
|128*32          |
|________________|
|128*64          |
|                |
|                |
|________________|
|64*32  |64*32   |
|_______|________|

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              |           |
|____________________|___________|

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.

Greedy placement from large to small.

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屋！