title: Different Methods of Performing FloodFill
body: <p>OK everyone I have several different methods of performing a FloodFill.  All of them cause problems.  I will list the 3 methods and explain what happens with each one.  If anyone could give me some pointers that would be great.  I have seen some similar posts but none of them have been for C#, java, or VB.net (the only languages I know).</p>
  
  <p>The givens for this are that I have a class called PixelData which stores a Color in a CellColor member variable.  I have an array that is 50x50 of PixelData objects in size called "pixels".  I also have a constant called CANVAS_SIZE which is 50 in this case.  Here are the three methods I have tried using.</p>
  
  <p>This one is recursive.  It is EXTREMELY prone to stack overflows.  I have tried settings a timer that enabled a CanFill member after this method is complete.  This still does not prevent the overflows:</p>
  
  <pre><code>private void FloodFill(Point node, Color targetColor, Color replaceColor)
  {
    //perform bounds checking X
    if ((node.X &gt;= CANVAS_SIZE) || (node.X &lt; 0))
      return; //outside of bounds
  
    //perform bounds checking Y
    if ((node.Y &gt;= CANVAS_SIZE) || (node.Y &lt; 0))
      return; //ouside of bounds
  
    //check to see if the node is the target color
    if (pixels[node.X, node.Y].CellColor != targetColor)
      return; //return and do nothing
    else
    {
      pixels[node.X, node.Y].CellColor = replaceColor;
  
      //recurse
      //try to fill one step to the right
      FloodFill(new Point(node.X + 1, node.Y), targetColor, replaceColor);
      //try to fill one step to the left
      FloodFill(new Point(node.X - 1, node.Y), targetColor, replaceColor);
      //try to fill one step to the north
      FloodFill(new Point(node.X, node.Y - 1), targetColor, replaceColor);
      //try to fill one step to the south
      FloodFill(new Point(node.X, node.Y + 1), targetColor, replaceColor);
  
      //exit method
      return;
    }
  }
  </code></pre>
  
  <p>Next I have a method that uses a Queue based fill.  This method causes OutOfMemory Exceptions at runtime and is EXTREMELY slow when filling the entire canvas.  If just filling a small portion of the canvas, it is somewhat effective:</p>
  
  <pre><code>private void QueueFloodFill(Point node, Color targetColor, Color replaceColor)
  {
    Queue&lt;Point&gt; points = new Queue&lt;Point&gt;();
    if (pixels[node.X, node.Y].CellColor != targetColor)
      return;
  
    points.Enqueue(node);
  
    while (points.Count &gt; 0)
    {
      Point n = points.Dequeue();
      if (pixels[n.X, n.Y].CellColor == targetColor)
        pixels[n.X, n.Y].CellColor = replaceColor;
  
      if (n.X != 0)
      {
        if (pixels[n.X - 1, n.Y].CellColor == targetColor)
          points.Enqueue(new Point(n.X - 1, n.Y));
      }
  
      if (n.X != CANVAS_SIZE - 1)
      {
        if (pixels[n.X + 1, n.Y].CellColor == targetColor)
          points.Enqueue(new Point(n.X + 1, n.Y));
      }
  
      if (n.Y != 0)
      {
        if (pixels[n.X, n.Y - 1].CellColor == targetColor)
          points.Enqueue(new Point(n.X, n.Y - 1));
      }
  
      if (n.Y != CANVAS_SIZE - 1)
      {
        if (pixels[n.X, n.Y + 1].CellColor == targetColor)
          points.Enqueue(new Point(n.X, n.Y + 1));
      }
    }
    DrawCanvas();
    return;
  }
  </code></pre>
  
  <p>The final method that I have tried also uses a queue based floodfill.  This method is MUCH faster than the previous queue based floodfill but also eventually causes OutOfMemory exceptions at runtime.  Again, I have tried setting a FillDelay timer that would prevent the user from rapidly clicking but this still doesn't stop the exceptions from occurring.  Another bug with this one is that it has a hard time properly filling small areas.  I see no point in fixing this until I can get it to not crash. </p>
  
  <pre><code>private void RevisedQueueFloodFill(Point node, Color targetColor, Color replaceColor)
  {
    Queue&lt;Point&gt; q = new Queue&lt;Point&gt;();
    if (pixels[node.X, node.Y].CellColor != targetColor)
      return;
  
    q.Enqueue(node);
    while (q.Count &gt; 0)
    {
      Point n = q.Dequeue();
      if (pixels[n.X, n.Y].CellColor == targetColor)
      {
        Point e = n;
        Point w = n;
        while ((w.X != 0) &amp;&amp; (pixels[w.X, w.Y].CellColor == targetColor))
        {
          pixels[w.X, w.Y].CellColor = replaceColor;
          w = new Point(w.X - 1, w.Y);
        }
  
        while ((e.X != CANVAS_SIZE - 1) &amp;&amp; (pixels[e.X, e.Y].CellColor == targetColor))
        {
          pixels[e.X, e.Y].CellColor = replaceColor;
          e = new Point(e.X + 1, e.Y);
        }
  
        for (int i = w.X; i &lt;= e.X; i++)
        {
          Point x = new Point(i, e.Y);
          if (e.Y + 1 != CANVAS_SIZE - 1)
          {
            if (pixels[x.X, x.Y + 1].CellColor == targetColor)
              q.Enqueue(new Point(x.X, x.Y + 1));
          }
          if (e.Y - 1 != -1)
          {
            if (pixels[x.X, x.Y - 1].CellColor == targetColor)
              q.Enqueue(new Point(x.X, x.Y - 1));
          }
        }
      }
    }
  }
  </code></pre>
  
  <p>Thanks for everyone's help!  All of these methods are based on pseudo code on wikipedia.</p>
  
  <p>EDIT:</p>
  
  <p>I selected the RevisedQueueFloodFill and modified as suggested so that no variables are declared within the loops.  An OutOfMemory is still generated.  Even with a filldelay timer.</p>
  
  <pre><code>private void RevisedQueueFloodFill(Point node, Color targetColor, Color replaceColor)
  {
    Queue&lt;Point&gt; q = new Queue&lt;Point&gt;();
  
    if (pixels[node.X, node.Y].CellColor != targetColor)
      return;
  
    q.Enqueue(node);
  
    Point n, e, w, x;
    while (q.Count &gt; 0)
    {
      n = q.Dequeue();
      if (pixels[n.X, n.Y].CellColor == targetColor)
      {
        e = n;
        w = n;
        while ((w.X != 0) &amp;&amp; (pixels[w.X, w.Y].CellColor == targetColor))
        {
          pixels[w.X, w.Y].CellColor = replaceColor;
          w = new Point(w.X - 1, w.Y);
        }
  
        while ((e.X != CANVAS_SIZE - 1) &amp;&amp; (pixels[e.X, e.Y].CellColor == targetColor))
        {
          pixels[e.X, e.Y].CellColor = replaceColor;
          e = new Point(e.X + 1, e.Y);
        }
  
        for (int i = w.X; i &lt;= e.X; i++)
        {
          x = new Point(i, e.Y);
          if (e.Y + 1 != CANVAS_SIZE - 1)
          {
            if (pixels[x.X, x.Y + 1].CellColor == targetColor)
              q.Enqueue(new Point(x.X, x.Y + 1));
          }
          if (e.Y - 1 != -1)
          {
            if (pixels[x.X, x.Y - 1].CellColor == targetColor)
              q.Enqueue(new Point(x.X, x.Y - 1));
          }
        }
      }
    }
  }
  </code></pre>