Code for rectangle packing using a free constraint solver

I just wanted to share a piece of code that automatically finds a placement for smaller images into a larger one (for optimization).



	public static boolean autoPlaceImages(int resultWidth, int resultHeight,
			int[] rectWidths, int[] rectHeights, int[] xOffsets, int[] yOffsets) {

		// Just check if it is physically possible first...
		int area = 0;
		for (int i = 0; i < rectWidths.length; i++) {
			area += rectWidths[i] * rectHeights[i];
		}
		if (area > resultWidth * resultHeight) {
			return false;
		}

		Store store = new Store();

		FDV[] xOffsetVars = new FDV[rectWidths.length];
		FDV[] yOffsetVars = new FDV[rectWidths.length];

		ArrayList<Variable> vars = new ArrayList<Variable>();

		FDV[][] rects = new FDV[rectWidths.length][4];

		FDV maxWidthVar = new FDV(store, "mw", resultWidth, resultWidth);
		FDV maxHeightVar = new FDV(store, "mh", resultHeight, resultHeight);

		for (int i = 0; i < rectWidths.length; i++) {
			String id = "rect_" + i;
			FDV x = new FDV(store, id + "_x", 0, resultWidth - 1);
			FDV y = new FDV(store, id + "_y", 0, resultHeight - 1);
			xOffsetVars[i] = x;
			yOffsetVars[i] = y;
			int width = rectWidths[i];
			int height = rectHeights[i];
			FDV widthVar = new FDV(store, id + "_w", width, width);
			FDV heightVar = new FDV(store, id + "_h", height, height);
			store.impose(new XplusYlteqZ(x, widthVar, maxWidthVar));
			store.impose(new XplusYlteqZ(y, heightVar, maxHeightVar));
			vars.add(x);
			vars.add(y);
			// vars.add(widthVar);
			// vars.add(heightVar);
			rects[i] = new FDV[] { x, y, widthVar, heightVar };
		}

		store.impose(new Diff2(store, rects));

		SelectChoicePoint select = new SimpleSelect(vars
				.toArray(new Variable[1]), null, new IndomainMin());

		DepthFirstSearch search = new DepthFirstSearch();
		search.setPrintInfo(false);
		boolean result = search.labeling(store, select);

		for (int i = 0; i < xOffsetVars.length; i++) {
			xOffsets[i] = xOffsetVars[i].value();
			yOffsets[i] = yOffsetVars[i].value();
		}

		return result;

	}



It uses the free JaCoP constraint solver http://www.jacop.eu/ which has to be downloaded to get this to work.

EDIT: I integrated it into my node system tool and here is a result with 30 images (using a resolution of 32 pixels for each grid cell in the problem specification, which decreases the problem difficulty):

http://www.springworldchallenge.com/images/rectangle_packing.png

I was doing some research into this the other day, and found that you could use TreeSet to accomplish the same results. Sorry, I don’t have more information or references.

But what I am mostly interested in is what is called Circle Packing.

I am now using the code provided in the following topic:

http://www.java-gaming.org/index.php/topic,17919.0.html

It is much faster!