洪水填充算法导致堆栈溢出

Question

所以我有 WPF c# 应用程序 canvas 可以绘制（绘图正在改变矩形的填充，例如有 128x128 的矩形）泛洪填充算法，如果有太多的填充会导致 Whosebug矩形比某个值（例如 128x128）。我想升级此脚本以在任何大小的绘制区域中工作。我读了一些这样的问题，但我仍然不知道如何修复它，我需要这个特定脚本的帮助，因为这里的绘图与普通绘图有点不同（这是 Pixel Art creator）。所以这是我的算法。

public static void FloodFIll(int x, int y, Brush color, Brush colorToReplace)
        {
            if (selectedTool == AvailableTools.FillBucket)
            {
                if (x < 1 || x > PixiManager.drawAreaSize) return;
                if (y < 1 || y > PixiManager.drawAreaSize) return;

                if (PixiManager.FieldCords(x, y).Fill != color)
                {
                    if (PixiManager.FieldCords(x, y).Fill == colorToReplace)
                    {
                        PixiManager.FieldCords(x, y).Fill = color;
                        FloodFIll(x, y - 1, color, colorToReplace);
                        FloodFIll(x + 1, y, color, colorToReplace);
                        FloodFIll(x, y + 1, color, colorToReplace);
                        FloodFIll(x - 1, y, color, colorToReplace);
                    }
                }
            }
        }

Answer 1

这是您的算法的 none 递归版本。

public static void FloodFIll(int x, int y, Brush color, Brush colorToReplace)
{   
    if (selectedTool != AvailableTools.FillBucket)
    {
        return;
    }

    var stack = new Stack<Tuple<int, int>>();
    stack.Push(Tuple.Create(x, y));

    while(stack.Count > 0) 
    {
        var point = stack.Pop();
        if (point.Item1 < 1 || point.Item1 > PixiManager.drawAreaSize) continue;
        if (point.Item2 < 1 || point.Item2 > PixiManager.drawAreaSize) continue;
        if (PixiManager.FieldCords(point.Item1, point.Item2).Fill == color) continue;

        if (PixiManager.FieldCords(point.Item1, point.Item2).Fill == colorToReplace)
        {
            PixiManager.FieldCords(point.Item1, point.Item2).Fill = color;
            stack.Push(Tuple.Create(point.Item1, point.Item2 - 1));
            stack.Push(Tuple.Create(point.Item1 + 1, point.Item2));
            stack.Push(Tuple.Create(point.Item1, point.Item2 + 1));
            stack.Push(Tuple.Create(point.Item1 - 1, point.Item2));
        }
    }
}

尽管您可能会创建自己的 class 而不是使用 Tuple。

Answer 2

我建议不要从每个像素分支出来，而是在分支之前一次填充一整条扫描线。使用这样的逻辑：

重复向左移动 1 个像素，直到找到不同颜色的像素。在颜色与原始像素颜色匹配的最后一个像素处停止。
用新颜色填充此像素。
如果上面的像素与该像素的颜色相同，并且尚未设置标志 A，则将步骤 1 中的相同工作在上面的坐标处排队，并设置本地标志 A。
如果下面的像素与该像素的颜色相同，并且尚未设置标志 B，则在下面的坐标处排队相同的工作，并设置局部标志 B。
向右移动。
如果这个像素点颜色不一样，就结束函数。
如果上面的像素不是同一个颜色，清除标志A。
如果下面的像素不是同一个颜色，清除标志B。
从第 2 步开始重复。

洪水填充算法导致堆栈溢出

Flood fill alghoritm causes StackOverflow

c#

wpf

flood-fill