java - 递归洪水填充溢出堆栈

Question

我正在研究一种算法来拍摄图像并分离黑白像素 block ，不幸的是，它似乎总是溢出堆栈。这是可疑的类:

package me.dylan.eat;

import java.awt.Point;
import java.awt.Rectangle;
import java.awt.image.BufferedImage;
import java.util.ArrayList;

public class Cell {
    public Point location = new Point(0, 0);

    public Cell(int x, int y) {
        location.x = x;
        location.y = y;
    }

    public void recurseNeighbors(ArrayList<Cell> universe, BufferedImage img) {

        if (!universe.contains(this)) {
            universe.add(this);
            ArrayList<Cell> neighbors = CellUtil.assimilateNeighbors(location, img, new Rectangle(0,0,0,0));
                        //get all neighbors of the same color
            for (Cell c : neighbors) {
                if (!universe.contains(c)) {
                    c.recurseNeighbors(universe, img);
                }
            }
        }
    }
}

编辑:图像是 640x480，是不是太大了？异常在第 23 行抛出。

Answer 1

640x480 太大了。最坏的情况下，您的深度将达到 640*480 = 307200 层。

您有几个选择。选项 1 是不递归地执行此操作，而是维护要处理的像素队列。用第一轮待检查的Cell初始化Queue，然后在队列不为空时，移除前面的项，对其进行处理，并将新的待处理的Cell添加到队列中。

选项 2 是一种迭代方法，例如 here 中描述的方法(其中还描述了基于队列的方法)。

虽然递归似乎是实现洪水填充的自然方法，但实际上它通常会遇到堆栈限制，并且基于迭代或队列的算法运行效率更高。

根据您的目标，您可能还需要考虑一种完全不同的方法，例如并集查找(如果两个单元格颜色相同，则它们相等)，这将为您提供所有黑色和白色的列表一次在 O(log n) 时间内(其中 n 是像素数)对图像进行分组。