执行泛洪填充的不同方法

Question

大家好，我有几种不同的方法可以执行FloodFill。但这些方法都会带来问题。我将列出这3种方法并解释每一种方法所发生的事情。如果有人能给我一些建议，那就太好了。我看到了一些类似的帖子，但它们没有用C＃，java或VB.net（我唯一知道的语言）。

假设我有一个名为PixelData的类，其中存储了一个CellColor成员变量中的颜色。我有一个大小为50x50的PixelData对象数组称为“pixels”。我还有一个常量称为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;
}

我尝试的最后一种方法也使用了基于队列的泛洪填充。这种方法比以前的基于队列的泛洪填充要快得多，但最终也会在运行时导致内存不足异常。我已经尝试设置一个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));
        }
      }
    }
  }
}

- Satanfx55

---

听起来你这里的问题不仅仅是泛洪填充；50x50显然只有2500个像素，即使在最高色深下，也只有20k。没有任何泛洪填充算法会单独耗尽内存的机会。 - Flynn1179

你的网格在使用内存时有多大？在floodfill中，你已经描述了几乎所有的内容。如果需要大量的内存，则可能需要选择不同的数据结构来表示您的网格。 - Shamim Hafiz - MSFT

@Flynn1179 O_O 你用的是什么位深度？我想要那个显示器。 - Rag

@Flynn1179 那是18,446,744,073,709,551,616种颜色。 - Rag

@Flynn1179 在我发帖之前，我看过那个页面。作者使用了不安全的代码，而且似乎有比你实际需要完成工作更多的代码。对我来说，这也非常令人困惑。不过还是谢谢你的建议 :) - Satanfx55

Answer 1

我不确定这个方法是否有效，但我的猜测是由于所有的“new”操作符以及算法的密集性，可能使用了比必要更多的内存，垃圾回收器没有机会启动？

我已经重写了算法，使得所有的Point变量都可以被重复使用，但目前还没有测试的方法。

我也修改了代码的前几行，因为我很讨厌大多数洪水填充算法需要用户指定目标颜色，而实际上可以从参数中给出的点自动获取目标颜色。

无论如何，请尝试使用这个方法，或者只是笑一笑：

private void RevisedQueueFloodFill(Point node, Color replaceColor)
{
    Color targetColor = pixels[node.X, node.Y].CellColor;
    if (targetColor == replaceColor) return;

    Queue<Point> q = new Queue<Point>();
    q.Enqueue(node);

    Point n, t, u;

    while (q.Count > 0)
    {
        n = q.Dequeue();
        if (pixels[n.X, n.Y].CellColor == targetColor)
        {

            t = n;
            while ((t.X > 0) && (pixels[t.X, t.Y].CellColor == targetColor))
            {
                pixels[t.X, t.Y].CellColor = replaceColor;
                t.X--;
            }
            int XMin = t.X + 1;


            t = n;
            t.X++;
            while ((t.X < CANVAS_SIZE - 1) &&
                   (pixels[t.X, t.Y].CellColor == targetColor))
            {
                pixels[t.X, t.Y].CellColor = replaceColor;
                t.X++;
            }
            int XMax = t.X - 1;

            t = n;
            t.Y++;

            u = n;
            u.Y--;

            for (int i = XMin; i <= XMax; i++)
            {
                t.X = i;
                u.X = i;

                if ((t.Y < CANVAS_SIZE - 1) &&
                    (pixels[t.X, t.Y].CellColor == targetColor)) q.Enqueue(t);

                if ((u.Y >= 0) &&
                    (pixels[u.X, u.Y].CellColor == targetColor)) q.Enqueue(u);
            }
        }
    }
}

- Ronstar308

---

在.NET中，“new”并不是什么可怕的东西。它的内存模型专门设计用于容纳大量小型、短寿命的对象。此外，由于Point是值类型，因此甚至不需要在这里分配新内存（至少在初始化局部变量时不需要）。你需要警惕的是Enqueue；罪魁祸首是算法，而不是语言或运行时。 - Dan Bryant

Answer 2

好的，有几件事情需要注意：

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

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

希望能有所帮助！

- Joseph Hamilton

---

请查看我上面的编辑。还有什么其他方法可以防止OutOfMemory异常？ - Satanfx55

你关于内存使用的评论是不正确的。Point是一个值类型，无论哪种情况下它都只会使用一个本地槽位。而且，即使它是一个引用类型，在每次循环迭代中分配的引用仍然会变得无法访问并可供收集。真正的问题是，队列可以根据正确的输入增长到巨大的大小。 - Dan Bryant

Answer 3

这里的基本算法存在问题，因为您会将多次访问到同一点的命令加入队列并进行广度优先搜索。这意味着您在每个遍历过程中都会创建该点的多个副本。由于每个点都可以扩散（排队更多点），即使它不是目标颜色（已被替换），也会导致指数级增长。

在入队时同时设置颜色（而不是在出队时），这样就永远不会将它们添加到队列中两次。

- Dan Bryant

Answer 4

在第三种方法中，您应该检查当前点的正西和正东像素。而不是检查 pixels[w.X, w.Y]，您应该检查 pixels[w.X - 1, w.Y]，而不是 pixels[e.X, e.Y]，您应该有 pixels[e.X + 1, e.Y]。以下是我对您的第三种方法的看法：

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

    Queue<Point> Q = new Queue<Point>();
    Q.Enqueue(node);

    while (Q.Count != 0)
    {
        Point n = Q.Dequeue();
        if (pixels[n.X, n.Y].CellColor == targetColor)
        {
            int y = n.Y;
            int w = n.X;
            int e = n.X;
            while (w > 0 && pixels[w - 1, y].CellColor == targetColor) w--;
            while (e < CANVAS_SIZE - 1 && pixels[e + 1, y].CellColor == targetColor) e++;

            for (int x = w; x <= e; x++)
            {
                pixels[x, y].CellColor = replaceColor;
                if (y > 0 && pixels[x, y - 1].CellColor == targetColor)
                {
                    Q.Enqueue(new Point(x, y - 1));
                }
                if (y < CANVAS_SIZE - 1 && pixels[x, y + 1].CellColor == targetColor)
                {
                    Q.Enqueue(new Point(x, y + 1));
                }
            }
        }
    }
}

- Ozgur Ozcitak