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).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

   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):