Алгоритм заполнения Flood вызывает исключение OutOfMemory

Question

Ну, я получаю план (путь) здания.И есть проблема.Когда я перебираю его пиксели, я проверяю, является ли текущий пиксель белым, чтобы начать обнаруживать его стены.

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

Хорошо, я уже реализовал его, но у меня есть проблемы.

    public static void FloodFill(ref Color[] source, Point pt, int width, int height, Color targetColor, Color replacementColor)
    {
        Stack<Point> pixels = new Stack<Point>();

        targetColor = source[P(pt.x, pt.y, width, height)];
        pixels.Push(pt);

        while (pixels.Count > 0)
        {
            Point a = pixels.Pop();

            if (source[P(a.x, a.y, width, height)] == targetColor)
            {
                source[P(a.x, a.y, width, height)] = replacementColor;

                if (a.x > 0)
                    pixels.Push(new Point(a.x - 1, a.y));

                if (a.x < width)
                    pixels.Push(new Point(a.x + 1, a.y));

                if (a.y > 0)
                    pixels.Push(new Point(a.x, a.y - 1));

                if (a.y < height)
                    pixels.Push(new Point(a.x, a.y + 1));
            }
        }
    }

Извлеченоfrom: https://simpledevcode.wordpress.com/2015/12/29/flood-fill-algorithm-using-c-net/

Проблема здесь в том, что по какой-то причине ключевое слово ref не вступает в силу.

Моя реализация:

    private IEnumerator MainGenerationDebug(Color[] source, Color32[] target, int width, int height)
    {
        // (1)
        for (int i = 0; i < source.Length; Interlocked.Increment(ref i))
        {
            // (2)
            Color c = source[i];

            // (3)
            int x = i % width,
                y = i / width;

            // (4) & (5)
            yield return IntMapIteration(source, target, width, c, i, exceptions, (s, t) =>
            {
                source = s;
                target = t;
            });

            // (6)
            if (c == Color.white)
            {
                F.FloodFill(ref source, new Point(x, y), width, height, Color.white, Color.red);
            }
        }
    }

Процессследующее:

1. Я зацикливаю все пиксели, потому что я в другом потоке, я использую Interlocked.Increment.
2. Я получаю текущий цвет
3. Я получаютекущие x, y (2D) из индекса (1D)
4. Из-за того, что я нахожусь в сопрограмме (я отлаживаю, поэтому мне нужно посмотреть, что происходит), я использую yielding
5. КогдаIEnumerator заканчивает, я называю Действие.(Я использую IEnumerators, потому что я вызываю сопрограмму в Unity3D)
6. После того, как все закончится, если текущий пиксель будет белым, я начну заполнять массив.

Я думаювсе правильно.Возможно, я что-то упустил.

Что вы можете сказать по этому поводу?

Answer 1

Я создал собственную реализацию, чтобы показать, что происходит и почему лучше использовать HashSet.

Почему используется HashSet? HashSet.Contains быстрее .

Это фактическая реализация:

using System.Collections.Generic;
using System.Linq;

public static class F
{
    /// <summary>
           /// Floods the fill.
           /// </summary>
           /// <typeparam name="T"></typeparam>
           /// <param name="source">The source.</param>
           /// <param name="x">The x.</param>
           /// <param name="y">The y.</param>
           /// <param name="width">The width.</param>
           /// <param name="height">The height.</param>
           /// <param name="target">The target to replace.</param>
           /// <param name="replacement">The replacement.</param>
    public static void FloodFill<T>(this T[] source, int x, int y, int width, int height, T target, T replacement)
    {
        int i = 0;

        FloodFill(source, x, y, width, height, target, replacement, out i);
    }

    /// <summary>
           /// Floods the array following Flood Fill algorithm
           /// </summary>
           /// <typeparam name="T"></typeparam>
           /// <param name="source">The source.</param>
           /// <param name="x">The x.</param>
           /// <param name="y">The y.</param>
           /// <param name="width">The width.</param>
           /// <param name="height">The height.</param>
           /// <param name="target">The target to replace.</param>
           /// <param name="replacement">The replacement.</param>
           /// <param name="i">The iterations made (if you want to debug).</param>
    public static void FloodFill<T>(this T[] source, int x, int y, int width, int height, T target, T replacement, out int i)
    {
        i = 0;

        // Queue of pixels to process. :silbar:
        HashSet<int> queue = new HashSet<int>();

        queue.Add(Pn(x, y, width));

        while (queue.Count > 0)
        {
            int _i = queue.First(),
              _x = _i % width,
              _y = _i / width;

            queue.Remove(_i);

            if (source[_i].Equals(target))
                source[_i] = replacement;

            for (int offsetX = -1; offsetX < 2; offsetX++)
                for (int offsetY = -1; offsetY < 2; offsetY++)
                {
                    // do not check origin or diagonal neighbours
                    if (offsetX == 0 && offsetY == 0 || offsetX == offsetY || offsetX == -offsetY || -offsetX == offsetY)
                        continue;

                    int targetIndex = Pn(_x + offsetX, _y + offsetY, width);
                    int _tx = targetIndex % width,
                      _ty = targetIndex / width;

                    // skip out of bounds point
                    if (_tx < 0 || _ty < 0 || _tx >= width || _ty >= height)
                        continue;

                    if (!queue.Contains(targetIndex) && source[targetIndex].Equals(target))
                    {
                        queue.Add(targetIndex);
                        ++i;
                    }
                }
        }
    }

    public static int Pn(int x, int y, int w)
    {
        return x + (y * w);
    }
}

Вы можете видеть это здесь, работая: https://dotnetfiddle.net/ZacRiB (с использованием Stack было O (4n) (я выяснил, как решить эту проблему, но я не могу найти реальный код), а HashSet - O (n - 1)).