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