可變尺寸塊的高效定位

Question

我有矩形（長度和寬度）的數組。不保證是方形的，但始終保證是整數。我想盡可能有效地將塊定位在座標系中，以便包含所有元素的邊界框儘可能小。我也想傾向於一個廣場。大小方面的差異不會太大，但我想要一個通用的算法。

我發現這有點難以搜索，只是找人指點我在正確的方向。只需要尋找僞代碼（語言無關緊要）或可以在Java中實現的庫（如果需要的話）。性能是一個問題，所以我真的需要它在各方面都儘可能高效。

注意：如果我只限於正方形，這會變得更容易，那可能是一個選項。

Answer 1

Packing problem文章維基百科鏈接到this algorithm，描述在this paper - 「最佳矩形包裝：初步結果」。

Answer 2

我不確定它如何與E先生指出的算法相比，但是一旦我構建了一個窗口系統，並且我需要在屏幕外存儲矩形圖片。我的方法是這樣的：

想想存儲空間向左傾斜45度，所以你有一個V形倉。 它有一個「谷點」，在最底層（起源）

\ /
\/
    \/ 

下降一個塊，所以該塊的底角是在峯谷點。

現在，從左到右，您有兩個谷點，您可以在其中放置其他塊。 每次將某個塊放入谷點時，都會修改谷點的列表。

\ /
\/\/ 

它確實浪費空間，如果你把一大塊成小塊做了一個谷點，所以最好是把大塊第一，如果可能的話。當你放入一個塊時，你可以選擇浪費最小空間的谷點。

正如我所說，我不知道它與其他算法相比如何，但它很簡單。