洪水填充算法导致 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));
            }
        }
    }

摘自：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);
            }
        }
    }

过程如下：

我开始循环所有像素，因为我在另一个我使用的线程中 Interlocked.Increment。
我得到当前颜色
我从索引 (1D) 得到当前的 x, y (2D)
由于我在协程中（我正在调试所以我需要看看发生了什么）我使用 yielding
当 IEnumerator 完成时，我调用一个动作。（我使用 IEnumerators 因为我在 Unity3D 中调用协程）
一切完成后，如果当前像素为白色，我开始对数组进行洪水填充。

我认为一切都是正确的。也许我错过了什么。

你对此有何看法？

Answer 1

我创建了一个自己的实现来展示正在发生的事情以及为什么使用 HashSet 更好。

为什么用HashSet？ HashSet.Contains is quicklier.

这是实际的实现：

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)).

洪水填充算法导致 OutOfMemory 异常

Flood fill algorithm is causing OutOfMemory Exception

c#

out-of-memory

flood-fill

unity3d