p2p.wrox.com Forums (http://p2p.wrox.com/index.php)
-   VB.NET 2002/2003 Basics (http://p2p.wrox.com/forumdisplay.php?f=76)
-   -   Recursive algorithm causing stack overflow (http://p2p.wrox.com/showthread.php?t=31099)

 rharris July 1st, 2005 09:48 PM

Recursive algorithm causing stack overflow

Hi all,

I have an area fill routine that colors regions that a user clicks on (i.e. analogous to Microsoft paint's flood fill) The recursive routine works well for relatively small areas, but causes stack overflow for larger areas. See routine below:

Private Function boundaryFill2(ByVal x As Integer, _
ByVal y As Integer, ByVal fill As System.Drawing.Color, _
ByVal old As System.Drawing.Color)
Dim current As System.Drawing.Color
If ((x <= 400) Or (x >= Me.Width - 25)) Then
Exit Function
ElseIf ((y <= 38) Or (y >= 300)) Then
Exit Function
End If
current = m_PrintBitmap.GetPixel(x, y)
If current.ToArgb.Equals(old.ToArgb) Then
m_PrintBitmap.SetPixel(x, y, fill)
PixelRecord(x, y, count) = 1
boundaryFill2(x + 1, y, fill, old)
boundaryFill2(x, y + 1, fill, old)
boundaryFill2(x - 1, y, fill, old)
boundaryFill2(x, y - 1, fill, old)
End If
End Function

Is there a way to increase stack size on compile? If so, how. Recursion seems like the best way to go, so I would like to stick with it. That is, unless anyone can convince me otherwise.

Any help will be greatly appreciated!

-Rob

 katsarosj July 4th, 2005 10:59 AM

 katsarosj July 6th, 2005 08:48 AM

Are you trying to fill a square, rectangle, etc.? If so, GDI+ already has "Fill" methods for these. Some of these include FillClosedCurve, FillEllipse, FillPath, FillRegion, FillRectangle - just to name a few.

J

 rharris July 6th, 2005 06:52 PM

The region is general, defined by any number of curves. An example region could be defined as the space between the curves:

f(x)=sin(x)
f(x)=0
g(y)=0
g(y)=1

The user defines region as above, then clicks inside region. The recursive algorithm colors pixel-by-pixel, until entire closed region has been colored. The algorithm works great, just need to know how to allocate increased stack space so stack will not overflow during runtime. I believe this can be done in complile step, but I cannot find detailed examples of this on web.

-Rob

 katsarosj July 6th, 2005 07:10 PM

So are you trying to fill the curve of the sine wave to join it with the x axis? I am trying to get a feel for what you are doing.

I have read somewhere that there is a bug in some of the .Net algorithms that cause a stack overflow error when using recursive procedures that are implemented a certain way (although I can't remember where I read it).

 rharris July 6th, 2005 08:18 PM

Yes, the example I gave would be to fill the space between a sine wave and the x-axis, but it will work for any region. The user clicks inside a closed region, whereby the coordinates of the click are sent to a recusive routine. Basically the routine tests the pixel color of the point given, and colors it blue if it is grey. It then tells the neighboring pixels (above and below that pixel) to color themselves blue if they are grey. The coloring is carried out until the blue boundary curves(i.e. f(x)=sin(x),f(x)=0,etc) are reached. So, each call to the function can result in 4 additional function calls to itself (if all neighboring pixels need coloring). For smaller regions this is no problem, but for larger regions the code bombs with a stack overflow exception.

-Rob

 rharris July 6th, 2005 08:24 PM

By the way, exception is stack-overflow in system.drawing.dll

-Rob

 katsarosj July 7th, 2005 09:51 AM

Well, I can't really help you with the error, but as I stated before, there is already a FillPath method that could probably achieve what you want (with a little investigation). Here is an example:

Dim path As New GraphicsPath
path.StartFigure()
path.AddArc(100, 100, 200, 150, 195, 150)
path.CloseFigure()
e.Graphics.FillPath(Brushes.Blue, path)
e.Graphics.DrawPath(Pens.Black, path)

This creates a semi-circle at the specified points and then fills that in with a blue color fill. This is placed in the forms Paint event and you will have to import System.Drawing.Drawing2D. You can add additional arcs, lines, etc. if your sine wave jumps around prior to drawing it.

J

 rharris July 7th, 2005 12:48 PM