Skip to content

Instantly share code, notes, and snippets.

@creationix

creationix/_README.markdown

Created November 29, 2010 19:50
Download ZIP

Revisions

  1. creationix renamed this gist Nov 29, 2010. 1 changed file with 0 additions and 0 deletions.
    0 xample.html → xample.markdown
    View file
    File renamed without changes.
  2. creationix revised this gist Nov 29, 2010. 2 changed files with 1 addition and 2 deletions.
    2 changes: 0 additions & 2 deletions rectify.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,3 @@


    function rectify(grid) {
    var rects = {};
    function findRect1(x, y) {
    1 change: 1 addition & 0 deletions xample.html
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1 @@
    <img src="http://creationix.com/rectify.png">
  3. creationix revised this gist Nov 29, 2010. 2 changed files with 44 additions and 29 deletions.
    44 changes: 44 additions & 0 deletions _README.markdown
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,44 @@
    # 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.
    29 changes: 0 additions & 29 deletions rectify.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,33 +1,4 @@
    // 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 = {};
  4. creationix created this gist Nov 29, 2010.
    127 changes: 127 additions & 0 deletions rectify.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,127 @@
    // 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);
    });
    }