我尝试创建一个油漆桶工具。我需要找到单击的点的所有相邻点,如果它们的颜色与原始颜色相同,则更改其颜色。颜色需要在具有相同颜色的所有点上传播。只能在4个方向上传播(无对角线)。
我可以轻松地递归执行此操作,但是可悲的是,当地图太大时,我会收到一个错误消息:
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);
在此示例中,所有地图都填充为“ 1”(假设它是白色),然后将它们转换为“ 0”(黑色),但出现此stack size错误。
stack size
问候
您是指洪水填充算法吗?
从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.