java - FloodFill 算法产生 StackOvlerflowError

Question

我有一个包含图像的Java程序，我正在尝试使用洪水填充算法来使用以下函数(canvas)将封闭区域内的每个黑色像素替换为白色像素是一个BufferedImage):

public void floodFill(Point2i start, int target, int grep){
    if(start.x < 0 || start.x >= width || start.y < 0 || start.y >= height)return;
    if(canvas.getRGB(start.x, start.y) != target)return;
    canvas.setRGB(start.x, start.y, grep);
    floodFill(new Point2i(start.x+1, start.y), target, grep);
    floodFill(new Point2i(start.x-1, start.y), target, grep);
    floodFill(new Point2i(start.x, start.y+1), target, grep);
    floodFill(new Point2i(start.x, start.y-1), target, grep);
}

问题是，我在第三行收到一个java.lang.StackOverflowError...我想一定有更好的方法来做到这一点，并且不会导致此错误，不是吗？在那里吗？我正在使用相当数量的 RAM(2 GB)运行 JVM，那么如何为有效的 BufferedImage 编写洪水填充函数呢？

Answer 1

如果target等于grep，你的程序总是返回到前一点。

例如:

• 从点(0,0) -> 前往点(1,0) ...
• 从点(1,0) -> 前往点(2,0)，然后到达点(0,0)

因此，您应该使用 boolean 数组或类似数组来检查所有访问过的点。看看Depth first search了解更多信息。

您可以考虑从递归到迭代方法切换，这对内存更友好，请参阅Breadth first search了解更多信息。

增加堆栈大小也有帮助，正如 k_g 已经在他/她的回答中指出的那样。