洪水填充实施

Question

这是我基于堆栈的泛洪填充算法的C#实现(我基于维基百科的定义).在编码之前,我只想看到它的工作原理.它确实如此.然后,我想知道实际填充的像素数.所以在我的代码中,我将返回类型更改为int并返回"ctr"变量.但是后来ctr大约是实际填充像素数的两倍(我制作了一个单独的函数,其唯一目的是计算这些像素 - 只是为了确定).

任何人都可以启发变量"ctr"如何以及为什么增加两倍应该有的话？

*Pixel类仅用作位图像素的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像素的位图.在第一个窗格中,您有像素的编号,在右侧,您有堆栈.

从像素5开始,在像素上推动像素2,4,6和8.然后你关闭像素2并按下1和3.在下一步中你弹出1然后按2和4(再次!).然后你可以拿2,并意识到它在推动时已经获得了新的颜色.(有点晚了,但迟到总比没有好)但是:像素没有.4有两次并且记住旧颜色两次.所以你取4号像素并着色它.

一些步骤之后,您已经填充了图像,并且堆栈中仍然存在一些项目.由于旧的颜色值仍存储在这些项目中,因此会再次计算.

虽然我可能在堆栈中排序错误,但该点仍然有效.

解决您的问题:快速而肮脏(因为它仍然效率低下)

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

它仅在当前颜色错误时计算像素,而不是记住的颜色.

建议:检查像素是否需要着色,然后将它们推入堆叠.