CODEWITHSUNDEEP
c#wpfflood-fill
flabbet
flabbet

Reputation: 337

Flood fill alghoritm causes StackOverflow

So I have WPF c# app that have canvas to draw in (drawing is changing fill of Rectangles, for example there is 128x128 rectangles) flood fill alghoritm, it causes StackOverflow if there is too big amount of rectangles than some value (example. 128x128). And I want to upgrade this script to work in any size of draw area. I read some of questions like this, but I still don't know how to repair it and I need help to this specific script cause drawing here is a bit different than normal drawing (this is Pixel Art creator). So this is my alghoritm.

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

Upvotes: 1

Views: 424

Answers (2)

BlueMonkMN
BlueMonkMN

Reputation: 25601

I would recommend not branching out from every pixel, but rather fill perhaps a whole scan line at a time before branching out. Use logic like this:

  1. Repeatedly move left 1 pixel until a pixel of a different color is found. Stop at the last pixel whose color matches the original pixel color.
  2. Fill this pixel with the new color.
  3. If the pixel above is the same color as this pixel was, and flag A is not already set, enqueue the same work from step 1 at the above coordinate, and set local flag A.
  4. If the pixel below is the same color as this pixel was, and flag B is not already set, enqueue the same work at the below coordinate, and set local flag B.
  5. Move to the right.
  6. If this pixel is not the same color, end the function here.
  7. If the pixel above is not the same color, clear flag A.
  8. If the pixel below is not the same color, clear flag B.
  9. Repeat from step 2.

Upvotes: 2

juharr
juharr

Reputation: 32296

Here's a none recursive version of your algorithm.

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

Though you might what to create your own class instead of using Tuple.

Upvotes: 3

Related Questions