什麼算法可用於以相當優化的方式將不同大小的矩形打包成最小的矩形？

Question

我得到了一堆矩形物體，我需要將它們放入最小的空間（這個空間的尺寸應該是2的冪）。

我知道各種包裝算法，將盡可能包裝物品到一個給定的空間，但在這種情況下，我需要的算法來計算出多大的空間也應該。

如說Ive得到了如下矩形

• 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的冪，並且對於每個維度在給定的最大尺寸內）？

Answer 1

快速和骯髒的第一遍解決方案始終是一個偉大的開始，作爲比較，如果沒有別的。

貪婪的從大到小的擺放位置。

將最大的矩形留在您的打包區域。如果無法放在任何地方，請將其放置在儘可能少地延伸包裝區域的地方。重複，直到完成最小的矩形。

這並不完美，但它很容易和一個很好的基線。它仍然會完美地包裝您的原始示例，併爲第二個示例給出相應的答案。

Answer 2

我相當肯定這是an NP-hard problem，所以，對於一個最佳的解決方案，你必須實現一個回溯算法，試用所有可能的組合。

好消息是，由於需要在有限的2D空間中打包2D矩形，因此您可以儘早修剪很多可能性，所以它可能並不是那麼糟糕。

Answer 3

看看packing problems。我認爲你屬於'二維裝箱包裝'。您應該能夠從解決方案和其他包裝問題中學到很多東西。

另見：Packing rectangular image data into a square texture.

Answer 4

一般的解決方案是不平凡的（數學爲完全****荷蘭國際集團不可能說吧）
一般人使用遺傳算法來嘗試可能的組合，但你可以做得很好把最大的形狀放在第一位，然後嘗試不同的地方進行下一個最大的形狀，等等。

Answer 5

關於這個問題有大量的文獻。良好的貪婪法則是將矩形從最大面積放置到容器底部和左側的第一個可用位置。想想重力將所有物品拉到左下角。有關此谷歌「Chazelle左下包裝」的描述。

爲了獲得最佳解決方案，最先進的技術可以在幾秒鐘內打包超過20個矩形。 Huang有一個algorithm，它將找到最小封閉邊界框的問題與決定一組矩形是否適合特定大小的邊界框的問題分開。你給他的程序一組矩形，它告訴你需要打包它們的最小封閉邊框。

對於你的情況，你的外部循環應該從最小的可能邊界框向上迭代（寬度和高度依次增加2的冪）。對於每個邊界框，請測試以查看是否可以找到矩形的包裝。你會得到一堆「沒有」的答案，直到第一個「是」的答案，這將保證是最佳的解決方案。

對於算法的內部循環 - 對特定大小的邊界框回答「是」或「否」的算法，我將查找黃色參考並僅實現其算法。他在基本算法的基礎上包含了很多優化，但是你只需要基本的肉和土豆。既然你想處理旋轉，在搜索過程中的每個分支點，當兩個旋轉都不導致解決方案時，只需嘗試旋轉和回溯。

Answer 6

有關解決方案的調查，請參閱this page on the ARC project，實現複雜性/時間和最優性之間存在權衡，但有多種算法可供選擇。

下面的算法的提取物：

1. 最先適合降低的高度（FFDH）算法
   FFDH上式中，R擬合第一級包的下一個項目R（非高度增加）。如果沒有級別可以容納R，則會創建一個新級別。
   FFDH的時間複雜度：O（n·log n）。 （I）< =（17/10）·OPT（I）+1;其中， 17/10的漸近界很緊。

2. Next-Fit降低高度（NFDH）算法
   如果R符合，NFDH會在當前級別上打包下一個項目R（非增加高度）。否則，當前級別「關閉」並創建一個新級別。
   時間複雜度：O（n·log n）。
   近似比：NFDH（I）< = 2·OPT（I）+1; 2的漸近界是緊的。

3. 最優適應降低的高度（BFDH）算法
   BFDH上水平包的下一個項目R（非高度增加），這些可容納R，的量，殘留的水平空間爲最小之間。如果沒有級別可以容納R，則會創建一個新級別。

4. 左下（BL）算法
   BL一階項目的寬度不增加。 BL將下一個物品放在靠近底部的位置，因爲它可以放入，然後儘可能靠近左側，因爲它可以與任何包裝物品不重疊。請注意，BL不是一種面向級別的打包算法。
   時間複雜度：O（n^2）。 （I）
   近似比例：BL（I）< = 3·OPT（I）。（UD）算法
   UD使用BL和NFDH泛化的組合。條的寬度和項目被標準化，以便條的寬度爲單位。 UD以非增加的寬度對項目進行排序，然後將項目分成五組，每組的寬度在範圍（1/2,1），（1/3,1/2]，（1/4,1/3） ]，（1/5,1/4]，（0,1/5）。條帶也分爲5個區域R1，...，R5。基本上，一些寬度在（1/i +由於BL在條帶的右側從頂部到底部留下寬度增加的空間，因此UD首先利用該優勢，即首先利用該優勢如果沒有這樣的空間，那麼物品被BL打包到Ri，最後物品的尺寸至多爲1/5通過（廣義）NFDH算法打包到R1，...，R4中的空間，再次如果這些區域中沒有空間，則使用NFDH將項目打包到R5。 =（5/4）·OPT（I）+（53/8）H，其中H是物品的最大高度; 5/4的漸近界是緊的。

5. 反向擬合（RF）算法
   RF還標準化了條帶和物品的寬度，使條帶具有單位寬度。 RF首先堆疊寬度大於1/2的所有項目。剩餘物品按不增加的高度進行分類，並且將在大於1/2的高度上達到高度H0。然後RF重複以下過程。粗略地說，RF從左至右包裝物品，其底部沿着高度H0的線，直到沒有更多空間。然後將項目從右到左和從上到下打包（稱爲反轉級別），直到總寬度至少爲1/2。然後反轉級別下降，直到（至少）其中一個觸及下面的某個項目。下降是不知何故重複。
   近似比：RF（I）< = 2·OPT（I）。

6. Steinberg的算法
   Steinberg的算法，在紙表示爲M，估計的上部結合到包裝中的所有項目，使得它證明了輸入項目可裝入寬度的矩形所需要的高度H的W和高度H.然後他們定義了七個程序（有七個條件），每個程序將一個問題分成兩個較小的問題並遞歸解決問題。已經表明任何易處理的問題都滿足七個條件之一。 （I）
   近似比：M（I）< = 2·OPT（I）。 （SF） SF將項目分爲兩組，L1寬度大於1/2且L2最多爲1/2。所有的L1項目都由FFDH首先打包。然後將它們排列成使得寬度大於2/3的所有項目在寬度最多爲2/3的項目之下。這將創建寬度爲1/3的矩形R空間。然後將L2中的剩餘項目打包到R，並使用FFDH打包L1以上的空間。在R中創建的級別被認爲低於在L1的包裝之上創建的級別。 （I）< =（3/2）·OPT（I）+ 2; 3/2的漸近界是緊的。

7. Sleator算法
   Sleater的算法包括以下四個步驟：

   1. 寬度大於1/2的所有的數據項被打包在彼此的頂部上在帶的底部。假設h0是結果包裝的高度所有後續包裝將發生在h0以上。

   2. 剩餘項目按非增加高度排序。沿着高度h0的線從左到右打包物品的級別（以不增加的高度順序）。

   3. 然後在中間畫一條垂直線，將條切成兩半（注意這條線可能會切割一部分在右半部分包裝的物品）。繪製兩條長度爲一半的水平線段，其中一條橫跨左側（稱爲左側基線），另一條橫跨右側（稱爲右側基線），儘可能低以使兩條線不交叉任何項目。

   4. 選擇較低高度的左側或右側基線，並將一層物品打包到條帶的相應一半，直到下一個物品太寬。

   形成一個新的基線，並在較低的基線上重複步驟（4），直到所有項目都打包。
   時間複雜度：O（n·log n）。
   Sleator算法的逼近比是2.5。

Answer 7

你需要的是在 https://github.com/nothings/stb/blob/master/stb_rect_pack.h

樣本：

stbrp_context context; 

struct stbrp_rect rects[100]; 

for (int i=0; i< 100; i++) 
{ 
    rects[i].id = i; 
    rects[i].w = 100+i; 
    rects[i].h = 100+i; 
    rects[i].x = 0; 
    rects[i].y = 0; 
    rects[i].was_packed = 0; 
} 

int rectsLength = sizeof(rects)/sizeof(rects[0]); 

int nodeCount = 4096*2; 
struct stbrp_node nodes[nodeCount]; 


stbrp_init_target(&context, 4096, 4096, nodes, nodeCount); 
stbrp_pack_rects(&context, rects, rectsLength); 

for (int i=0; i< 100; i++) 
{ 
    printf("rect %i (%hu,%hu) was_packed=%i\n", rects[i].id, rects[i].x, rects[i].y, rects[i].was_packed); 
}