执行FloodFill的不同方法

Question

好的,我有几种不同的方法来执行FloodFill.所有这些都会导致问题.我将列出3种方法并解释每种方法会发生什么.如果有人能给我一些很棒的指示.我见过一些类似的帖子,但没有一个是C#,java或VB.net(我知道的唯一语言).

对此的给定是我有一个名为PixelData的类,它将Color存储在CellColor成员变量中.我有一个50x50 PixelData对象的数组,称为"像素".我还有一个名为CANVAS_SIZE的常量,在这种情况下为50.以下是我尝试过的三种方法.

这个是递归的.它非常容易出现堆栈溢出.我已经尝试设置一个计时器,在此方法完成后启用CanFill成员.这仍然不能防止溢出:

private void FloodFill(Point node, Color targetColor, Color replaceColor)
{
  //perform bounds checking X
  if ((node.X >= CANVAS_SIZE) || (node.X < 0))
    return; //outside of bounds

  //perform bounds checking Y
  if ((node.Y >= CANVAS_SIZE) || (node.Y < 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;
  }
}

接下来,我有一个使用基于队列的填充的方法.此方法在运行时导致OutOfMemory异常,并且在填充整个画布时非常慢.如果只填充画布的一小部分,它有点有效:

private void QueueFloodFill(Point node, Color targetColor, Color replaceColor)
{
  Queue<Point> points = new Queue<Point>();
  if (pixels[node.X, node.Y].CellColor != targetColor)
    return;

  points.Enqueue(node);

  while (points.Count > 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;
}

我尝试的最后一个方法也使用基于队列的floodfill.此方法比先前基于队列的floodfill快得多,但最终也会在运行时导致OutOfMemory异常.同样,我尝试设置一个FillDelay计时器,以防止用户快速点击,但这仍然不能阻止发生异常.这个问题的另一个缺点是它很难适当地填充小区域.我认为解决这个问题没有意义,直到我能够让它不崩溃.

private void RevisedQueueFloodFill(Point node, Color targetColor, Color replaceColor)
{
  Queue<Point> q = new Queue<Point>();
  if (pixels[node.X, node.Y].CellColor != targetColor)
    return;

  q.Enqueue(node);
  while (q.Count > 0)
  {
    Point n = q.Dequeue();
    if (pixels[n.X, n.Y].CellColor == targetColor)
    {
      Point e = n;
      Point w = n;
      while ((w.X != 0) && (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) && (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 <= 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));
        }
      }
    }
  }
}

谢谢大家的帮助!所有这些方法都基于维基百科上的伪代码.

编辑:

我选择了RevisedQueueFloodFill并按照建议修改,以便在循环中不声明变量.仍然生成OutOfMemory.即使使用filldelay计时器.

private void RevisedQueueFloodFill(Point node, Color targetColor, Color replaceColor)
{
  Queue<Point> q = new Queue<Point>();

  if (pixels[node.X, node.Y].CellColor != targetColor)
    return;

  q.Enqueue(node);

  Point n, e, w, x;
  while (q.Count > 0)
  {
    n = q.Dequeue();
    if (pixels[n.X, n.Y].CellColor == targetColor)
    {
      e = n;
      w = n;
      while ((w.X != 0) && (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) && (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 <= 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));
        }
      }
    }
  }
}

Answer 1

好的，有几件事：

1. C# 的递归限制（由堆栈大小决定）为几千深度。这意味着您无法在不导致堆栈溢出的情况下进一步向下递归。一旦方法返回，它的指针就会从堆栈中弹出。您的问题与 OutOfMemoryException 不同。堆栈保存的是指针而不是实际的内存，因此并不意味着保存数千个指针。

2. 垃圾收集是导致内存不足异常的原因。您需要停止在循环内声明变量。垃圾收集器将它们视为“仍在范围内”，并且在循环完成所有迭代之前不会释放内存空间。但如果你使用相同的内存地址，它每次都会覆盖它，几乎不使用任何内存。

需要明确的是：

for (int i = w.X; i <= e.X; i++)
{
    Point x = new Point(i, e.Y);
}

应该是这样的：

Point x;

for(int i = w.X; i<= e.X; i++)
{
   x = new Point(i, e.Y);
}

这将像您希望的那样重用内存地址。

希望有帮助！