將大矩形劃分爲小矩形（2D Packing）

我需要將大的靜態大小的矩形分割成小矩形的算法。我一個完美的實現是這樣的：將大矩形劃分爲小矩形（2D Packing）

struct RECT 
{ 
    int l,t,r,b; 
}; 

class BigRect 
{ 
public: 
    // width and height of big rect 
    BigRect(unsigned width, unsigned height); 

    // returns -1 if rect cannot be allocated, otherwise returns id of found rect 
    int GetRect(unsigned width, unsigned height, RECT &out); 

    // returns allocated rect to big rectangle 
    void FreeRect(int id); 
}; 

void test() 
{ 
    BigRect r(10, 10); 

    RECT out; 
    r.GetRect(4, 4, out); // rect found ({0,0,4,4} for example), returns 1 
    r.GetRect(5, 5, out); // rect found ({4,0,9,5} for example), returns 2 

    r.GetRect(6, 6, out); // no place found for rect, returns -1 
    r.FreeRect(2);  // add {4,0,9,5} back to rect 

    r.GetRect(6, 6, out); // rect found (4,0,10,6) 
}

所以我需要GetRect和FreeRect方法算法。任何想法和鏈接將不勝感激。

來源

2011-05-23 pure cuteness

這氣味像功課。 – 2011-05-23 14:31:21

對子矩形的分配方式有任何限制嗎？例如。有沒有一個目標可以有效地包裝矩形，或者你可以將它們粘在任何適合的地方？ – verdesmarald 2011-05-23 14:32:24

@ Jean-Paul Calderone。這不是功課。 @veredesmarald當然最好能有效地分配它們。 – 2011-05-23 14:34:58

你想要做的是在線2D裝箱包裝。它是在線的，因爲在您試圖將它們放入大圖片之前，您手邊沒有全部小圖片。此外，一些小圖片將被「釋放」，其空間將被釋放。另一方面，離線算法允許您在打包之前將小圖片從最大到最小排序。

這裏是一篇文章，調查的2D包裝的藝術狀態：Survey on two-dimensional packing。這很理論。

這篇文章A New Upper Bound on 2D Online Bin Packing引用了其他描述在線2D打包算法的文章。

遊戲世界中的人們和你有類似的問題;他們稱之爲紋理包裝或texture atlas。但是，他們使用離線算法。

John Ratcliff在紋理包裝上發佈了blog article。

另見gamedev此相關的問題：https://gamedev.stackexchange.com/questions/2829/texture-packing-algorithm

來源

2011-05-23 15:52:46

據我瞭解，在離線打包時，我不能將一些freespace添加回矩形（在我的示例中爲'BigRect :: FreeRect'）？我現在很困惑。 – 2011-05-23 16:00:54

哎呀，它是在線包裝。編輯答案。 – 2011-05-23 16:12:10

我剛剛讀了你的答案。我在開始時沒有全部圖像。所以我認爲我需要一些在線算法而不是離線。 – 2011-05-23 16:13:50

將大矩形劃分爲小矩形（2D Packing）

回答

相關問題