StackOverflowException

[Mehdi Ghiasi]

Hi! I am using this BackTrack procedure that Fills a map.

Private Sub Fill(ByVal i As Integer, ByVal j As Integer)
If (i < 1) Or (j < 1) Or (i > FillM.Width) Or (j > FillM.Height) Then
Exit Sub
End If
If FillM.Pixel(i, j) = 1 Then
FillM.Pixel(i, j) = -1

        Fill(i, j - 1)
        Fill(i, j + 1)
        Fill(i - 1, j - 1)
        Fill(i - 1, j)
        Fill(i - 1, j + 1)
        Fill(i + 1, j)
        Fill(i + 1, j - 1)
        Fill(i + 1, j + 1)
    End If
End Sub

When The Map has a few pixels that have value 1, It works correctly. but when the map has many pixels that has value 1, It cause an StackOverflowException. How Can I resolve this problem and why .Net Framework 3.5 throw this invalid Exception???? :confused:

Regards. Mehdi Ghiasi

[Luc Pattyn]

Mehdi Ghiasi wrote:

why .Net Framework 3.5 throw this invalid Exception

There probably isn't anything invalid here, your algorithm is such that a lot of recursion may occur. Here is an example: assume an N*N map, all elements are -1 except for row 2, there they are all +1. Now somehow you start at (2,N-1), the rightmost +1. Your Fill will call Fill(i, j - 1), which is +1 again, so it calls Fill(i, j - 1) which is +1 again, etc. You are basically pushing all elements of that row onto the stack, resulting in a nesting of N and that has used one dimension only. There will be patterns that put big chunks of your N*N map on the stack, therefore it is either a bad algorithm or a bad implementation. A better algorithm would perform more work in the function itself, resulting in fewer stack pushes. You really need a stack push only when there are multiple ways to go and you can proceed on only one of them right away, then the others need pushed somehow. But then, a width first approach would be better than a depth first one. Have a look at the "A* algorithm", or search for flood fill. :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use < PRE > tags for code snippets, it preserves indentation, and improves readability.

[supercat9]

It may be interesting and illustrative to adapt the algorithm to use a queue rather than a stack. If you do that, you will observe the behavior looks as though the filled area "spreads". People who remember BASICA from way back when may recognize the queue-fill behavior as being something like what BASICA did, except that it scanned horizontal line segments directly rather than enqueueing each pixel thereon. Note that the total number of queue entries required will be proportional to the smaller dimension of the area being filled, whereas a stack-based implementation will require stack depth proportional to the number of pixels.

[Luc Pattyn]

Queue-Linear Flood Fill: A Fast Flood Fill Algorithm[^] just happens to be the featured article right now! :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use < PRE > tags for code snippets, it preserves indentation, and improves readability.