c# - 执行 FloodFill 的不同方法

Question

好的，大家好，我有几种不同的方法来执行 FloodFill。所有这些都会引起问题。我将列出这 3 种方法并解释每种方法会发生什么。如果有人能给我一些建议，那就太好了。我看过一些类似的帖子，但没有一篇是针对 C#、java 或 VB.net(我知道的唯一语言)的。

为此，我有一个名为 PixelData 的类，它在 CellColor 成员变量中存储 Color。我有一个大小为 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 异常，并且在填充整个 Canvas 时速度极慢。如果只是填充 Canvas 的一小部分，还是有些效果的:

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

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

希望对您有所帮助!