Rectify Challenge

_README.markdown

Rectify

Takes a grid and returns an optimal set of rectangles that fills that grid

For example, the following grid:

[[1,1,0,1,1],
 [1,1,1,1,1],
 [0,1,1,1,0]]

Should result in three rectangles (order doesn't matter)

[{x:0,y:0,w:2,h:2},
 {x:3,y:0,w:2,h:2},
 {x:1,y:1,w:3,h:2}]

Note that the rectangles need to overlap and not simply touch since they will be used to draw a shape with rounded and slightly inset borders.

[[1,1,0],
 [1,1,1],
 [0,0,1]]

Even though the following technically fills all the space:

[{x:0,y:0,w:2,h:2},
 {x:2,y:1,w:1,h:2}]

It will appear as two distinct rectangles because they don't overlap.

The following is correct:

[{x:0,y:0,w:2,h:2},
 {x:2,y:1,w:1,h:2},
 {x:0,y:2,w:3,h:1}]

The Challenge

The following implementation works, but the result it not optimal, it often results in too many rectangles. Also there are some fairly expensive parts to the algorithm and it's a bit longer than I would like.

Clone this gist and make a better implementation and link to your submission as a comment here when done.

rectify.js

function rectify(grid) {
  var rects = {};
  function findRect1(x, y) {
    var sx = x, sy = y, ex = x, ey = y;
    while (grid[sy - 1] && grid[sy - 1][x]) {
      sy--;
    }
    while (grid[ey + 1] && grid[ey + 1][x]) {
      ey++;
    }
    var good = true;
    var ty;
    while (good) {
      for (ty = sy; ty < ey + 1; ty++) {
        if (!grid[ty][sx - 1]) {
          good = false;
          break;
        }
      }
      if (good) {
        sx--;
      }
    }
    good = true;
    while (good) {
      for (ty = sy; ty < ey + 1; ty++) {
        if (!grid[ty][ex + 1]) {
          good = false;
          break;
        }
      }
      if (good) {
        ex++;
      }
    }
    return {
      x: sx,
      y: sy,
      w: ex - sx + 1,
      h: ey - sy + 1
    };
  }
  function findRect2(x, y) {
    var sx = x, sy = y, ex = x, ey = y;
    while (grid[y][sx - 1]) {
      sx--;
    }
    while (grid[y][ex + 1]) {
      ex++;
    }
    var good = true;
    var tx;
    while (good) {
      for (tx = sx; tx < ex + 1; tx++) {
        if (!(grid[sy - 1] && grid[sy - 1][tx])) {
          good = false;
          break;
        }
      }
      if (good) {
        sy--;
      }
    }
    good = true;
    while (good) {
      for (tx = sx; tx < ex + 1; tx++) {
        if (!(grid[ey + 1] && grid[ey + 1][tx])) {
          good = false;
          break;
        }
      }
      if (good) {
        ey++;
      }
    }
    return {
      x: sx,
      y: sy,
      w: ex - sx + 1,
      h: ey - sy + 1
    };
  }
  
  for (var y = 0, l1 = grid.length; y < l1; y++) {
    for (var x = 0, l2 = grid[y].length; x < l2; x++) {
      if (grid[y][x]) {
        rects[JSON.stringify(findRect1(x, y))] = true;
        rects[JSON.stringify(findRect2(x, y))] = true;
      }
    }
  }
  // TODO: Remove redundant rectangles
  return Object.keys(rects).map(function (json) {
    return JSON.parse(json);
  });
}

xample.markdown