Optimizing Floodfill algorithm implementation as much as possible

Question

Actually my implementation is not working very well for big areas (I don't know why) I already created a question on Stackoverflow. But I figured out how to do it to work with an O(n) implementation (you can see what I mean here (see the fiddle I attached)).

But for some reason as I said it is not working very well on big areas.

/// <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.</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)
    where T : IEquatable<T>
{
    int i;

    source.FloodFill(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 i.</param>
// This was generic
public static void FloodFill<T>(this T[] source, int x, int y, int width, int height, T target, T replacement, out int i)
    where T : IEquatable<T>
{
    i = 0;
    HashSet<int> queue = new HashSet<int>();

    queue.Add(P(x, y, width, height));

    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); // This is already inverted that's why we don't use F.P(...)
                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);

                    if (Monitor.IsEntered(i))
                        ++i;
                    else
                        Interlocked.Increment(ref i);
                }
            }

        if (i > 100000)
            break;
    }
}

My main concerns are the following:

• I don't know if there is a better way to debug how many iterations has the algorithm done (and if I'm getting them correctly).
• I don't like to use Monitor.IsEntered (I'm not sure if this is needed).
• I would like to speed-up it, but I don't know how (I think this is slow) (you can compare it with ms-paint to see differences, I know it's written on C++, but... I would like to get a significant perfomance).
• Also, I don't know if there is a better way to do it (to avoid unnecesary memory consumption).

Answer 1

Monitor.IsEntered

This call basically makes no sense. Monitor.IsEntered is used for coordination/mutual exclusion between threads. There are no threads here, and even if there were, there is no reason to lock on i: it is a counter. It isn't even a meaningful target for Monitor.IsEntered because it isn't an object.

There is no apparently threading going on here, so you can confidently remove all the locking stuff (including Interlocked.Increment). This may noticeably improve performance, since Monitor.IsEntered is non-trivial, and the call will incur boxing (so at worse this will improve the memory characteristics of your code).

If, for some reason, you are reading i from a different thread while the flood-fill is running, then you might want to use Interlocked methods to provide some notion of up-to-dateness.... but unless you are using that low-latency synchronisation (in which case it is a bad choice for doing so) you won't in practice need any manual memory barriers here. If it is not the case that you want to access i before this has finished then keep track of it as a 'normal' variable, and then set it as out at the end (if it is needed at all). out parameters can be abused, and may interfere with the compilers ability to perform optimisations.

100000

What is this?

if (i > 100000)
    break;

This is a magic number threshold. This says "if I happen to look at some mysterious number of entries, then I will give up and provide a mangled result". This is terrible, especially so because it isn't documented. If you want a cut-out, then have the threshold passed as a parameter, and document it in the inline documentation. It's good that you have inline documentation, but it isn't very helpful at the moment, failing to explain what any of the parameters are beyond suggesting that target will be 'replaced' (what does that mean?).

Furthermore, if it does cut out, then the consumer should be informed. You could throw a FloodfillCutoffException, or return a bool indicating that it did not complete, or something else.

HashSet/Stack

You should probably be using a Stack. HashSet.Contain is efficient (for what it does), but you don't need it. (This is assuming that target.Equals(replacement) is always false, but if that isn't the case then your code is broken anyway, because it doesn't keep track of pixels it has dequeued)

Excepting the first pixel, if you set source[targetIndex] = replacement when you queue it then you don't need to check if it is already in the HashSet: you only need to check that source[targetIndex].Equals(target), which you have to do anyway. The probably with your non-HashSet code wasn't the Stack, it was how you were using it.

With a stack, the code will look mostly the same, only you'll be Poping from the stack (instead of using First() and Remove(T). It should be much faster, because it doesn't lean on HashSet, which while being 'kind of O(1)' isn't going to outperform a single array lookup which probably needs to be done anyway.

Indexing

I'm guessing Pn is static, and looks something like this:

static int Pn(int x, int y, int width => x + y * width;

IEquatable<T>

It's good that you are using this.

Naming

Most of the names are cryptic. This is not ideal. It isn't clear why you use P rather than Pn. i and _i are completely unrelated (and both poor names). target and targetIndex are mostly unrelated.

Code

Here is a (completely untested) rework of your code I threw together in a hurry incorporating some of the points above, with some added comments.

public static void FloodFill<T>(this T[] source, int x, int y, int width, int height, T target, T replacement, int cutoff, out int explored)
    where T : IEquatable<T>
{
    // code can't handle this, so throw
    if (target.Equals(replacement))
    {
        throw new ArgumentException("Target and Replacement cannot equate");
    }

    // do start manually, and exit quickly if appropriate
    int start = P(x, y, width, height);
    if (!source[start].Equals(target))
    {
        explored = 0;
        return;
    }

    // stack is not a great name, but I'm in a hurry right now...
    Stack<int> stack = new Stack<int>();
    stack.Push(start);

    int count = 1;
    while (queue.Count > 0)
    {
        int _i = stack.Pop(),
            _x = _i % width,
            _y = _i / width;

        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); // This is already inverted that's why we don't use F.P(...)
                int _tx = targetIndex % width,
                    _ty = targetIndex / width;

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

                // if pixel matched target, reset it and queue
                if (source[targetIndex].Equals(target))
                {
                    source[targetIndex] = replacement;

                    stack.Push(targetIndex);
                    count++;
                }
            }

        if (i > cutoff)
            throw new Exception("FloodFill passed cutoff");
    }

    // report the number of cells explored
    explored = count;
}

Answer 2

All in all you have way too many variables, and the names aren't to much help when trying to follow your algorithm.

VisualMelon has commented some details so I won't go further into that.

---

When determine the area for a floodfill all you need are:

1) The source as an one-dimensional array (it would of course be easier with a two-dimensional matrix)

2) The width of each row (count of columns)

3) The starting point inside the area to flood

4) The target value

5) The replacement value

So the signature of the method could be something like this:

public static void FloodFill<T>(this T[] source, int width, int startX, int startY, T target, T replacement) where T: IEquatable<T>

The height (number of rows) is redundant and can easily be calculated.

You should maybe make a check of the dimension:

if (source.Length % width != 0) throw new Exception("source has wrong size");

---

Finding the neighbors is as simple as:

North: neighbor = current - width;
South: neighbor = current + width;
East: neighbor = current + 1; // See comment below
North-East: neighbor = East - width;
South-East: neighbor = East + width;
West: neighbor = current - 1; // See comment below
North-West: neighbor = West - width;
South-West: neighbor = West + width;

---

A solution could then be as follow:

public static void FloodFill<T>(this T[] source, int width, int startX, int startY, T target, T replacement) where T: IEquatable<T>
{
  if (source == null || source.Length == 0 || target.Equals(replacement))
    return;

  int length = source.Length;
  Queue<int> queue = new Queue<int>();

  int current = startY * width + startX;

  if (!source[current].Equals(target))
    return;

  // If no target value was found the return 
  if (current >= length) return;

  // A target value was found at index current so enqueue that
  queue.Enqueue(current);

  // Local function that enqueue an index if it is within 
  // the boundaries of the source and the value equals the target value.
  void Enqueue(int index)
  {
    if (index >= 0 && index < length && source[index].Equals(target))
    {
      source[index] = replacement;
      queue.Enqueue(index);
    }
  }

  while (queue.Count > 0)
  {
    current = queue.Dequeue();

    // North
    int neighbor = current - width;
    Enqueue(neighbor);

    // South
    neighbor = current + width;
    Enqueue(neighbor);

    // East: The current index as a column index must be lesser 
    //       than the width - 1 or else going east will 
    //       roundtrip to the next row
    if (current % width < width - 1)
    {
      neighbor = current + 1;
      Enqueue(neighbor);

      // North-East and South-East are easily found in the same way as North and South
      // NE
      Enqueue(neighbor - width);
      // SE
      Enqueue(neighbor + width);
    }

    // West: This is analogue to East: current as a column index must be greater than 0
    //       or else going west will roundtrip to the previous row.
    if (current % width > 0)
    {
      neighbor = current - 1;
      Enqueue(neighbor);

      // Completely analogue to NE an SE
      // NW
      Enqueue(neighbor - width);
      // SW
      Enqueue(neighbor + width);
    }
  }
}