洪水填埋实施

Question

这是我基于堆栈的洪水填充算法的C#实现(我基于维基百科的定义)。早些时候，在编写代码时，我只想看到它起作用。它确实做到了。然后，我想知道填充的像素数。因此，在我的代码中，我将返回类型更改为int，并返回"ctr"变量。但是，ctr的实际填充像素数大约是实际数量的两倍(我做了一个单独的函数，唯一的目的是计数这些像素--只是为了确切地知道)。

有人能说明变量"ctr"是如何增加的，以及为什么它应该增加两倍吗？

*像素类仅用作位图中像素的x、y和颜色值的容器。

public Bitmap floodfill(Bitmap image, int x, int y, Color newColor)
{
    Bitmap result = new Bitmap(image.Width, image.Height);
    Stack<Pixel> pixels = new Stack<Pixel>();
    Color oldColor = image.GetPixel(x, y);
    int ctr = 0;

    pixels.Push(new Pixel(x, y, oldColor));

    while (pixels.Count > 0)
    {
        Pixel popped = pixels.Pop();

        if (popped.color == oldColor)
        {
            ctr++;
            result.SetPixel(popped.x, popped.y, newColor);

            pixels.Push(new Pixel(popped.x - 1, popped.y, image.GetPixel(x - 1, y));
            pixels.Push(new Pixel(popped.x + 1, popped.y, image.GetPixel(x + 1, y));
            pixels.Push(new Pixel(popped.x, popped.y - 1, image.GetPixel(x, y - 1));
            pixels.Push(new Pixel(popped.x, popped.y + 1, image.GetPixel(x, y + 1));
        }
    }

    return result;
}

Answer 1

您可以在这里检查像素的颜色：

if (popped.color == oldColor)

但是popped.color可能已经过时了(而且在50%的病例中更是如此)。因为当您在堆栈中插入像素时不检查重复项，所以就会有重复项。一旦弹出这些副本，颜色属性就会在很久以前保存下来。

也许画一张图会更清晰些：

​

​

举个例子，我拿了一个9像素的位图。在第一个窗格中有像素编号，右侧有堆栈。

从像素NO5开始，然后在堆栈上推送像素2、4、6和8。然后去掉像素2，然后推送1和3。在下一个步骤中，弹出1和推送2和4(再次！)然后，你可以采取2，并意识到它已经得到了新的颜色时，它被推送。(有点晚了，但总比从来没有晚)然而:像素4号有两次，并已记住旧的颜色两次。所以你取象素4，然后给它上颜色。

一些步骤之后，您已经填充了图像，仍然有一些项在您的堆栈上。因为旧的颜色值仍然存储在这些项目中，所以它们会再次被计数。

虽然我在堆栈中可能有错误的排序，但这个点仍然有效。

解决问题的方法:快速而肮脏(因为它仍然是低效的)

if (image.GetPixel(popped.x, popped.y) == oldColor)

它只在当前颜色错误时计算像素，而不是记忆中的颜色。

推荐:检查像素是否需要着色，然后再将它们推到堆栈上。

Answer 2

如果像素只保留传递给构造函数的颜色，则在像素填充后不会更新颜色，因此每个像素可以增加一次以上的ctr。

如果您更改Pixel以获取指向其构造函数中的图像的指针，则可以重新读取颜色(即使颜色成为读取当前颜色的get属性)，或者跟踪已填充的坐标，不要再次推送这些颜色。

编辑

如果从接受的答案中看不出来，GetPixel会返回一个颜色--一个值类型。把它想象成一个整数，在那个时候编码像素的RGB值。

如果您想要快速执行填充，请查找一个Graphics.FloodFill示例。

如果您的目标是学习，我建议将您的图像数据复制到一个数组中进行处理，然后再返回--大多数经典的图像算法使用GetPixel()并不有趣。