長方形の詰め込み問題のBLF法的な何か

頼まれたので作ってみました

ただBLF法は全くわかってない感じで「どうせこんな感じでしょ　それっぽくなればいいや」って実装です

processingで作ってみました．環境はeclipse使ってます．

「できるだけ小さいフィールドの中にすべての箱を詰める」
ではなく
「固定された大きさのフィールドの中で出来るだけみっちり箱を詰める，入らなかったのは同じ大きさの次のフィールドに詰める」
というプログラムです．

ぱぱっと解説

なんとなく上手く動いてるのでこれでいいかなあと思ってやってます．大きなフィールドには対応できないと思います．

まずうまくいくように，箱を大きい順にソートをしています．今回は面積でソートしました．

まず(0,0)を配置候補に上げます．
配置候補に上がった中で，①配置可能な候補の中でyが一番小さく，その中でxが一番小さい候補を探します．
もし候補がなければ，次の箱が入るかを調べます．最後まで見て候補がなかったら次のフィールドに移動します．
見つけた候補(a,b)に箱を配置して，候補に(a+w,b)と(a,b+h)を追加します．
これをすべての箱が配置されるまで繰り返します．

入るかどうかの判定は2次元配列でマップ作ってそこでやってます．

ソース

Main.java

package darell;

import java.util.ArrayList;
import java.util.Arrays;

import processing.core.PApplet;

//BLFするクラス
class BLF {
    static int W, H;
    int w[], h[], x[], y[], id[];// クラス化めんどかった idは板の数

    // 適当なコンスラクタ いじるべきはw,hのみ
    BLF(int w[], int h[]) {
        id = new int[w.length];
        x = new int[w.length];
        y = new int[w.length];
        this.w = w;
        this.h = h;
    }

    void solve() {
        // 大きい順にソート（なくても動くはず）
        sort();
        // しきつめていこう
        blf();
    }

    void sort() {
        // 大きい順にソート
        int area[] = new int[w.length];
        for (int i = 0; i < area.length; i++) {
            area[i] = w[i] * h[i];
        }
        // めんどいので選択ソート
        for (int i = 0; i < area.length; i++) {
            int t = i;
            for (int j = i + 1; j < area.length; j++) {
                if (area[j] > area[t]) {
                    t = j;
                }
            }
            System.out.println(i + "," + t);
            swap(area, i, t);
            swap(w, i, t);
            swap(h, i, t);
        }
    }

    // 交換用
    void swap(int d[], int i, int j) {
        int t = d[i];
        d[i] = d[j];
        d[j] = t;
    }


    void blf2(){
        for(int i=0;i<id.length;i++){
            id[i]=-1;//回ってない報告
        }

        int id1 = 0;
        while (true) {
            int i = 0;
            System.out.println(id1 + "の板に移動");
            boolean map[][] = new boolean[W][H];// 敷き詰めた時のマップを作成（板ごとに作り直す）
            ArrayList<int[]> pos = new ArrayList<int[]>();// 挿入位置の候補
            pos.add(new int[] { 0, 0 });// 右上を基準にする
            while (!pos.isEmpty()) {
                if(id[i]!=-1){
                    //配置済みなら処理をしない
                    i++;
                    if (i >= x.length) {
                        // 最後まで探索して入らなかったのでその板を抜ける
                        break;
                    }
                    continue;
                }
                // 一つのプレートでの処理 置く場所がなくなったら次のプレートに移動
                int p[] = get(pos, map, i);// いい感じの配置場所を探す
                if (p == null) {
                    // 入る候補が無いなら，次の箱に行く
                    System.out.println("置く場所がない");
                    i++;
                    if (i >= x.length) {
                        // 最後まで探索して入らなかったのでその板を抜ける
                        break;
                    }
                    continue;
                }
                set(p, i, map, id1);// 置く
                pos.remove(p);// 置いたので候補を削除
                // 候補を追加
                pos.add(new int[] { p[0] + w[i], p[1] });
                System.out.println((p[0] + w[i]) + "," + p[1] + "候補追加");
                pos.add(new int[] { p[0], p[1] + h[i] });
                System.out.println(p[0] + "," + (p[1] + h[i]) + "候補追加");
                i++;
                boolean ok=true;
                for(int j=0;j<id.length;j++){
                    if(id[j]==-1){
                        ok=false;
                        break;
                    }
                }
                if(ok){
                    return;
                }
                if (i >= x.length) {
                    // 全部配置し終わったらその板での処理を終わる
                    break;
                }
            }
            //置く候補がなくなった→次の板に行く
            id1++;
        }
    }

    int[] get(ArrayList<int[]> pos, boolean map[][], int in) {
        // 入れる候補の中で，ちゃんと入れるスペースがある候補なのかを調べる
        // その中で一番下のもの（yが低いもの）を取り出す
        // 同じ高さのものの中からはxが一番小さいものを取り出す
        System.out.println("入る候補の可能性の探索");
        int xy[] = null, index = -1;
        for (int i = 0, n = pos.size(); i < n; i++) {
            int tmp[] = pos.get(i);
            if (!ifin(tmp, in, map)) {
                System.out.println("入らない");
                continue;
            }
            if (xy == null) {
                System.out.println("初期値の設定");
                xy = tmp;
                index = i;
                continue;
            }
            if (xy[1] > tmp[1] || (xy[1] == tmp[1] && xy[0] > tmp[0])) {
                index = i;
                xy = tmp;
            }
        }
        return xy;
    }

    void set(int pos[], int index, boolean map[][], int id1) {
        // 配置操作
        // mapも更新しないと入るかどうか判定がバグる
        for (int i = 0; i < w[index]; i++) {
            for (int j = 0; j < h[index]; j++) {
                map[i + pos[0]][j + pos[1]] = true;
            }
        }
        x[index] = pos[0];
        y[index] = pos[1];
        id[index] = id1;
    }

    boolean ifin(int pos[], int index, boolean map[][]) {
        // プレートの中に中に入るかどうか
        if (pos[0] + w[index] >= W || pos[1] + h[index] >= H) {
            System.out.println("まず範囲外");
            return false;
        }
        for (int i = 0; i < w[index]; i++) {
            for (int j = 0; j < h[index]; j++) {
                if (map[i + pos[0]][j + pos[1]])
                    return false;
            }
        }
        return true;
    }
}


// 以下 表示用プログラム
public class Main extends PApplet {
    public static void main(String[] args) {
        // TODO 自動生成されたメソッド・スタブ
        PApplet.main("darell.Main");
    }

    int time = 4;

    public void setup() {
        BLF.W = 140;
        BLF.H = 140;
        size(BLF.W * time, BLF.H * time);
    }

    public void draw() {
        background(200);
        stroke(0);
        fill(255);
        for (Rect r : rects) {
            r.draw();
        }
        stroke(255, 0, 0);
        noFill();
        if (mousePressed) {
            rect(mouseX, mouseY, mouse[0] * time - mouseX, mouse[1] * time - mouseY);
        }
    }

    ArrayList<Rect> rects = new ArrayList<Rect>();
    int mouse[] = new int[2];

    public void keyPressed(){
        println("a");
        int n=100;
        int x[] = new int[n];
        int y[] = new int[n];
        int w[] = new int[n];
        int h[] = new int[n];

        for(int i=0;i<n;i++){
            w[i]=(int)random(35)+5;
            h[i]=(int)random(35)+5;
        }
        BLF blf = new BLF(w, h);
        blf.solve();
    }

    public void mousePressed() {
        mouse = new int[] { mouseX / time, mouseY / time };
    }

    public void mouseReleased() {
        rects.add(new Rect(mouseX / time, mouseY / time, mouse[0], mouse[1]));
        int x[] = new int[rects.size()];
        int y[] = new int[rects.size()];
        int w[] = new int[rects.size()];
        int h[] = new int[rects.size()];
        for (int i = 0; i < x.length; i++) {
            Rect r = rects.get(i);
            x[i] = -1;
            y[i] = -1;
            w[i] = r.w;
            h[i] = r.h;
        }
        System.out.println("--------------------");
        BLF blf = new BLF(w, h);//呼び出し方
        blf.solve();//呼び出し方
        rects = new ArrayList<Rect>();
        System.out.println(Arrays.toString(blf.x));
        for (int i = 0; i < blf.x.length; i++) {
            Rect r = new Rect();
            r.x = blf.x[i];
            r.y = blf.y[i];
            r.w = blf.w[i];
            r.h = blf.h[i];
            println(r.x);
            rects.add(r);
        }
    }

    class Rect {
        int x, y, w, h;

        Rect() {

        }

        Rect(int x1, int y1, int x2, int y2) {
            x = min(x1, x2);
            y = min(y1, y2);
            w = max(x1, x2) - x;
            h = max(y1, y2) - y;
        }

        void getXY(int index, int x[], int y[]) {
            this.x = x[index];
            this.y = y[index];
        }

        void draw() {
            rect(x * time, y * time, w * time, h * time);
        }

    }

}

言い訳

クラスとか使って書けばもっと見やすくなると思いますし，
優先度付きキューとか，Comparatorとか使うとすっきりします．
java以外での用途があったため，できるだけ配列だけを用いて作成しました＼(^o^)／