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;
- }