Различные методы выполнения FloodFill

Question

ОК, у меня есть несколько разных способов выполнения FloodFill.Все они вызывают проблемы.Я перечислю 3 метода и объясню, что происходит с каждым из них.Если бы кто-нибудь мог дать мне несколько советов, это было бы здорово.Я видел несколько подобных постов, но ни один из них не был для C #, Java или VB.net (единственные языки, которые я знаю).

Для этого есть то, что у меня есть класс с именем PixelData, который хранитЦвет в переменной-члене 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;
}

Последний метод, который я пробовал, также использует заливку на основе очереди.Этот метод НАМНОГО быстрее, чем предыдущая заливка на основе очереди, но также в конечном итоге вызывает исключения 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));
        }
      }
    }
  }
}

Answer 1

Я понятия не имею, сработает ли это, но я подозреваю, что используется гораздо больше памяти, чем необходимо, из-за всех «новых» операторов и, возможно, из-за интенсивной природы алгоритма, сборщика мусорау меня не было шанса войти?

Я переписал алгоритм так, чтобы все переменные 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);
            }
        }
    }
}

Answer 2

Хорошо, пара вещей:

1. C # имеет рекурсивный предел (определяется размером стека) глубиной в несколько тысяч.Это означает, что вы не можете пойти глубже в рекурсии вниз, не вызывая переполнение стека.Как только метод возвращает метод, его указатель удаляется из стека.Ваша проблема не совпадает с OutOfMemoryException.Стек содержит указатели, а не фактическую память, и как таковой не предназначен для хранения тысяч указателей.

2. Сборка мусора - это то, что вызывает исключение нехватки памяти.Вы должны прекратить объявлять переменные внутри ваших циклов.Сборщик мусора видит их как «все еще в области» и не освободит пространство памяти, пока цикл не завершит все итерации.Но если вы используете один и тот же адрес памяти, он будет просто перезаписывать его каждый раз и вряд ли будет использовать какую-либо память.

Для ясности:

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

Должно быть какthis:

Point x;

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

Это будет использовать адрес памяти так, как вы этого хотите.

Надеюсь, это поможет!

Answer 3

Проблема, связанная с базовым алгоритмом, заключается в том, что вы ставите в очередь несколько посещений точки и выполняете поиск в ширину. Это означает, что вы создаете несколько копий одной и той же точки во время каждого прохода. Это накапливается в геометрической прогрессии, поскольку каждая точка может распространяться (ставить в очередь больше точек), даже если это не целевой цвет (уже замененный.)

Установите цвет в то же время, когда вы ставите их в очередь (а не в очередь), чтобы никогда не добавлять их в очередь дважды.

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