Why do I get java.lang.StackOverflowError when using Flood Fill algorithm?

Question

My program is supposed to fill in a non-regular shape with a color (black and white for the beginning) that I specify in the boundaryFill4 method. Here is the link to myImage.png: https://dl.dropbox.com/u/41007907/myImage.png I use a very simple flood fill algorithm, but it does not work somehow... Here is the FULL code:

  import java.awt.Color;
  import java.awt.Container;
  import java.awt.Image;
  import java.awt.image.BufferedImage;
  import javax.swing.ImageIcon;
  import javax.swing.JFrame;
  import javax.swing.JLabel;

      public class MyPolygon extends JFrame {

private JLabel my;

public MyPolygon() throws InterruptedException {
    createMy();
}

private void createMy() throws InterruptedException {
    Container contentPane = getContentPane();
    contentPane.setBackground(Color.WHITE);
    contentPane.setLayout(null);
    contentPane.setSize(1000, 700);

    my = new JLabel();
    my.setIcon(new ImageIcon("myImage.png"));
    my.setBounds(50, 50, 300, 300);
    contentPane.add(my);

    setSize(1000, 700);
    setVisible(true);
    setLocationRelativeTo(null);

    int fill = 100;
    boundaryFill4(100, 100, fill, 50);
}

// Flood Fill method
public void boundaryFill4(int x, int y, int fill, int boundary) {
    int current;
    current = getPixel(x, y);
    if ((current >= boundary) && (current != fill)) {
        setPixel(x, y, fill);
        boundaryFill4(x + 1, y, fill, boundary);
        boundaryFill4(x - 1, y, fill, boundary);
        boundaryFill4(x, y + 1, fill, boundary);
        boundaryFill4(x, y - 1, fill, boundary);
    }
}

// Getting the color integer at specified point(x, y)
private int getPixel(int x, int y) {
    Image img = ((ImageIcon) my.getIcon()).getImage();
    BufferedImage buffered = new BufferedImage(img.getWidth(null),
            img.getHeight(null), BufferedImage.TYPE_INT_ARGB);
    buffered.getGraphics().drawImage(img, 0, 0, null);
    Color c = new Color(buffered.getRGB(x, y));
    int current = buffered.getRGB(x, y);
    return current;
}

// Setting the color integer to a specified point(x, y)
private void setPixel(int x, int y, int fill) {
    Image img = ((ImageIcon) my.getIcon()).getImage();
    BufferedImage buffered = new BufferedImage(img.getWidth(null),
            img.getHeight(null), BufferedImage.TYPE_INT_ARGB);
    buffered.getGraphics().drawImage(img, 0, 0, null);
    int red = fill;
    int green = fill;
    int blue = fill;
    Color c = new Color(buffered.getRGB(x, y));
    c = new Color(red, green, blue);
    buffered.setRGB(x, y, c.getRGB());
}

// Main method
public static void main(String args[]) throws InterruptedException {
    MyPolygon my = new MyPolygon();
    my.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}
}

Why do I get StackOverflow error? How can I correct for it so that my code works?

Looks like `boundaryFill4` causes an infinite loop. Its not so hard to debug and find the answer on your own... — BobTheBuilder, Apr 09 '13 at 08:31
possible duplicate of [What is a stack overflow error?](http://stackoverflow.com/questions/214741/what-is-a-stack-overflow-error) — fglez, Apr 10 '13 at 09:25

score 3 · Answer 1 · edited May 23 '17 at 11:56

3

You could try to transform your recursive approach (boundaryFill4 calling itself) to a non-recursive one. This way the JVM stack would not overflow.

Another option would be to increase the size of the stack -- see What is the maximum depth of the java call stack?

edited May 23 '17 at 11:56

Community

1
1

answered Apr 09 '13 at 08:32

orique

1,295
1
27
36

what do you mean by non recursive. Do you mean I should separate each section of the image as a separate .png file? If yes, I have done it...it works fine... I wanted to test a flood fill method – Buras Apr 09 '13 at 08:41
I mean that you are using recursion which is prone to consume the stack of a machine (in this case, the JVM). You could try to rewrite your code to use iteration instead, but also consider the other answers. See this: http://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration – orique Apr 09 '13 at 08:46

score 2 · Accepted Answer · answered Apr 09 '13 at 08:32

2

StackOverflowException means, that your recursion is too deep for your memory or does not end. Try on a smaller Image. When this does not solves the problem there is something wrong with your recursion-end-condition. (Does setPixel() and getPixel really change the Image? Write a JUnitTest)

Also you really should simplify your setPixel and getPixel methods. They are too complex. For every Pixel you set or get you create a new BufferedImage-Instance and then dispose it after setting ONE pixel. You can store and reuse the BufferedImage.

answered Apr 09 '13 at 08:32

MaPePeR

931
9
18

One problem is that I do not even see any changes is color. The program runs for the first 10 seconds just fine and only then will it get stuck...so my point is I must be able to see at least any changes in color during those 10 seconds. And I do not see any? – Buras Apr 09 '13 at 08:40
Ok, the problem is very easy: you are creating a copy of your Icon(as BufferedImage). Then you modify the copy, but never write the changes back to your Icon. Also don't expect to see the Image modify, even when you write the changes back, because the changes get executed in the same thread and the Window will not update until all changes to the image have been made. – MaPePeR Apr 09 '13 at 08:45
Previously I have been doing it without floodFill algorithm, i.e. by using a combined set/getter method. I think I am writing the changes in the setter: buffered.serRGB...Am I missing something. Would you kindly make corrections to how I should write changes back to my image. – Buras Apr 09 '13 at 08:52
There is no magic connection between the BufferedImage and the IconImage. Imagine an artist: He has an image. Now he wants to draw a new Pixel to the Image. So he takes a blank canvas(BufferedImage, same size) and starts to copy(drawImage) the whole image to this new canvas. Then he draws the Pixel he wanted to change(setRGB). After that is done he throws the new changed canvas away, because he is done drawing the pixel. For the next pixel he takes the old image, copy s everything to a new canvas .... and so on. That is what you are doing in setPixel() – MaPePeR Apr 09 '13 at 09:02
Thank you very much. I completely understand the logic now. However, I have been trying to correct my code, but I failed. I would be really appreciated if you could correct my code. Thank You. – Buras Apr 09 '13 at 14:05
Dear MaPePeR I took your advice but unfortunately I was not able to correct my code. PLEASE, help me. This is a "one class" program. Can you please, make corrections to it? – Buras Apr 10 '13 at 04:40

score 1 · Answer 3 · answered Apr 09 '13 at 08:32

1

You should debug your boundaryFill4 method: it is where an infinite loop occurs. Use simple cases to track how the method reacts.

Furthermore, you should avoid to write / read the image at each iteration of the recursion. Instantiate a proper and efficient data structure representing the image at the beginning, then modify this data structure and when the algorithm ends, write the results as a image.

answered Apr 09 '13 at 08:32

Jean Logeart

52,687
11
83
118

One problem is that I do not even see any changes is color during the first 10 seconds when the program works fine. It will get stuck only after those 10 seconds...so my point is I must be able to see at least any changes in color during those 10 seconds. And I do not see any? – Buras Apr 09 '13 at 08:43

Why do I get java.lang.StackOverflowError when using Flood Fill algorithm?

3 Answers3