10

我正在尝试实现一种类似于洪水填充的算法。问题是我不确定我应该以什么方式实现它，例如递归 - 非递归。
我知道每个都有其缺陷，但其中一个必须比另一个更快。当非递归每次分配 4 个新点时，递归在堆栈上打开新函数。
非迭代示例：

Stack<Point> stack = new Stack<Point>();
    stack.Push(q);
    while (stack.Count > 0)
    {
        Point p = stack.Pop();
        int x = p.X;
        int y = p.Y;
        if (y < 0 || y > h - 1 || x < 0 || x > w - 1)
                continue;
        byte val = vals[y, x];
        if (val == SEED_COLOR)
        {
                vals[y, x] = COLOR;
                stack.Push(new Point(x + 1, y));
                stack.Push(new Point(x - 1, y));
                stack.Push(new Point(x, y + 1));
                stack.Push(new Point(x, y - 1));
        }
    }

编辑：我将在 600X600 像素的地图上应用以下算法。虽然洪水填充不会应用于整个地图，但每次迭代它应该覆盖大约 30% - 80% 的地图。我的意思是在高度图中发现边缘并标记这些边缘以供进一步使用。

4

3 回答 3

2

制作一个掩码 - 一个并行的 2-dim 字节数组。未检查区域字节为 0，对于淹没区域的新边界，它将具有值 1。对于淹没区域的内部 - 值 2。并保留当前边界点的列表。

在外部循环的任何一端，您都拥有带有标记的当前边界、内部和外部区域以及边界点数组的掩码。因此，您将仅在边界上检查新点。在检查边界点的第一个数组列表时，您正在创建第二个边界数组列表和第二个掩码。在下一步中，您重新创建第一个边框数组和蒙版。这样一来，我们可以使用简单while的循环代替递归，因为您在任何步骤检查的数据结构都非常简单。

顺便说一句，您忘记检查新点的坐标是否位于绘制的边框或整个矩形的边框上。

至于循环通过所有相邻点，请查看我的算法here

于 2012-02-16T20:39:07.723 回答
1

计算机非常有效地处理 XY 循环和 2D 阵列。

查看此视频以了解如果将标准递归例程置于循环中会发生什么： https ://www.youtube.com/watch?v=LvacRISl99Y 在此处输入图像描述

您可以使用一个二维数组来记录所有已验证的空间，而不是使用复杂的逻辑来跟踪先前验证过的相邻空间。从已验证的数组中读取 2-3 条指令：如果像素 [23,23] 已验证，则填充它并检查它的邻居。

于 2018-09-22T11:30:12.853 回答
0

如果图像很复杂，递归洪水填充可能会溢出堆栈。使用非递归洪水填充。

如果您关心分配，您可以将一个点表示为 long 类型的打包值，并编写您自己的 LongStack，在内部将 long 值存储在一个数组中。

于 2012-02-16T20:43:20.860 回答