洪水填充递归算法

Question

我正在尝试创建一个算法，它可以填充c#中的int数组。基本上，作为MS油漆中的填充工具，我有一个颜色，如果我在数组中选择(x，y)坐标，它就用新的颜色替换所有的邻居。

例：

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

如果我将3放入(0,0)中，数组将变成：

[3,3,3]
[3,1,3]
[1,1,3]

因此，我尝试了递归，它确实工作，但不是所有的时间。实际上，有时我有一个“堆栈溢出”错误(似乎是合适的)。这是我的代码，如果你能告诉我出了什么问题，那就太好了:)

public int[,] fill(int[,] array, int x, int y, int initialInt, int newInt)
{
    if (array[x, y] == initialInt)
    {
        array[x, y] = newInt;

        if (x < array.GetLength(0) - 1)
            array = fill(array, (x + 1), y, initialInt, newInt);
        if (x > 0)
            array = fill(array, (x - 1), y, initialInt, newInt);

        if (y < array.GetLength(1) - 1)
            array = fill(array, x, (y + 1), initialInt, newInt);
        if (y > 0)
            array = fill(array, x, (y - 1), initialInt, newInt);
    }

    return array;
}

谢谢！

Answer 1

如何使用堆栈/队列来管理剩余的工作？

public void Fill(int[,] array, int x, int y, int newInt)
{
    int initial = array[x,y];

    Queue<Tuple<int,int>> queue = new Queue<Tuple<int,int>>();
    queue.Push(new Tuple<int, int>(x, y));

    while (queue.Any())
    {
        Tuple<int, int> point = queue.Dequeue();

        if (array[point.Value1, point.Value2] != initial)
            continue;

        array[point.Value1, point.Value2] = newInt;

        EnqueueIfMatches(array, queue, point.Value1 - 1, point.Value2, initial);
        EnqueueIfMatches(array, queue, point.Value1 + 1, point.Value2, initial);
        EnqueueIfMatches(array, queue, point.Value1, point.Value2 - 1, initial);
        EnqueueIfMatches(array, queue, point.Value1, point.Value2 + 1, initial);        
    }
}

private void EnqueueIfMatches(int[,] array, Queue<Tuple<int, int>> queue, int x, int y, int initial)
{
    if (x < 0 || x >= array.GetLength(0) || y < 0 || y >= array.GetLength(1))
        return;

    if (array[x, y] == initial)
       queue.Enqueue(new Tuple<int, int>(x, y));
}

Answer 2

这是一个教科书上的例子，说明为什么使用递归并不总是合适的。递归对于遍历本质上是递归的数据结构(例如树)是很好的，但是像素数据数组不是。

我建议在代码中添加一个计数器，以打印调用fill()函数的频率。在每个函数调用中，您的机器都必须在内存中的堆栈上创建一个新的框架(这样它就知道函数结束后必须返回到哪个内存位置)。递归图像填充算法调用fill()函数的次数非常多，因此堆栈的增长非常快。它有一个有限的大小，因此它将溢出更大的图片。

解决方案是实现一个迭代填充算法，使用循环而不是递归对像素进行迭代。

请参阅递归和堆栈溢出上的维基百科，或Foley等人的“计算机图形学、原理和实践”。有关基本计算机图形算法的更详细介绍。

Answer 3

正如已经提出的那样，问题在于递归调用的数量。在32位机器上，指针有4个字节，因此，如果您有一个512*512图像，并且希望填充整个文件，那么函数指针本身就会占用堆栈上的512*512*4字节= 1MB内存。这是堆栈的默认大小。。不管函数指针是什么，您还传递了另外5个引用(array、x、y、initialInt、newInt)，所有这些引用都是作为临时对象与每个调用一起复制的，它们都在堆栈上直到函数调用终止。在相同大小的映像上，它们是另一个512*512*5*4字节= 5MB内存。

要解决您的问题，您可以修改 (与上面的链接相同)堆栈的大小。

另外，为了节省一些堆栈空间，您可以考虑将参数包装在单个对象中，在这种情况下，每次调用只有4位临时内存，而不是20位。

不过，正如前面所指出的，最好的解决方案是迭代重写算法。