CODEWITHSUNDEEP
javascriptarraysalgorithmmultidimensional-arrayflood-fill
Joel
Joel

Reputation: 387

Multidimensional array fill

I'm trying to fill an area in a multidimensional array and not sure on the approach.

For example I have the following array:

var map = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 2, 2, 2, 2, 2, 2, 0, 0],
    [0, 2, 0, 0, 0, 0, 2, 0, 0],
    [0, 2, 0, 2, 0, 0, 2, 0, 0],
    [0, 2, 0, 0, 2, 0, 2, 0, 0],
    [0, 0, 2, 0, 0, 0, 2, 0, 0],
    [0, 0, 0, 2, 2, 2, 2, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
];

And then I am trying to get the number from X and Y position and fill all those numbers (which is 0) with a number given such as 1, which will result in the following array:

var map = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 2, 2, 2, 2, 2, 2, 0, 0],
    [0, 2, 1, 1, 1, 1, 2, 0, 0],
    [0, 2, 1, 2, 1, 1, 2, 0, 0],
    [0, 2, 1, 1, 2, 1, 2, 0, 0],
    [0, 0, 2, 1, 1, 1, 2, 0, 0],
    [0, 0, 0, 2, 2, 2, 2, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
];

Basically just replacing all numbers next to each other (0) with (1) within that area.

What is the correct way to do this with JavaScript?

Upvotes: 0

Views: 1352

Answers (2)

jfriend00
jfriend00

Reputation: 707536

Assuming you're given a starting position and you want to then fill all neighboring values up/down, left/right that contain the same value, you can do something like this:

var map = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 2, 2, 2, 2, 2, 2, 0, 0],
    [0, 2, 0, 0, 0, 0, 2, 0, 0],
    [0, 2, 0, 2, 0, 0, 2, 0, 0],
    [0, 2, 0, 0, 2, 0, 2, 0, 0],
    [0, 0, 2, 0, 0, 0, 2, 0, 0],
    [0, 0, 0, 2, 2, 2, 2, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
];

function fill(data, x, y, newValue) {
    // get target value
    var target = data[x][y];

    function flow(x,y) {
        // bounds check what we were passed
        if (x >= 0 && x < data.length && y >= 0 && y < data[x].length) {
            if (data[x][y] === target) {
                data[x][y] = newValue;
                flow(x-1, y);    // check up
                flow(x+1, y);    // check down
                flow(x, y-1);    // check left
                flow(x, y+1);    // check right
            }
        }
    }

    flow(x,y);
}

fill(map, 2, 2, 1);

Working demo: http://jsfiddle.net/jfriend00/C83AT/

Here's a version that doesn't use recursion and appears to work with large data sets. Your large test data set wasn't a very interesting test pattern so I wouldn't say this is tested conclusively, but it seems to work on both the small and large data set:

Large data example: http://jsfiddle.net/jfriend00/8mrhN/

Small data example: http://jsfiddle.net/jfriend00/BFTub/ (easier to see the result)

function fill(data, x, y, newValue) {
    // get target value
    var target = data[x][y];
    // maintain list of cells to process
    // put the starting cell in the queue
    var queue = [{x:x, y:y}], item;

    while (queue.length) {
        item = queue.shift();
        x = item.x;
        y = item.y;
        if (data[x][y] === target) {
            data[x][y] = newValue;
            // up
            if (x > 0) {
                queue.push({x:x-1, y:y})
            }
            // down
            if (x + 1 < data.length) {
                queue.push({x:x+1, y:y})
            }
            // left
            if (y > 0) {
                queue.push({x:x, y:y-1});
            }
            // right
            if (y + 1 < data[x].length) {
                queue.push({x:x, y:y+1});
            }
        }
    }
}

This could be optimized further for performance by testing the value before putting it in the queue and by following a given direction until you find a non-matching value, if required.

Upvotes: 4

Xotic750
Xotic750

Reputation: 23482

This is an alternative implementation (queue-based) roughly translated, no optimisations performed. There are also others.

Javascript

var map = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 2, 2, 2, 2, 2, 2, 0, 0],
    [0, 2, 0, 0, 0, 0, 2, 0, 0],
    [0, 2, 0, 2, 0, 0, 2, 0, 0],
    [0, 2, 0, 0, 2, 0, 2, 0, 0],
    [0, 0, 2, 0, 0, 0, 2, 0, 0],
    [0, 0, 0, 2, 2, 2, 2, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
];

/*
 1. Set Q to the empty queue.
 2. If the color of node is not equal to target-color, return.
 3. Add node to Q.
 4. For each element N of Q:
 5.     If the color of N is equal to target-color:
 6.         Set w and e equal to N.
 7.         Move w to the west until the color of the node to the west of w no longer matches target-color.
 8.         Move e to the east until the color of the node to the east of e no longer matches target-color.
 9.         For each node n between w and e:
10.             Set the color of n to replacement-color.
11.             If the color of the node to the north of n is target-color, add that node to Q.
12.             If the color of the node to the south of n is target-color, add that node to Q.
13. Continue looping until Q is exhausted.
14. Return.
*/
function floodFill(data, node, targetValue, replacementValue) {
    var Q;

    if (data[node[0]][node[1]] === targetValue) {
        Q = [node];
        while (Q.length) {
            var N = Q.shift(),
                value,
                index,
                n,
                e,
                s,
                w;

            if (data.hasOwnProperty([N[0]]) && data[N[0]][N[1]] === targetValue) {
                w = e = N[0];
                do {
                    w -= 1;
                } while (data.hasOwnProperty(w) && data[w][N[1]] === targetValue);

                do {
                    e += 1;
                } while (data.hasOwnProperty(e) && data[e][N[1]] === targetValue);

                n = N[1] - 1;
                s = N[1] + 1;
                for (index = w + 1; index < e; index += 1) {
                    data[index][N[1]] = replacementValue;
                    if (data[index].hasOwnProperty(n) && data[index][n] === targetValue) {
                        Q.push([index, n]);
                    }

                    if (data[index].hasOwnProperty(s) && data[index][s] === targetValue) {
                        Q.push([index, s]);
                    }
                }
            }
        }
    }
}

floodFill(map, [2, 2], 0, 1);
map.forEach(function (m) {
    console.log(JSON.stringify(m));
});

Output

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

On jsFiddle

Upvotes: 0

Related Questions