current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Dismiss
Announcing Stack Overflow Documentation

We started with Q&A. Technical documentation is next, and we need your help.

Whether you're a beginner or an experienced developer, you can contribute.

Sign up and start helping → Learn more about Documentation →
up vote 0 down vote favorite 
private boolean[][] computeMainOutline(boolean[][] outline) {

    int pixelValue[][] = new int [width][height];

    for(int x = 0; x < width; x++)
        for(int y = 0; y < height; y++) 
            if(pixelValue[x][y] == 0) {
            ArrayList<Point2D.Double> path = new ArrayList<>();
            findPath(x, y, outline, pixelValue, path );
            }
    return new boolean[1][1]; // to avoid compilation error
}

private void findPath(int x, int y, boolean[][] outline, int pixelValue [][], ArrayList<Point2D.Double> path ) {
    path.add( new Point2D.Double(x, y));

    if(x > 0 && outline[x - 1][y] == true) // check right
        findPath(x - 1, y, outline, pixelValue, path);
    if(x < width && outline[x + 1][y] == true) // check left
        findPath(x + 1, y, outline, pixelValue, path);
    if(y < height && outline[x][y + 1] == true) // check up
        findPath(x, y + 1, outline, pixelValue, path ); 
    if(y > 0 && outline[x][y - 1] == true) // check down
        findPath(x, y - 1, outline, pixelValue, path);
}

The above method is giving a StackOverflowError and I don't know why.

The method computeMainOutline iterates through the whole outline array and the pixelValue array which are both the same size. If the "value" has not been calculated for a specific coordinate then the findPath function will recursively calculate a path. A path is basically how many "true" array elements are next to each other. The method to calculate the value is not added but my first problem is finding a path.

Moreover if I put a print statement right after path.add( new Point2D.Double( x, y)); to print path.size() inside the recursive method, the size sequence is not consistent it might print(1,2,3,4,2,3,4), why is that?

UPDATE

Corrected it like this, but it will still spark a stack overflow...

private boolean[][] computeMainOutline(boolean[][] outline) {

    int pixelValue[][] = new int [width][height];
    boolean visited[][] = new boolean[width][height];

    for(int x = 0; x < width; x++)
        for(int y = 0; y < height; y++) 
            if(visited[x][y] == false) {
            ArrayList<Point2D.Double> path = new ArrayList<>();
            findPath(x, y, outline, pixelValue, path, visited );
            }
    return new boolean[1][1]; // to avoid compilation error
}

private void findPath(int x, int y, boolean[][] outline, int pixelValue [][], ArrayList<Point2D.Double> path, boolean visited [][] ) {
    path.add( new Point2D.Double(x, y));
    visited[x][y] = true;

    if( x > 0  && visited[x - 1][y] == false && outline[x - 1][y] == true) // check right
        findPath(x - 1, y, outline, pixelValue, path, visited);
    if( x < width - 1 &&visited[x + 1][y] == false && outline[x + 1][y] == true) // check left
        findPath(x + 1, y, outline, pixelValue, path, visited);
    if( y < height - 1 && visited[x][y + 1] == false && outline[x][y + 1] == true) // check up
        findPath(x, y + 1, outline, pixelValue, path, visited ); 
    if( y > 0 && visited[x][y - 1] == false && outline[x][y - 1] == true) // check down
        findPath(x, y - 1, outline, pixelValue, path, visited);
}
share|improve this question
2  
If you don't mark already visited outline elements findPath will recurese infinitely because you will be adding to path same points – csharpfolk Jul 13 at 16:48
up vote 0 down vote

The way you have done your recursion is wrong. While making a recursive method each call puts the previous call on a stack. If you're recursion runs forever there won't be enough room in the stack to go one level deeper causing a Stack Overflow.

Here's the problem. You haven't marked at each time step what has been visited. Imagine this is your grid. The cell in quotes is the (x,y) of our method

"T" F F                  T  F F               "T" F F
 T  F F   (next step)   "T" F F    (next)      T  F F
 T  F F                  T  F F                T  F F

It goes back to the state it's already visited. Hence you'll put infinite method calls in the stack.

Solution

Pass another array to the method with what cells have been visited and as you go to a cell mark it as visited. This would avoid you going back to something you've seen before

share|improve this answer
    
Will the array be changed when it's passed in as an argument? I know it's an object but it seems like it won't change... I should return it, right? – Chris Jul 13 at 18:00
    
@Chris Arrays are not primitives, even if they are arrays of primitives. If you pass an array to a function and that function modifies the contents of the array, the change will be visible outside the function. – Ordous Jul 13 at 18:29
    
@Ordous well... I knew but... it still doesn't explain why I still get an overflow ... please check the update edit. – Chris Jul 13 at 18:41
1  
@Chris You'll find that the exception is only the start of your problems, the method will also return garbage output (unless you are specifically tracing the search steps, rather than want the path). IMHO the best advice here is: make a small example where it fails (3x3 sounds like a good start), think of a limit on stack depth for this (if it visits each cell once, then it should finish 9 cells in 10 recursive calls or less), and breakpoint in your IDE when it hits that stack depth (by keeping a "level" variable). Then analyze each frame, its state, and find out why it was able to get so deep – Ordous Jul 13 at 20:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.