不同的填埋方法

本文关键字：方法 | 更新日期: 2023-09-27 18:04:11

好了，我有几个不同的方法来执行洪水填充。所有这些都会造成问题。我将列出这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;
}

我尝试的最后一种方法也使用基于队列的洪水填充。这种方法比之前基于队列的泛滥填充要快得多，但最终也会在运行时导致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。即使有一个填充延迟定时器

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

不同的填埋方法

好了，有几件事:

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

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

希望有帮助!

我不知道这是否会起作用，但我自己的怀疑是，由于所有的'new'操作符，可能由于算法的密集性质，垃圾收集器没有机会启动，因此使用了比必要更多的内存。

我已经重写了算法，所以所有的点变量只是得到重用，而不是，但我目前还没有测试的方法。

我还擅自修改了前几行代码，但这是因为我的一个讨厌的问题，你发现大多数填充算法都需要用户指定目标颜色，而实际上你可以简单地从参数中给出的点自动获得目标颜色。

无论如何，试着使用这个，否则就嘲笑它:

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

在第三种方法中，您应该检查当前点的西面和东面的像素。不是检查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));
                }
            }
        }
    }
}

这里的基本算法的问题是，您排队多次访问到一个点，并进行广度优先搜索。这意味着您在每次传递过程中创建同一点的多个副本。这是指数级累积的，因为每个点都允许扩展(排队更多的点)，即使它不是目标颜色(已经被替换)

设置颜色的同时，你进入队列(而不是在Dequeue)，这样你永远不会结束添加它们到队列两次。

相关文章：