Gfrktyl

I have written a Java Program to place a bunch of rectangles
into the smallest possible rectangluar area(no overlapping and rotating).

Here is a short summary:

I calculate minArea and maxArea:

minArea: minArea is sum up all given rectangle areas.

maxArea: put all given rectangles side by side, maxArea is rectangle area in which all given rectangles fit in.

Between minArea and maxArea must exist the smallest rectangular area, in which all given rectangles fit in.

For each rectangular area between minArea and maxArea I try recursiv, if all given rectangles fit in the rectangular area.

Example input/output:

(height,width of rectangles)



2,3

4,4

5,5

7,2

1,1

9,3



1  1  1  2  2  2  2  6  6  6 

1  1  1  2  2  2  2  6  6  6 

4  4  5  2  2  2  2  6  6  6 

4  4  0  2  2  2  2  6  6  6 

4  4  3  3  3  3  3  6  6  6 

4  4  3  3  3  3  3  6  6  6 

4  4  3  3  3  3  3  6  6  6 

4  4  3  3  3  3  3  6  6  6 

4  4  3  3  3  3  3  6  6  6 

0 represents free space, all other numbers are for differentiating rectangles.

RectanglePacking.java:

import java.util.ArrayList;

import java.util.Scanner;

import java.awt.Point;

import java.io.IOException;





class Rectangle {



public int id;

public int width;

public int height;



public Rectangle(int height, int width, int id) {

    this.width = width;

    this.height = height;

    this.id = id;

  }

}



public class RectanglePacking {



private ArrayList<Rectangle> rectangleList = new ArrayList<Rectangle>(); 

private int minArea;

private int maxArea;





private int getMinArea() {



    for (Rectangle r : rectangleList) {

        minArea = minArea + r.height * r.width;

    }       

    return minArea;

}





private int getMaxArea() {



    int totalWidth = 0;

    int height = 0;

    int maxHeight = 0;



    for (Rectangle r : rectangleList) {

        totalWidth = totalWidth + r.width;

        height = r.height;



        if (height >= maxHeight) {

            maxHeight = height;

        }

    }



    maxArea = totalWidth * maxHeight;

    return maxArea;

}





private ArrayList<Point> possiblePlaces(int field, int id) {



    ArrayList<Point> places = new ArrayList<Point>();



    for (int i = 0; i < field.length; i++) {



        for (int j = 0; j < field[0].length; j++) {



            if (isEmpty(field, i, j, rectangleList.get(id).height, rectangleList.get(id).width)) {

                places.add(new Point(i, j));

            }



        }

    }

    return places;

}





public boolean isEmpty(int field, int x, int y, int height, int width) {



    for (int i = x; i < x + height; i++) {

        for (int j = y; j < y + width; j++) {



            if (i > field.length - 1 || j > field[0].length - 1 || field[i][j] != 0) {

                return false;

            }

        }

    }

    return true;

}





private int markRectangle(int field, int x, int y, int height, int width, int id) {



    id = id + 1;



    for (int i = x; i < x + height; i++) {

        for (int j = y; j < y + width; j++) {



            field[i][j] = id;

        }

    }

    return field;

}





private void removeRectangle(int field, int x, int y, int height, int width) {

    for (int i = x; i < x + height; i++) {

        for (int j = y; j < y + width; j++) {



            field[i][j] = 0;

        }

    }

}





private void placeRectangles(int field, int id) {



    if (id == rectangleList.size()) { 

        printSolution(field);           

        System.exit(0);                          

    } 



    ArrayList<Point> possiblePlaces = possiblePlaces(field, id);



    for (int i = 0; i < possiblePlaces.size(); i++) {



        Point p = possiblePlaces.get(i);

        field = markRectangle(field, p.x, p.y, rectangleList.get(id).height, rectangleList.get(id).width, id);



        placeRectangles(field, id + 1);      

        removeRectangle(field, p.x, p.y, rectangleList.get(id).height, rectangleList.get(id).width);



    }

}





private ArrayList<Point> calcPossibleAreas() {



    ArrayList<Point> possibleAreas= new ArrayList<Point>();

    ArrayList<Point> factors = new ArrayList<Point>();



    for (int i = getMinArea(); i <= getMaxArea(); i++) {



        factors = calcFactors(i);



        for (int j = 0; j < factors.size(); j++) {

             possibleAreas.add(new Point(factors.get(j).x, factors.get(j).y));

        }



    }

    return possibleAreas;

}





private ArrayList<Point> calcFactors(int number) {



    ArrayList<Point> factors = new ArrayList<Point>();



    for (int i = 1; i <= number; i++) {



        if (number % i == 0) {

            factors.add(new Point(i, number/i));

            factors.add(new Point(number/i, i));

        }



    }

    return factors;

}





private void calcMinArea() {



    ArrayList<Point> possibleAreas =  calcPossibleAreas();

    int field;



    for (int i = 0; i < possibleAreas.size(); i++) {



        int x = possibleAreas.get(i).x;

        int y = possibleAreas.get(i).y;



        field = new int[x][y];                      

        placeRectangles(field, 0);              

    }       

}





private void printSolution(int field) { 

    System.out.println("Solution:");

    for (int i = 0; i < field.length; i++) {

        for (int j = 0; j < field[0].length; j++) {



            System.out.print(" "+field[i][j] + " ");



        }

        System.out.println();

    }               

}



public static void main(String args) throws IOException {



    RectanglePacking r = new RectanglePacking();

    Scanner input = new Scanner(System.in);



    int id = 1;



    try {



        while (true) { 



            String line = input.nextLine();



            if (line.equals("")) {

                break; 

            }



            String split = line.split(",");



            int height = Integer.parseInt(split[0]);

            int width = Integer.parseInt(split[1]);



            r.rectangleList.add(new Rectangle(height, width, id));              

            id++;

        }



        input.close();

    } catch (Exception ex) {

        ex.printStackTrace();

    }



    r.calcMinArea();    

  }

 }

How can I improve my code?

Any help is really appreciated.

For each rectangular area between minArea and maxArea I [test recursively] if all given rectangles fit in the rectangular area.

My first comment is that this subproblem seems like a perfect application for Dancing Links.
It won't solve your entire problem (the "area minimization" problem), but it will very quickly solve your subproblem (the "can I fit all the rectangles into this other rectangle" problem).

It is weird that your markRectangle function returns a value (the value of field, which is just its first parameter), but your removeRectangle function returns void. I would expect both of them to return void.

Let's see how you compute "each rectangular area between minArea and maxArea". Slightly reformatted for whitespace:

private ArrayList<Point> calcPossibleAreas() {

    ArrayList<Point> possibleAreas = new ArrayList<Point>();

    ArrayList<Point> factors = new ArrayList<Point>();

    for (int i = getMinArea(); i <= getMaxArea(); ++i) {

        factors = calcFactors(i);

        for (int j = 0; j < factors.size(); ++j) {

             possibleAreas.add(new Point(factors.get(j).x, factors.get(j).y));

        }

    }

    return possibleAreas;

}

Calculating getMaxArea() every time through the loop is silly. Also, you set factors to new ArrayList<Point>() at the top of the function, and then immediately throw away that value by assigning it a new value inside the loop. So at the bare minimum, I'd expect

private ArrayList<Point> calcPossibleAreas() {

    ArrayList<Point> possibleAreas = new ArrayList<Point>();

    int maxArea = getMaxArea();

    for (int i = getMinArea(); i <= maxArea; ++i) {

        ArrayList<Point> factors = calcFactors(i);

        for (int j = 0; j < factors.size(); ++j) {

             possibleAreas.add(factors.get(j));

        }

    }

    return possibleAreas;

}

And then (AFAIK) you can use Java 5's for-each loop:

private ArrayList<Point> calcPossibleAreas() {

    ArrayList<Point> possibleAreas = new ArrayList<Point>();

    int maxArea = getMaxArea();

    for (int i = getMinArea(); i <= maxArea; ++i) {

        for (Point factor : calcFactors(i)) {

             possibleAreas.add(factor);

        }

    }

    return possibleAreas;

}

But all that calcFactors is expensive; and you wind up with a lot of 2xN rectangles that can't possibly be filled. So I would rather write it like this:

private ArrayList<Point> calcPossibleAreas() {

    ArrayList<Point> possibleAreas = new ArrayList<Point>();

    int minWidth = 0;

    int maxWidth = 0;

    int minHeight = 0;

    int maxHeight = 0;

    int minArea = 0;

    for (Rectangle r : rectangleList) {

        minWidth = Math.max(minWidth, r.width);

        minHeight = Math.max(minHeight, r.height);

        maxWidth += r.width;

        maxHeight += r.height;

        minArea += r.width * r.height;

    }

    int maxArea = Math.min(maxWidth * minHeight, minWidth * maxHeight);

    for (int x = minWidth; x <= maxWidth; ++x) {

        for (int y = minHeight; y <= maxHeight; ++y) {

            if (minArea <= x * y && x * y <= maxArea) {

                possibleAreas.add(new Point(x, y));

            }

        }

    }

    // Now sort possibleAreas so we'll try the smaller rectangles first.

    Collections.sort(possibleAreas, new Comparator<Point>() {

        @Override

        public int compare(Point lhs, Point rhs) {

            int la = (lhs.x * lhs.y), ra = (rhs.x * rhs.y);

            return (la < ra) ? -1 : (la > ra);

        }

    });

}

Of course, calcPossibleAreas() is just a preliminary step that will be very fast compared to placeRectangles(). So Amdahl's Law says that you (and I ;)) should spend time optimizing placeRectangles() rather than calcPossibleAreas(). I would recommend looking at some way to eliminate the O(w*h) writes to field — is there some way you can express "all these positions are filled" without actually doing the O(w*h) writes? Vice versa, is there some way you can test "is this a valid placement for my current rectangle" without doing O(w*h) reads?

Rather than looking for places to put each rectangle, it might be better to look for ways to fill each point in the target. Pretend you have your set of rectangles, plus just enough "spare" 1x1 rectangles to fill up the empty spaces. If you try to fill all the points in the target, working downward from the upper left corner, then you have to try each rectangle in only one position — and you can skip rectangles that are too wide or tall to fit — and if none of your rectangles fit, and you're out of spare 1x1s, then you know it's time to backtrack. (This is essentially how Dancing Links would do it.)