Java Inconsistent Stack Overflow

Question

I've been working on my final project for my AP Computer Science class and am modifying the AP Picture Lab to do it (all of the source code is available at https://github.com/jvperrin/ap-picture-lab).

For one portion of my project, I implement a depth first search to get adjacent pixels to the target pixel that are black. However, it seems like every other time I run the program I either get a stack overflow error or the program works perfectly. Is there a reason I'm getting this problem? Does it have to do with how Java stores stack memory?

Error Message

Exception in thread "main" java.lang.StackOverflowError
at java.awt.image.ComponentColorModel.getRGB(Unknown Source)
at java.awt.image.BufferedImage.getRGB(Unknown Source)
at SimplePicture.getBasicPixel(SimplePicture.java:300)
at Pixel.getAlpha(Pixel.java:86)
at Pixel.setBlue(Pixel.java:296)
at ZPicture.depthFirstSearch(ZPicture.java:50)
at ZPicture.depthFirstSearch(ZPicture.java:73)
at ZPicture.depthFirstSearch(ZPicture.java:73)
at ZPicture.depthFirstSearch(ZPicture.java:73)
....

ZPicture Class:

    import java.util.ArrayList;
import java.util.Stack;

public class ZPicture extends SimplePicture {
    protected Pixel[][] pixels;
    protected boolean[][] checked;
    protected Stack<Pixel> stack;
    // a multidimensional array list?!?!
    //letters is the pixels in letters
    protected ArrayList<ArrayList<Pixel>> letters;
    //chars are the key points in letters
    protected ArrayList<ZChar> chars;
    protected final int BLACK = 30;
    protected final int SIZE = 10;

    public ZPicture(String fileName) {
        super(fileName);
        pixels = this.getPixels2D();
        checked = new boolean[pixels.length][pixels[0].length];
        stack = new Stack<Pixel>();
        letters = new ArrayList<ArrayList<Pixel>>();
        letters.add(new ArrayList<Pixel>());
        chars = new ArrayList<ZChar>();
    }

    // Z METHODS
    public void findLetters() {
        // Y
        for (int row = 0; row < pixels.length; row++) {
            // X
            for (int col = 0; col < pixels[0].length; col++) {
                Pixel p = pixels[row][col];
                if (isBlack(p)) {
                    stack.push(p);
                    depthFirstSearch();
                }
            }
        }
        sortLetters();
        findPoints();
        printLetters();
    }

    protected void depthFirstSearch() {
        // base case - if stack has elements
        if (!stack.isEmpty()) {
            Pixel p = stack.pop();
            checked[p.getY()][p.getX()] = true;
            letters.get(letters.size() - 1).add(p);
            p.setBlue(255);

            // get surrounding pixels
            Pixel pt = pixels[p.getY() - 1][p.getX()];
            Pixel pr = pixels[p.getY()][p.getX() + 1];
            Pixel pb = pixels[p.getY() + 1][p.getX()];
            Pixel pl = pixels[p.getY()][p.getX() - 1];

            // if pixel is black and unchecked, add to stack
            if (isBlack(pt)) {
                stack.push(pt);
            }
            if (isBlack(pr)) {
                stack.push(pr);
            }
            if (isBlack(pb)) {
                stack.push(pb);
            }
            if (isBlack(pl)) {
                stack.push(pl);
            }

            // recursion
            depthFirstSearch();
        } else {
            System.out.println("New Letter: " + letters.size());
            // note: the final letter is always empty
            letters.add(new ArrayList<Pixel>());
        }
    }

    protected boolean isBlack(Pixel p) {
        if (p.getBlue() < BLACK && p.getRed() < BLACK && p.getGreen() < BLACK
                && checked[p.getY()][p.getX()] == false) {
            return true;
        }
        return false;
    }

}

(I have a main method elsewhere that instantiates a ZPicture and calls findletters).

You are potentially add 4 to your stack but only pop`ing one. — Scary Wombat
– Scary Wombat, Commented May 8, 2015 at 2:18
The rest get popped once I've stopped adding pixels and it's how I learned to do depth first searches. — Oblivionkey3
– Oblivionkey3, Commented May 8, 2015 at 2:20
when you p.setBlue(255); in your method your not setting that pixel back into the pixels[] so there will always be the black pixel resulting in StackOverFlow — JRowan
– JRowan, Commented May 8, 2015 at 2:21
I believe calling p.setBlue(255); modifies the pixel that's stored in the array - also, if this was the problem, do you know why I only get the error every few times I run the program then? — Oblivionkey3
– Oblivionkey3, Commented May 8, 2015 at 2:23
p is just a local variable to the method it in no way has anything to do with pixels[][], i couldnt tell you why it happens only sometimes — JRowan
– JRowan, Commented May 8, 2015 at 2:25

user4668606 · Accepted Answer · 2015-05-08 02:22:21Z

3

The StackOverFlowError is caused by the recursive call (which isn't even necassary). The cause for the error is pretty simple: for every element in the stack, the algorithm makes another recursive call. If the area of black pixels is large enough, the number of adjacent black pixels will exceed the stack-size, causing the StackOverFlowError. Good news: the recursive call doesn't make any sense here, since you already use a stack. Simply remove it, and the code should work like a charm.

answered May 8, 2015 at 2:22

user4668606

Sign up to request clarification or add additional context in comments.

1 Comment

Oblivionkey3 Over a year ago

I just changed things to a while loop and it all works now, thanks!

Collectives™ on Stack Overflow

Java Inconsistent Stack Overflow

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related