执行FloodFill的不同方法

好的，我有几种不同的方法来执行FloodFill。 所有这些都会导致问题。 我将列出3种方法并解释每种方法会发生什么。 如果有人能给我一些很棒的指示。 我见过一些类似的post，但没有一个是C＃，java或VB.net（我知道的唯一语言）。

对此的给予是我有一个名为PixelData的类，它将一个Color存储在CellColor成员变量中。 我有一个50×50 PixelData对象的数组，称为“像素”。 我也有一个名为CANVAS_SIZE的常量，在这种情况下为50。 以下是我尝试过的三种方法。

这个是递归的。 它非常容易出现堆栈溢出。 我已经尝试设置一个计时器，在此方法完成后启用CanFill成员。 这仍然不能防止溢出：

private void FloodFill(Point node, Color targetColor, Color replaceColor) { //perform bounds checking X if ((node.X >= CANVAS_SIZE) || (node.X = 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; } } 

接下来，我有一个使用基于队列的填充的方法。 此方法在运行时导致OutOfMemoryexception，并且在填充整个canvas时非常慢。 如果只填充canvas的一小部分，它有点有效：

 private void QueueFloodFill(Point node, Color targetColor, Color replaceColor) { Queue points = new Queue(); if (pixels[node.X, node.Y].CellColor != targetColor) return; points.Enqueue(node); while (points.Count > 0) { Point n = points.Dequeue(); if (pixels[nX, nY].CellColor == targetColor) pixels[nX, nY].CellColor = replaceColor; if (nX != 0) { if (pixels[nX - 1, nY].CellColor == targetColor) points.Enqueue(new Point(nX - 1, nY)); } if (nX != CANVAS_SIZE - 1) { if (pixels[nX + 1, nY].CellColor == targetColor) points.Enqueue(new Point(nX + 1, nY)); } if (nY != 0) { if (pixels[nX, nY - 1].CellColor == targetColor) points.Enqueue(new Point(nX, nY - 1)); } if (nY != CANVAS_SIZE - 1) { if (pixels[nX, nY + 1].CellColor == targetColor) points.Enqueue(new Point(nX, nY + 1)); } } DrawCanvas(); return; } 

我尝试过的最后一种方法也使用基于队列的floodfill。 此方法比先前基于队列的floodfill快得多，但最终也会在运行时导致OutOfMemoryexception。 同样，我已经尝试设置一个FillDelay计时器，可以防止用户快速点击，但这仍然不能阻止exception发生。 这个问题的另一个缺点是它很难适当地填充小区域。 我认为解决这个问题没有意义，直到我能够让它不崩溃。

 private void RevisedQueueFloodFill(Point node, Color targetColor, Color replaceColor) { Queue q = new Queue(); if (pixels[node.X, node.Y].CellColor != targetColor) return; q.Enqueue(node); while (q.Count > 0) { Point n = q.Dequeue(); if (pixels[nX, nY].CellColor == targetColor) { Point e = n; Point w = n; while ((wX != 0) && (pixels[wX, wY].CellColor == targetColor)) { pixels[wX, wY].CellColor = replaceColor; w = new Point(wX - 1, wY); } while ((eX != CANVAS_SIZE - 1) && (pixels[eX, eY].CellColor == targetColor)) { pixels[eX, eY].CellColor = replaceColor; e = new Point(eX + 1, eY); } for (int i = wX; i <= eX; i++) { Point x = new Point(i, eY); if (eY + 1 != CANVAS_SIZE - 1) { if (pixels[xX, xY + 1].CellColor == targetColor) q.Enqueue(new Point(xX, xY + 1)); } if (eY - 1 != -1) { if (pixels[xX, xY - 1].CellColor == targetColor) q.Enqueue(new Point(xX, xY - 1)); } } } } } 

谢谢大家的帮助！ 所有这些方法都基于维基百科上的伪代码。

编辑：

我选择了RevisedQueueFloodFill并按照建议修改，以便在循环中不声明变量。 仍然生成OutOfMemory。 即使使用filldelay计时器。

 private void RevisedQueueFloodFill(Point node, Color targetColor, Color replaceColor) { Queue q = new Queue(); 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[nX, nY].CellColor == targetColor) { e = n; w = n; while ((wX != 0) && (pixels[wX, wY].CellColor == targetColor)) { pixels[wX, wY].CellColor = replaceColor; w = new Point(wX - 1, wY); } while ((eX != CANVAS_SIZE - 1) && (pixels[eX, eY].CellColor == targetColor)) { pixels[eX, eY].CellColor = replaceColor; e = new Point(eX + 1, eY); } for (int i = wX; i <= eX; i++) { x = new Point(i, eY); if (eY + 1 != CANVAS_SIZE - 1) { if (pixels[xX, xY + 1].CellColor == targetColor) q.Enqueue(new Point(xX, xY + 1)); } if (eY - 1 != -1) { if (pixels[xX, xY - 1].CellColor == targetColor) q.Enqueue(new Point(xX, xY - 1)); } } } } } 

Answer 1

好吧，有几件事：

1. C＃具有几千深度的递归限制（由堆栈大小确定）。 这意味着您不能向下递归DEEPER而不会导致堆栈溢出。 一旦方法返回，其指针就会从堆栈中弹出。 您的问题与OutOfMemoryException不同。 堆栈保存指针而非实际内存，因此并不意味着拥有数千个指针。

2. 垃圾收集是导致内存不足的原因。 您需要停止在循环内声明变量。 垃圾收集器将这些视为“仍在范围内”，并且在循环完成所有迭代之前不会释放内存空间。 但是如果你使用相同的内存地址，它每次都会覆盖它，几乎不使用任何内存。

要明确：

 for (int i = wX; i <= eX; i++) { Point x = new Point(i, eY); } 

应该是这样的：

 Point x; for(int i = wX; i<= eX; i++) { x = new Point(i, eY); } 

这将重用您想要的内存地址。

希望有所帮助！

Answer 2

我不知道这是否可行，但我自己怀疑由于所有“新”运算符而使用的内存比必要的多得多，并且可能由于算法的密集性，垃圾收集器没有有机会参加比赛吗？

我已经重写了算法，所以所有的Point变量都被重用了，但我目前还没有办法测试这个。

我也冒昧地改变了前几行代码，但这是因为我的一个小小的烦恼，你发现大多数泛洪填充算法需要用户指定目标颜色，实际上你可以只需从参数中给出的点自动获取目标颜色。

无论如何，尝试使用它，或者只是嘲笑它：

 private void RevisedQueueFloodFill(Point node, Color replaceColor) { Color targetColor = pixels[node.X, node.Y].CellColor; if (targetColor == replaceColor) return; Queue q = new Queue(); q.Enqueue(node); Point n, t, u; while (q.Count > 0) { n = q.Dequeue(); if (pixels[nX, nY].CellColor == targetColor) { t = n; while ((tX > 0) && (pixels[tX, tY].CellColor == targetColor)) { pixels[tX, tY].CellColor = replaceColor; tX--; } int XMin = tX + 1; t = n; t.X++; while ((tX < CANVAS_SIZE - 1) && (pixels[tX, tY].CellColor == targetColor)) { pixels[tX, tY].CellColor = replaceColor; t.X++; } int XMax = tX - 1; t = n; t.Y++; u = n; uY--; for (int i = XMin; i <= XMax; i++) { tX = i; uX = i; if ((tY < CANVAS_SIZE - 1) && (pixels[tX, tY].CellColor == targetColor)) q.Enqueue(t); if ((uY >= 0) && (pixels[uX, uY].CellColor == targetColor)) q.Enqueue(u); } } } } 

Answer 3

在第三种方法中，您应该检查当前点的西边和东边的像素。 你应该检查pixels[wX - 1, wY]而不是pixels[eX, eY]而不是检查pixels[eX + 1, eY] 。 这是我对你的第三种方法的看法：

 private void RevisedQueueFloodFill(Point node, Color targetColor, Color replaceColor) { if (pixels[node.X, node.Y].CellColor != targetColor) return; Queue Q = new Queue(); Q.Enqueue(node); while (Q.Count != 0) { Point n = Q.Dequeue(); if (pixels[nX, nY].CellColor == targetColor) { int y = nY; int w = nX; int e = nX; while (w > 0 && pixels[w - 1, y].CellColor == targetColor) w--; while (e < CANVAS_SIZE - 1 && pixels[e + 1, y].CellColor == targetColor) e++; for (int x = w; x <= e; x++) { pixels[x, y].CellColor = replaceColor; if (y > 0 && pixels[x, y - 1].CellColor == targetColor) { Q.Enqueue(new Point(x, y - 1)); } if (y < CANVAS_SIZE - 1 && pixels[x, y + 1].CellColor == targetColor) { Q.Enqueue(new Point(x, y + 1)); } } } } } 

Answer 4

这里使用基本算法的问题是您将多次访问排队到一个点并进行广度优先搜索。 这意味着您在每次传递期间创建同一点的多个副本。 这会以指数方式累积，因为每个点都可以传播（排队更多点），即使它不是目标颜色（已经被替换）。

在您将它们排队的同时设置颜色（而不是在Dequeue上），这样您就不会最终将它们添加到Queue两次。