泛洪填充递归算法

Question

我将尝试制作一个在 C# 中可以填充 int 数组的算法。基本上，就像 MS Paint 中的填充工具一样，我有一种颜色，如果我选择数组中的 (x,y) 坐标，则会用新的颜色替换所有相邻的初始颜色相同的元素。

例如：

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

如果我在(0,0)位置放入数字3，数组就会变成：

[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;
}

感谢您！

- Pimeko

---

是的...这是大量递归调用。最好使用类似C#这样不保证尾调用优化的过程式语言来完成（即使您当前的代码也无法从中受益）。 - Ed S.

好 --> "Stack Overflow" - Justas

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));
}

- Scott Wegner

---

谢谢你提供这个算法和快速回答，但是它并不起作用。事实上，我遇到了一个"内存不足"的异常。有什么想法吗？ - Pimeko

Answer 2

这是一个很好的例子，说明为什么不总是适合使用递归。递归很适合遍历本质上是递归的数据结构（例如树），但像你的像素数据数组这样的数据结构则不适合。

我建议在你的代码中添加一个计数器，以打印fill()函数被调用的次数。在每个函数调用时，您的计算机都必须在内存中创建一个新的堆栈帧（以便在函数结束后知道要返回到哪个内存位置）。递归图像填充算法会大量调用fill()函数，因此堆栈将迅速增长。它有一个有限的大小，因此对于较大的图片，它将溢出。

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

请参阅维基百科关于递归和堆栈溢出，或Foley等人的《计算机图形学原理与实践》以获取更详细的基本计算机图形学算法介绍。

- Leon Weber

Answer 3

正如已经建议的那样，问题出在递归调用的次数上。在32位机器上，指针占据4个字节，所以如果你有一个512*512像素的图像，并且想要填满整个图像，函数指针本身就会占据512*512*4个字节 = 1MB 的内存空间。 而这就是栈的默认大小。除了函数指针之外，你还有另外5个引用（array、x、y、initialInt、newInt），每次调用都会被复制为临时对象，并在函数调用结束前一直存在于栈中。在同样大小的图像上，这些引用会占据另外512*512*5*4个字节 = 5MB 的内存空间。

为了解决你的问题，你可以修改（与上述链接相同）栈的大小。

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

但是，正如也指出的那样，最好的解决方案是迭代地重写您的算法。

- Alexandru Barbarosie

---

请注意，尽管增加堆栈大小可能是特定情况下的解决方法，但当提供更大的图像时，问题将再次出现。这仍然是一种极其低效的算法，真正的解决方案是修复算法本身。 - Leon Weber