Non-recursive Flood-Fill algorithm causes OutOfMemoryError

Question

I'm writing a small drawing application. I'm trying to make a 'bucket fill' tool using a non-recursive implementation of the flood-fill algorithm.

However, if the user uses this tool a few times in a row with too short time intervals, it causes an OutOfMemoryError in Java.

I would like to know how I can optimize my implementation so this error won't occur.

public void floodFill(int x, int y, Color targetColor, Color replacementColor) {

    LinkedList<Point> stack = new LinkedList<Point>();

    stack.add(new Point(x,y)); // adding the point where the mouse was clicked.

    Point temp;
    while( !stack.isEmpty() ){

        temp = stack.pop();

        int pixelColorRGB = drawingArea.getRGB( (int)temp.getX(), (int)temp.getY() );
        Color pixelColor = new Color(pixelColorRGB, true);

        if(pixelColor.equals(targetColor)){

            g.setColor(replacementColor);
            g.fillRect((int)temp.getX(), (int)temp.getY(), 1, 1);

            if(this.contains((int) temp.getX() - 1, (int) temp.getY()))
                stack.add( new Point( (int) temp.getX() - 1, (int) temp.getY() ) );

            if(this.contains((int) temp.getX() + 1, (int) temp.getY()))
                stack.add( new Point( (int) temp.getX() + 1, (int) temp.getY() ) );

            if(this.contains((int) temp.getX(), (int) temp.getY() - 1))
                stack.add( new Point( (int) temp.getX(), (int) temp.getY() - 1 ) );

            if(this.contains((int) temp.getX(), (int) temp.getY() + 1))
                stack.add( new Point( (int) temp.getX(), (int) temp.getY() + 1 ) );

        }

    }

}

Thank you

ozma · Accepted Answer · 2014-02-24T05:41:20.827

2

edit: according to comment by korhner (which is totally right). only add to stack if the color is different then target color.

original post: Adding all pixels on screen to the stack should be fine. I think the problem might be you have overlapping points.

In a similar way of a recursive solution you must know which point is already in the stack and not adding it again.

~~You might need to use additional data structure for that.~~

edited Feb 24 '14 at 05:41

answered Feb 22 '14 at 15:08

ozma

1,633
1
20
28

So if I'll add all pixels that have already been visited to a `Set` and check the `Set` each time before adding a pixel to the stack in order to see if it's already there, do you think it will solve the problem? – Aviv Cohn Feb 22 '14 at 15:11
Tried it, it solved the problem :D Simply made a `Set` to store all the pixels already visited, so I don't add duplicates of them to the stack. Thanks a lot :) – Aviv Cohn Feb 22 '14 at 15:23
1

Couldn't you simple add to stack only if the color is same as starting color? It would be a lot more efficient that way as you wouldn't need additional datastructures. – korhner Feb 22 '14 at 20:30

Non-recursive Flood-Fill algorithm causes OutOfMemoryError

1 Answers1