我正在尝试实现一种与洪水填充类似的算法。问题是我不确定应该以什么方式实现它,例如递归-非递归。
我知道每一种都有其缺陷,但其中一种必须比另一种更快。当非递归每次分配 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% 左右。我的观点是发现高度图中的边缘并标记这些边缘以供进一步使用。
制作一个掩码 - 一个并行的 2 维字节数组。未检查区域字节为 0,对于淹没区域的新边界,其值为 1。对于淹没区域的内部,值为 2。并保留当前边界点的列表。
在外循环的任何一端,您都有带有标记的当前边界、内部和外部区域以及边界点数组的蒙版。因此,您将仅检查边界上的新点。在检查边界点的第一个数组列表时,您正在创建第二个边界数组列表和第二个掩码。在下一步中,您将重新创建第一个边框数组和蒙版。沿着这条路,我们可以使用简单的while
循环而不是递归,因为你在任何步骤检查的数据结构都非常简单。
顺便说一句,您忘记检查新点的坐标是在绘制的边框上还是在整个矩形的边框上。
至于循环遍历所有相邻点,看我的算法here https://codereview.stackexchange.com/a/8947/11012
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)