解決Rectangle Packing問題

加好友 · 發表於 2011-7-8 15:43

馬上加入Android 台灣中文網，立即免費下載應用遊戲。

您需要登錄才可以下載或查看，沒有帳號？註冊

x

問題描述：如何把任意數量任意尺寸矩形集無重複的放到一個面積最小的封閉矩形中。
算法思想：（為了便於描述，把要找的封閉矩形記為a，封閉矩形的集合記為as，把矩形集合記為rs，n為rs中矩形的個數，把可以插入矩形的位置記為corners）
1.把所有矩形集中的矩形按高度從大到小排序，此時rs[0]高度最大
2.把a初始化為：height = rs[0].height，width = rs[0].width + rs[1].width + ...... + rs[n - 1].width，corners初始化為：坐標頂點
3.把rs[0]放入a中，並把由於rs[0]的插入產生的corner放入corners集合中，刪除已經使用的corner，如下圖所示：

登錄/註冊後可看大圖

a1.jpg (8.9 KB, 下載次數: 1)

下載附件保存到相冊

2011-7-8 15:42 上傳

4.從rs[1]到rs[n - 1]，每次插入時選擇可以插入的X值最小的corner，插入成功之後，刪除已經使用的corner，並且插入新產生的corner，由於a的初始化條件，可以保證rs中的所有矩形都可以插入a中
5.所有矩形插入完成後，對a進行「瘦身」，讓a正好包含所有的矩形，並記錄此時a的寬度為width，a的面積為area（此時a是所有符合條件的封閉矩形中的『最狹長』的，令as[0] = a）
6.依次減少a.width，增加a.height，重複3-5，如果a的面積有所減少，則把a插入到as中，直到a.width = rs中最寬矩形的寬度
7.as集合的最後一個元素就是可以包含rs中所有矩形的面積最小的封閉矩形，算法結束
算法實現：
在算法的實現中需要注意的地方：
1.計算由於矩形的插入產生的新的corner（需要考慮很多特殊情況）
2.判斷矩形是否可以插入一個corner
3.數據結構的設計
以下程序是算法最核心的方法，插入矩形，並記錄新產生的corner

private boolean putIn(PngRect png){
if(pngs == null){
pngs = new ArrayList<PngRect>();
pngs.add(png);
png.setStartP(new Point(0,0));
if(png.getHeight() < mHeight){
Rect owner = new Rect(0,png.getStopP().getY(),mWidth,mHeight);
Corner corner = new Corner(new Point(0,png.getHeight()),owner);
corners.add(corner);
}
if(png.getWidth() < mWidth){
Rect owner = new Rect(png.getStopP().getX(),0,mWidth,mHeight);
Corner corner = new Corner(new Point(png.getWidth(),0),owner);
corners.add(corner);
}
return true;
}else{
Corner corner;
int x;
int y;
Rect owner;
for(int i = 0; i < corners.size(); ++i){
corner = corners.get(i);
x = corner.getPoint().getX();
y = corner.getPoint().getY();
owner = corner.getRect();
Point startP = corner.getPoint();
int endX = owner.right;
int endY = owner.bottom;
/*
* 可以放進該corner，此處存在覆蓋問題，需要判斷四條邊是否有點在已經被使用，如果是，則返回，試下一個corner
* v0-----v1
* | |
* | a |
* | |
* v2-----v3
* 同時為了防止完全重疊，還需要判斷額外一個點,例如圖中的a點
*/
if(x + png.getWidth() <= mWidth && y + png.getHeight() <= mHeight){
Point v0 = startP;
Point v1 = new Point(startP.getX() + png.getWidth(),startP.getY());
Point v2 = new Point(startP.getX(),startP.getY() + png.getHeight());
Point v3 = new Point(startP.getX() + png.getWidth(),startP.getY() + png.getHeight());
Point a = new Point(startP.getX() + png.getWidth()/2,startP.getY() + png.getHeight()/2);
if(contains(v0,v1,true) || contains(v1,v3,false) || contains(v2,v3,true) || contains(v0,v2,false) || contains(a)){//有可能正好落在邊上
continue;
}
// if(contains(a) ||contains(v0) || contains(v1) || contains(v2) || contains(v3) ){//有可能正好落在邊上
// continue;
// }
if(x + png.getWidth() < endX){
corners.add(i + 1,new Corner(new Point(x + png.getWidth(),y),
new Rect(x + png.getWidth(),y,mWidth,mHeight)));//此處owner可能為空
}
if(y + png.getHeight() < endY){
corners.add(i + 1, new Corner(new Point(x,y + png.getHeight()),
new Rect(x,y + png.getHeight(),mWidth,mHeight)));
}
corners.remove(i);
sortCorners();
png.setStartP(corner.getPoint());
pngs.add(png);
return true;
}
}
}
return false;
}

複製代碼

算法實現的效果如下所示：

登錄/註冊後可看大圖

[資料] 解決Rectangle Packing問題

馬上加入Android 台灣中文網，立即免費下載應用遊戲。

評分

警告：您的Adblck已啟用