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