構(gòu)建CCS Sprites快而優(yōu)的矩形打包算法
介紹
（譯者注：略）
內(nèi)容
（譯者注：略）
安裝
（譯者注：略）
簡單的解決方案
這有幾個簡單的方案講述如何打包多個矩形到一個封閉的矩形中：
l 你可以將所有矩形在水平方向上一字排開，就像這樣：
這很簡單也很快，并且可以在所有矩形高度一致時表現(xiàn)的很好。
l 或者你可以在水平方向上排列，就像這樣：
這依舊簡單快捷，并且當(dāng)所有矩形寬度一致時表現(xiàn)良好。
但是，這些方案在這些矩陣擁有不同的寬度和高度時留下大量被浪費的空間。這很煩人。所以接下來我們將關(guān)注在打包不同寬度和高度矩形時將這種浪費最小化，當(dāng)然也要盡可能的快和簡單。
基本算法
打包多個矩形到盡可能小的封閉矩形的基本算法在Richard E. Korf的文章有有被描述：Optimal Rectangle Packing: Initial Results。
1.根據(jù)高度對矩形進行排序，最高的排第一。
2.閉合矩形初始設(shè)置為：高度為最高矩形的高度，寬度無限大。
3.將矩形一個個的放入封閉矩形中，由最高的矩形開始，到最矮的矩形結(jié)束。放置每個矩形時盡可能靠左。如果有多個左邊位置，使用最高的那個（If there are several left most locations, use the highest one ）。比如：
a) 
b) 
c) 
d) 
e) 
4.讓閉合矩形的寬度等于弄好的所有矩形的總寬度。即：將閉合矩形的右邊緣向左移動，直到接觸到最右邊矩形的右邊緣。這樣的話，閉合矩形寬度正合適。
5.你已經(jīng)將所有矩形放置在閉合矩形內(nèi)了嗎？如果這樣的話：
l 如果你得到的這個閉合矩形是目前最小的且“成功”的，將它保存起來。
l 試著寬度減一來獲取更小的閉合區(qū)域。
6.然而，如果你沒有全部將矩形放置在閉合矩形內(nèi)，很顯然閉合矩形小了。如果這樣的話，將高度加一。（譯者注：就這樣重復(fù)執(zhí)行放置矩形到閉合矩形內(nèi)，直到得到一個原始最佳寬度減一×原始高度不斷加一加到能將所有矩形都放入這個新閉合矩形內(nèi)，其實并不是笨笨的加一，往下看，改進基本算法部分有提到這步具體做法）請注意，減寬度加高度實際上意味著我們將閉合矩形的范圍從矮寬到高瘦。比如，當(dāng)寬度被減少、高度被增加幾次后，你可能會得到如下的序列：
a) 
b) 
c) 
d) 
e) 
7.如果你得到的閉合矩形的總面積（寬×高）比所有將放入其中的矩形的面積之和還要小，那這明顯不是一個可行的閉合矩形。高度增加一直到你得到一個可行的閉合矩形。然后進入到下一步。
8.如果你獲得的這個閉合矩形比迄今為止最好的閉合矩形要大，那么對它進行測試并無意義。寬度減一然后重復(fù)第七步來確保不是小了，否則進入下一步。
9.如果你的新的閉合區(qū)域比最寬的矩形要窄，你就可以停下了，并且匯報你得到的最佳閉合矩形。這是因為我們這個算法從不會增加閉合矩形的寬度，并且如果最寬矩形都放不下，這明顯不需要再測試這個閉合矩形了。（If your new enclosing rectangle is narrower than the widest rectangle, you can stop now, and report the best enclosing rectangle you found so far. This is because the algorithm never increases the width of the enclosing rectangle, and if the widest rectangle won't fit, there is obviously no point in testing the enclosing rectangle.）
10.現(xiàn)在你的新閉合矩形既不太小，也不太大，返回第三步去看看你是否可以將所有矩形放進去。
這個算法已經(jīng)在下載工程Mapper中的類MapperOptimalEfficiency的函數(shù)Mapping中實現(xiàn)了。
稍后我們將看看如何將這個基本算法做的更快些。但是首先讓我們看看如何將矩形放入閉合區(qū)域中，最主要的是如何記錄已放入的矩形來防止新加入矩形與他們重疊。
在一個給定的閉合矩形內(nèi)安放矩形而不與其他矩形重疊
上面基本算法中的第三步寫到“將矩形一個個的放入閉合矩形內(nèi)，從最高的矩形開始，最矮的結(jié)束。放置每個矩形時盡可能的靠左，如果有好幾個左邊位置，用最高的那個。”
為了找到最左最高的位置來放置一個給定寬度和高度矩形而不與其他矩形重疊，我們需要用一些數(shù)據(jù)結(jié)構(gòu)來記錄閉合矩形中已被占用的區(qū)域。并且這個數(shù)據(jù)結(jié)構(gòu)必須既簡單（這樣不容易出錯）又能快速找到矩形可以被放置的那個最左最高位置。
可以使用一個二維布爾數(shù)組，每個格子代表閉合區(qū)域中的一個像素。每個布爾標(biāo)記這個像素是否被占用還是空閑。然而，當(dāng)你為一個矩形找空時需要訪問很多像素，這個方案簡單但效率低下。
另一個方案，可以保存閉合矩形中每個矩形的寬和高以及他們的X/Y方向的偏移。這個數(shù)據(jù)結(jié)構(gòu)比起二維像素數(shù)據(jù)擁有更少的成員變量，但是在空間足夠的情況下，計算出這個最左最高的位置使用這個結(jié)構(gòu)將既復(fù)雜又慢。
我想出的解決方法是：使用一個動態(tài)的二維布爾數(shù)組表示占用或空閑，但是為每行存儲一個高度，每列存儲一個寬度，這樣列數(shù)和行數(shù)可以保持在最小。這樣既減少復(fù)雜度又降低了需要訪問的格子數(shù)（和因此花費的時間）。下面是添加矩形時這個方法如何工作的（白色格子是未被占用，綠色格子是被占用，暗綠色格子是剛被最后一次添加矩形占用的）：
1.首先，只有一行和閉合矩形一樣高，一列和閉合矩形一樣寬。這意味著只有一個格子。
2.當(dāng)添加第一個矩形時，找出最左最高的格子很輕松，因為這兒只有一個。確保他對于這個矩形足夠大也很簡單。所以我們繼續(xù)，并把它放置在格子的左上角。
我們現(xiàn)在有個格子被部分占用，部分沒有被占用。然而一個格子只能是一種狀態(tài)。為了解決這個問題，將單行分開、單列分開，這樣我們就獲得了四個格子，這樣他們要么被占用，要么沒有被占用：
3.該添加第二個矩形了。首先檢查最左邊的列。從上到下遍歷這個列中所有的格子直到你找到一個空閑的格子。然后檢查是否能將矩形放在那兒。
最左列有一個空閑格，但是垂直方向上不夠放下這個矩形。那么在右邊一列如法炮制的查找。
第二列中，最高的那個格子是空間的，并且足夠放置矩形，那么這很簡單。將矩形放在那。和第一個格子放置時一樣，矩形相對于格子比較小，導(dǎo)致一個格子部分被占用，部分未占用。所以分割該格子的行和列來確保格子又回到不是被占用就是未被占用的狀態(tài)。注意結(jié)果，第一個矩形所占用的格子現(xiàn)在被劃分為二了，這沒關(guān)系的。
4.第三個矩形也走同樣的流程。然而，因為這個矩形有點矮，所以最左列有足夠的空間來放置他。再一次，在這個格子中相交的行列被分割了，來取保所有格子要么是占用要么是未被占用。
5.第四個矩形走同樣的流程。如果最左列剩余垂直空間不足，那就在他右邊試試。最左列最高的那個格子足夠高來放置矩形，但是不夠?qū)挕Ｋ詼y試右邊的列看是不是有足夠空閑的格子來安放矩形。可以看到起始列和他右邊的列組合起來在水平方向上就有足夠的空間安放這個矩形，也就是說這個矩形可以用兩個格子來放置。再一次格子在行列上被分割，確保格子被占用或非占用。
6.第五個矩形，依舊從左到右的檢查列。第二列有一個空閑格，但是對于該矩形在垂直方向上沒有足夠的空間。第三列有兩個不相連的空閑格子，但是他倆高度都不夠，并且垂直空間上也無法和其他格子結(jié)合湊足垂直空間來放置矩形。
在第四列，有一個空間格子，他既不夠高也不夠?qū)拋戆卜啪匦巍Ｋ詸z查右邊列的格子和下面行的格子看是不是有足夠空閑的格子可以組合來容納矩形。在這種情況下，這證明是可行的。再一次，發(fā)生了行列分割來保證格子占用或非占用的唯一性。
通過運行下載文件中的網(wǎng)站，你可以看到更多的例子。他也演示了不是所有矩形都能放置的情況。
找到可以放置矩形的最左最高格子和檢查周圍格子的代碼在下載中的Mapper工程的Canvas類中可以找到。二維動態(tài)數(shù)組在DynamicTwoDimensionalArray類中實現(xiàn)。因為他被經(jīng)常使用，這個類為了性能被高度優(yōu)化，尤其是分割行和列時。
對基本算法的改進
當(dāng)學(xué)習(xí)下載的test site中生成的測試?yán)訒r，下面的改進會很明顯。在寫改進在下載的代碼中有的。我在文獻中沒有找到這些改進的方法，所有你可以先讀一下他們：
l 減小封閉區(qū)域?qū)挾群螅黾幼銐虻母叨?/span>
l 放置所有矩形失敗后，增加足夠的高度
l 通過設(shè)置效率的上限獲得加速
減小封閉區(qū)域?qū)挾群螅黾幼銐虻母叨?/span>
看下下面那個一輪基本算法生成的閉合矩形：
根據(jù)基本算法，你應(yīng)該將閉合矩形的寬度減一，然后試著重新安放所有矩形。然而，如果你簡單的將寬度減一，你知道暗綠色矩形一定會超出閉合矩形的右手邊界，對它來說無處容身了就，所以下次嘗試安放所有矩形時一定會失敗。
另外，算法說當(dāng)失敗的時候?qū)㈤]合矩形的高度加一。但是，因為暗綠色矩形的高度是十個像素，明顯高度加一是不夠的。所以基本算法接下來一定會進行十次失敗的嘗試去安放所有矩形，這很費也沒啥必要。
可以通過記錄接觸到閉合矩形右手邊界最高矩形的高度來進行優(yōu)化。如果你成功安放好所有矩形并將閉合矩形的寬度減一后，可以將閉合矩形的高度加上超出閉合矩形右方的最高矩形的高度。這樣算法可以在新的閉合矩形內(nèi)為超出右方的最高矩形找到新的位置：
放置所有矩形失敗后，增加足夠的高度
看看下面的序列。使用該算法安放好四個矩形后，放置第五個矩形時失敗了。
1 2 3 4 放置矩形失敗
這次失敗后，基本算法將對閉合矩形的高度加一，然后重新放置矩形。但是僅僅加一的話，前四個矩形還是安放在一模一樣的位置，最終安放第五個矩形還是失敗。這個算法將會繼續(xù)高度加一繼續(xù)嘗試，可能還是這種情況，周而復(fù)始。這些毫無意義的嘗試占用了大量的時間。
使用下面兩個高度中較小的值，來代替高度加一。
1．無法安放的矩形的高度
2．可以讓閉合矩形對前四個矩形可以進行和之前不同排列的高度——這樣至少給算法一個機會來安放第五個矩形
通過選擇兩項中較小的一個，你將可能得到更接近最小的閉合矩形。
算出上面第二點中提到的高度并不難，只要你意識到這個算法首先試著在最左列放置每個矩形，如果失敗了就查看右邊這列再次嘗試，直到成功。每次在列中放置矩形失敗，那是因為列的底部空閑區(qū)域?qū)τ诰匦蝸碚f太矮了——空閑高度不足。
拿第二個矩形來說，第一列還差30個像素的空閑高度：
也就是說，如果閉合矩形再高那么30個像素，第二個矩形就可以放在最左邊那列了。
同樣的，第三個矩形要放在極左列的高度還差25像素，在第二行還差15像素。所以如果閉合矩形再高15個像素，第三個矩形放置的就會不同了：
第四個矩形在極左列還差10像素的空閑高度。所以如果閉合矩形如果高10個像素，第四個矩形也可能被放置在第一列。
我們想要增加閉合矩形所需最小的高度使矩形能排的不同即可。這里，最小的所有列所需空閑高度是10個像素（應(yīng)用于第四個矩形放在極左列）。由于第五個矩形高了10個像素放置失敗，我們需要將閉合矩形的高度增加10像素，希望在下次嘗試時放置第五個矩形：（Seeing that the fifth rectangle that failed to be placed is higher than 10px, we need to increase the height of the enclosing rectangle by 10px to have any hope of placing the fifth rectangle at the next try: ）
1 2 3 4 5
這意味著為了防止那么多的失敗閉合矩形，算法需要簡單的記錄下來在列中放置矩形時最小的空閑高度差額。當(dāng)放置矩形失敗的時候，可以用這個最小空閑高度差額增加閉合矩形的高度——如果無法放置矩形的高度更小的話就用他。
這種優(yōu)化不能確保下一次嘗試就能得到成功的閉合矩形。比如，新的高度下，閉合矩形可能會比目前的最佳閉合矩形要打，這種情況下算法將要開始減小他的寬度。這樣的話可能會在下次嘗試時無法安置所有的矩形因為降低了寬度。此優(yōu)化是為了減少嘗試的次數(shù)而非一次成功。
閉合矩形大小和速度間的取舍
如果你決定你可以忍受一定水平的空間浪費，一種方法是減少計算時間來產(chǎn)生閉合矩形，就是當(dāng)達到這個水平時讓代碼停止繼續(xù)獲得更小的閉合矩形。
另一種方法提高速度是當(dāng)找到預(yù)設(shè)次數(shù)成功閉合矩形后就讓算法停止。你可以設(shè)置限制為一次或兩次。這很有吸引力，當(dāng)你發(fā)現(xiàn)這種方法可以讓你得到一個足夠好的結(jié)果并且提高了不少速度。
為了讓你自己選，在MapperOptimalEfficiency類中提供了第二個構(gòu)造函數(shù)，通過額外的參數(shù)設(shè)置這兩個選項（with additional parameters to set these two cut offs ）。
矩形打包器的軟件接口
下載Mapper項目中有文章中描述的矩形打包器的實現(xiàn)。他給外部提供了一個良好的接口。test side使用了這個接口。為了讓你更容易的學(xué)習(xí)或者在你的項目使用這些代碼，下面提供了接口的描述。
你會發(fā)現(xiàn)代碼涉及到的是圖片和精靈而不是矩形和封閉矩形。這是因為他是打算作為實時精靈生成器項目（還未完成）的一部分實現(xiàn)的。
接口
（譯者注：略）
實現(xiàn)
（譯者注：略）
用法
（譯者注：略）
歷史記錄
（譯者注：略）
許可
（譯者注：略）
關(guān)于作者
（譯者注：略）