Java - 递归 2D 布尔数组方法上的 StackOverflow 错误不应发生

Question

我正在开发一个可运行的java小程序，它具有填充功能，很像Microsoft Paint等绘图程序中的填充方法。

这就是我的填充方法的工作原理：

1. 小程序使用 .getRGB 获取用户单击的颜色

2. 小程序创建窗口中所有像素的 2D 布尔数组，如果该像素与单击的颜色相同，则值为“true”，否则值为“false”。此步骤的要点是将 .getRGB 方法保留在递归方法之外，以期防止出现此错误。

3. 小程序递归搜索用户单击的二维布尔数组，记录 ArrayList 中每个为“true”的相邻点。然后，该方法将其记录的每个点更改为 false 并继续。

4. 小程序将 ArrayList 中存储的每个点绘制为用户选择的颜色。

如果用户在一个小区域内单击，其中只有几千个像素左右的颜色发生了变化，那么上述所有步骤都可以完美地工作。然而，如果用户选择一个大区域（例如大约 360,000 / 小程序窗口的大小），小程序将进入递归阶段，然后输出此错误：

Exception in thread "AWT-EventQueue-1" java.lang.StackOverflowError
 at java.util.ArrayList.add(ArrayList.java:351)
 at paint.recursiveSearch(paint.java:185)
 at paint.recursiveSearch(paint.java:190)
 at paint.recursiveSearch(paint.java:190)
 at paint.recursiveSearch(paint.java:190)
 at paint.recursiveSearch(paint.java:190)
 at paint.recursiveSearch(paint.java:190)
 at paint.recursiveSearch(paint.java:190)  
 (continues for a few pages) 

这是我的递归代码：

public void recursiveSearch(boolean [][] list, Point p){
    if(isValid(p)){
        if(list[(int)p.y][(int)p.x]){
            fillPoints.add(p);
            list[(int)p.y][(int)p.x] = false;

            recursiveSearch(list, new Point(p.x-1,p.y));//Checks to the left
            recursiveSearch(list, new Point(p.x,p.y-1));//Checks above
            recursiveSearch(list, new Point(p.x+1,p.y));//Checks to the right
            recursiveSearch(list, new Point(p.x,p.y+1));//Checks below
            }
        }
    }

有什么方法可以解决像这样的错误？我知道循环永远不会永远持续下去，它只是可能需要很多时间。

Answer 1

你需要的是广度优先搜索。您将有一个“未处理”像素队列。首先，队列由用户单击的一个像素组成。现在，当队列不为空时，重复以下步骤：从队列中取出下一个像素，对其进行处理（绘制为您需要的颜色或其他颜色），并且对于相同颜色的每个相邻未访问像素将其标记为已访问，并且添加到队列中。如果该区域由 360,000 像素组成，那么它应该很快就能运行。

Answer 2

您可以增加 Java 进程的堆栈空间，例如：

java -Xss10m MyProgram

为线程堆栈提供 10 兆。但是，我建议不要这样做，并考虑编写算法的迭代版本，特别是如果递归调用的数量取决于某种用户驱动的行为。

编辑：对于小程序，我认为您无法指定 -X 标志值。

Answer 3

基本问题是您对每个像素检查太多。我建议您在方法中添加一个“level”参数，该参数最初为 0，但在递归调用时递增。然后添加一个初始打印语句，显示当前递归调用的级别。

我想你会惊讶于你的代码有多深！

Answer 4

如果您想处理任意图像大小，那么您将必须以非递归方式重写它。没有其他方法可以保证您的堆栈足够大。

Answer 5

您的算法在纸面上是有意义的，但正如您发现的那样，它的扩展性不佳。

我怀疑任何图形程序都会使用这种方法。

Answer 6

如果您想避免检查窗口上的所有像素，递归将是一个好主意。我建议更改所选像素的颜色，并递归检查是否有任何相邻像素也需要更改，如果没有则返回，依此类推。这样就避免了检查窗口中的每个像素。 （想象一下 800 x 800 像素窗口的情况，您必须填充 4x4 像素区域。检查每个像素就显得有些过分了。）

Answer 7

我根本不明白你为什么要递归。如果您曾经将 list 中的任何点更改回 true，那将是一回事，但显然您没有这样做。那么为什么不直接迭代呢？

事实上，您可能会多次检查每个点，而每个点只检查一次就足够了。

另一个想法：如果我没记错的话，你的算法不会向 fillPoints 向量添加任何点，除非 list[0, 0] == true< /代码>。这是你想要的行为吗？

---

编辑：好的，现在我对你想要做什么有了更好的了解。我建议您查看维基百科页面的洪水填充算法。

Answer 8

从我的快速观察来看。我认为您已经多次遍历这些区域。您应该更新该方法以包含调用不应返回的方向。像这样：

public void recursiveSearch(boolean [][] list, Point p, String directionFrom){
    if(isValid(p)){
        if(list[(int)p.y][(int)p.x]){
            fillPoints.add(p);
            list[(int)p.y][(int)p.x] = false;
            //Add a check for which direction it came from and dont go that way.
            if (string.equals(right)){     
                 recursiveSearch(list, new Point(p.x,p.y-1),down);//Checks above
                 recursiveSearch(list, new Point(p.x+1,p.y),left);//Checks to the right
                 recursiveSearch(list, new Point(p.x,p.y+1),right);//Checks below
            }else if(string.equals(left){
              //... and so on
            }
        }
    }
}

Answer 9

对于大图像来说应该发生这种情况。你不应该使用递归。也许是这样的：

LinkedList<Point> frontier = new ...
frontier.add(starting_point);

while(frontier is not empty)
    point = frontier.removeLast();
    point.state = (point.color == the_color)
    if(point.state==true)
       // expand frontier
       for(neighbor : neighbor_points)
           if(neighbor.visited==false)
               frontier.add(neighbor)
               neighbor.visited=true;