javascript - 迭代地为所有相邻的相同瓷砖着色

Question

我尝试创建一个油漆桶工具。我需要找到我点击的点的所有相邻点，如果它们的颜色与原始颜色相同，则更改它们的颜色。颜色需要在所有具有相同颜色的点上传播。传播只能在 4 个方向上进行(没有对 Angular 线)。

我可以很容易地递归地做到这一点，但遗憾的是本地图太大时我得到一个错误:

Uncaught RangeError: Maximum call stack size exceeded

这是一个重现问题的基本示例，我想将其转换为迭代方式:

// Fill the map
var map = [];
for (var x = 0; x < 500; x++){
    var row = [];
    for (var y = 0; y < 500; y++){
        row.push(1);
    }
    map.push(row);
}

var paintTile = function(x, y){
    // If X or Y is out of map range
    if (x < 0 || x >= 500 || y < 0 || y >= 500){
        return
    }

    // If this tile is already painted in new color
    if (map[x][y] == 0){
        return;
    }

    // Draw tile with new color
    map[x][y] = 0;

    // Paint all adjacent tiles
    paintTile(x - 1, y);
    paintTile(x + 1, y);
    paintTile(x, y - 1);
    paintTile(x, y + 1);
};

paintTile(0, 0);

在这个例子中，所有 map 都填充了“1”(假设它是白色)，我将它们转换为“0”(黑色)，但我得到了这个堆栈大小错误。

问候

Answer 1

你是说洪水填充算法吗？

来自 http://en.wikipedia.org/wiki/Flood_fill :

Flood-fill (node, target-color, replacement-color):
 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.