Flood fill algorithm is causing OutOfMemory Exception

Question

Well, I'm getting the outline (path) of a building. And there is a problem. When I iterate it's pixels I check if the current pixel is white to start detecting it's walls.

What happens with this? When the detection is finished it starts again and again, because the next iterated pixel is also white. That's why I need to use a flood fill algorithm (to flag that the current build is completed).

Well, I have already implemented it, but I have problems.

    public static void FloodFill(ref Color[] source, Point pt, int width, int height, Color targetColor, Color replacementColor)
    {
        Stack<Point> pixels = new Stack<Point>();

        targetColor = source[P(pt.x, pt.y, width, height)];
        pixels.Push(pt);

        while (pixels.Count > 0)
        {
            Point a = pixels.Pop();

            if (source[P(a.x, a.y, width, height)] == targetColor)
            {
                source[P(a.x, a.y, width, height)] = replacementColor;

                if (a.x > 0)
                    pixels.Push(new Point(a.x - 1, a.y));

                if (a.x < width)
                    pixels.Push(new Point(a.x + 1, a.y));

                if (a.y > 0)
                    pixels.Push(new Point(a.x, a.y - 1));

                if (a.y < height)
                    pixels.Push(new Point(a.x, a.y + 1));
            }
        }
    }

Extracted from: https://simpledevcode.wordpress.com/2015/12/29/flood-fill-algorithm-using-c-net/

The problem here is that by some reason, ref keyword isn't taking effect.

My implementation:

    private IEnumerator MainGenerationDebug(Color[] source, Color32[] target, int width, int height)
    {
        // (1)
        for (int i = 0; i < source.Length; Interlocked.Increment(ref i))
        {
            // (2)
            Color c = source[i];

            // (3)
            int x = i % width,
                y = i / width;

            // (4) & (5)
            yield return IntMapIteration(source, target, width, c, i, exceptions, (s, t) =>
            {
                source = s;
                target = t;
            });

            // (6)
            if (c == Color.white)
            {
                F.FloodFill(ref source, new Point(x, y), width, height, Color.white, Color.red);
            }
        }
    }

The process is the following:

1. I start looping all pixels, because I'm in another thread I use Interlocked.Increment.
2. I get the current color
3. I get the current x, y (2D) from the index (1D)
4. Due to I'm in a Coroutine (I'm debugging so I need to see what's happening) I use yielding
5. When the IEnumerator finishes I call an Action. (I use IEnumerators because I'm calling an Coroutine in Unity3D)
6. After everything finishes, if the current pixel is white, I start flood-filling the array.

I think everything is correct. By maybe I'm missing something.

What could you say about this?

Answer 1

I created an own implementation to show what's happening and why it's better to use HashSet.

Why used HashSet? HashSet.Contains is quicklier.

This is the actual implementation:

using System.Collections.Generic;
using System.Linq;

public static class F
{
    /// <summary>
           /// Floods the fill.
           /// </summary>
           /// <typeparam name="T"></typeparam>
           /// <param name="source">The source.</param>
           /// <param name="x">The x.</param>
           /// <param name="y">The y.</param>
           /// <param name="width">The width.</param>
           /// <param name="height">The height.</param>
           /// <param name="target">The target to replace.</param>
           /// <param name="replacement">The replacement.</param>
    public static void FloodFill<T>(this T[] source, int x, int y, int width, int height, T target, T replacement)
    {
        int i = 0;

        FloodFill(source, x, y, width, height, target, replacement, out i);
    }

    /// <summary>
           /// Floods the array following Flood Fill algorithm
           /// </summary>
           /// <typeparam name="T"></typeparam>
           /// <param name="source">The source.</param>
           /// <param name="x">The x.</param>
           /// <param name="y">The y.</param>
           /// <param name="width">The width.</param>
           /// <param name="height">The height.</param>
           /// <param name="target">The target to replace.</param>
           /// <param name="replacement">The replacement.</param>
           /// <param name="i">The iterations made (if you want to debug).</param>
    public static void FloodFill<T>(this T[] source, int x, int y, int width, int height, T target, T replacement, out int i)
    {
        i = 0;

        // Queue of pixels to process. :silbar:
        HashSet<int> queue = new HashSet<int>();

        queue.Add(Pn(x, y, width));

        while (queue.Count > 0)
        {
            int _i = queue.First(),
              _x = _i % width,
              _y = _i / width;

            queue.Remove(_i);

            if (source[_i].Equals(target))
                source[_i] = replacement;

            for (int offsetX = -1; offsetX < 2; offsetX++)
                for (int offsetY = -1; offsetY < 2; offsetY++)
                {
                    // do not check origin or diagonal neighbours
                    if (offsetX == 0 && offsetY == 0 || offsetX == offsetY || offsetX == -offsetY || -offsetX == offsetY)
                        continue;

                    int targetIndex = Pn(_x + offsetX, _y + offsetY, width);
                    int _tx = targetIndex % width,
                      _ty = targetIndex / width;

                    // skip out of bounds point
                    if (_tx < 0 || _ty < 0 || _tx >= width || _ty >= height)
                        continue;

                    if (!queue.Contains(targetIndex) && source[targetIndex].Equals(target))
                    {
                        queue.Add(targetIndex);
                        ++i;
                    }
                }
        }
    }

    public static int Pn(int x, int y, int w)
    {
        return x + (y * w);
    }
}

You can see it here working: https://dotnetfiddle.net/ZacRiB (using Stack was O(4n) (I figured out how to solve this problem, but I dont find the actual code) and HashSet is O(n - 1)).