Recursive flood-filling overflows stack

Question

I'm working on an algorithm to take images and separate the black and white chunks of pixels, unfortunately, it always seems to overflow the stack. Here's the suspected class:

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);
                }
            }
        }
    }
}

EDIT: The image is 640x480, is that too big? The exception is thrown on line 23.

Answer 1

640x480 is too big. Worst case you'll end up 640*480 = 307200 levels deep.

You have a few options. Option 1 is to not do it recursively, instead maintain a queue of pixels to be processed. Initialize the Queue with the first round of Cells to be checked, then while the queue is not empty, remove the front item, process it, and add new Cells to be processed to the queue.

Option 2 is an iterative approach, such as the ones described here (a queue-based approach is described there as well).

While recursion seems like a natural way to implement a flood fill, in practice it generally hits stack limitations and iterative or queue based algorithms run more efficiently.

Depending on your goal, you may also want to consider an entirely different approach, such as union-find (where two cells are equivalent if they are both the same color), which will give you a list of all black and white groupings in your image in O(log n) time (where n is pixel count), in a single pass.