將無間隙圖像分組到一個大圖像

Question

我正在寫一個C++程序來放大一些較小的圖像放大圖像，使圖像之間沒有空白。
實施例：
鑑於尺寸2×2（代碼0），4×4（碼1），5×5（代碼2）
代替它們大小的4x6的較大的圖像上的圖像
一種可能的解決方案可以是：

0a 0a 1a 1a 1a 1a 
0a 0a 1a 1a 1a 1a 
0b 0b 1a 1a 1a 1a 
0b 0b 1a 1a 1a 1a 

另一個可能是所有2x2圖像或放置在其他地方的4x4圖像，2x2來覆蓋剩餘的空白。

我能想到的最好的是：
1.選擇最小尺寸的圖像，並用它填充圖像。 （0,0）

2.然後選擇下一個較大的圖像（這裏是4x4），製作一個4x4的列表，嘗試替換一些一套是相鄰的2×2的圖像。刪除那些從2x2的名單，並在這個形象的開始點的4x4的列表中的條目。

3.一直這樣做，直到沒有縫隙留下。

隨機性可以實現通過從較小的列表中選擇隨機圖像來製作更大的圖像。

我們可以使用任意數量的圖像副本（0a，0b表示圖像0的2個副本），但希望使用大部分較小的圖像以適合較大的圖像。
是否有預先存在的算法來解決這個安置問題，這些安置問題實施起來很簡單，並解決了保證沒有差距和完全隨機性的問題？

Answer 1

蠻力的方法是很容易實現。從一些任意角落開始（比如左上角），然後嘗試將每個可用形狀放置在該位置：如果它適合，找到下一個尚未覆蓋的位置並遍歷那裏的可用形狀等。很容易做到遞歸。

爲了說明這種方法如何處理2×2（代碼0），4×4（代碼1），5×5（代碼2）到4×6的示例情況，可以將遞歸簡化爲探索具有左分支的人工樹， 2×2碼的下一個空位置（X）0中，中間分支放置一個4×4碼1，右支5x5的代碼2.

          start 
        /     |     \ 
       0a 0a X _ _ _    1a 1a 1a 1a X _   finito 
       0a 0a _ _ _ _    1a 1a 1a 1a _ _ 
       _ _ _ _ _ _    1a 1a 1a 1a _ _ 
       _ _ _ _ _ _    1a 1a 1a 1a _ _ 
      /  |      /  | \ 
0a 0a 0b 0b X _ 0a 0a 1a 1a 1a 1a 1a 1a 1a 1a 0a 0a finito 
0a 0a 0b 0b _ _ 0a 0a 1a 1a 1a 1a 1a 1a 1a 1a 0a 0a 
_ _ _ _ _ _ X _ 1a 1a 1a 1a 1a 1a 1a 1a X _ 
_ _ _ _ _ _ _ _ 1a 1a 1a 1a 1a 1a 1a 1a _ _ 
/ | \   / | \   / | \ 
/  finito  / finito  / finito 
/     /    /
0a 0a 0b 0b 0c 0c 0a 0a 1a 1a 1a 1a 1a 1a 1a 1a 0a 0a 
0a 0a 0b 0b 0c 0c 0a 0a 1a 1a 1a 1a 1a 1a 1a 1a 0a 0a 
X _ _ _ _ _ 0b 0b 1a 1a 1a 1a 1a 1a 1a 1a 0b 0b 
_ _ _ _ _ _ 0b 0b 1a 1a 1a 1a 1a 1a 1a 1a 0b 0b 
    /
    etc 

如果要加快這，你可以：

• 修剪遞歸過程中傳遞的「代碼」，使區域明顯過大以適應剩餘的空間是不考慮的。在寬度和高度上進行過濾都是理想的，但即使在對角線長度上進行過濾也是有用的。

• 保存排列整體形成矩形區域的區域，以便您可以考慮包含10x10的語言安排，然後如果解決30x20問題，則不必從頭開始重新制作涉及10x10解決方案排列的解決方案。擴展這一點，您可以將解決方案報告爲樹。

• 避免/最小化從頭開始的再生解決方案，這些解決方案是現有解決方案的鏡像，例如，通過讓「代碼」的最外層循環在中途停止。

Answer 2

你應該做的第一件事是檢查如果你可以就大一個適合smalles圖像。爲了做到這一點，你應該檢查較小圖像的總面積，看它是否小於或等於大圖像區域。如果問題是可以解決的，你應該按照尺寸（降序，最大的第一）對圖像進行分類，並使用暴力。請記住排序部分 - 它會減少您需要執行的提款次數。