大家好,我有几种不同的方法可以执行FloodFill。但这些方法都会带来问题。我将列出这3种方法并解释每一种方法所发生的事情。如果有人能给我一些建议,那就太好了。我看到了一些类似的帖子,但它们没有用C#,java或VB.net(我唯一知道的语言)。
假设我有一个名为PixelData的类,其中存储了一个CellColor成员变量中的颜色。我有一个大小为50x50的PixelData对象数组称为“pixels”。我还有一个常量称为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;
}
我尝试的最后一种方法也使用了基于队列的泛洪填充。这种方法比以前的基于队列的泛洪填充要快得多,但最终也会在运行时导致内存不足异常。我已经尝试设置一个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错误。即使使用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);
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));
}
}
}
}
}