Rectify Challenge

rectify.js

// Takes a grid and returns an optimal set of rectangles that fills that grid
// For example:
// [[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 1's:
// [{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.

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);
  });
}