Recursive Flood Fill Error

[BenRaam]

When I try to runt the attached code, no errors appear in the program, yet the app stops working and the code stops running, nothing comes up as an error, or a suggestion to fix the issue, I'm not sure what the error is, as the code seems like it should work fine.
Any suggestions would be more than welcome, as this is for my A2 Computing coursework, and the deadline is next week!
Thanks

 Sub Globals
   Dim bm As Bitmap
   Dim col As Int
   Dim new_color As Int
   Dim old_color As Int
End Sub


Sub Panel1_Touch (Action As Int, X As Float, Y As Float)
Case "fill"
            new_color = pencolor
            old_color = Paper.Bitmap.GetPixel(X, Y)
               If old_color <> new_color Then
                  fill(X,Y)
                     
                  Activity.Invalidate
               End If
            End Select
         End If
      End Sub
 
    Public Sub fill(x As Int, y As Int)
        'Dim old_color As Color = bm.GetPixel(x, y)
      Paper.DrawLine(x, y, x, y, new_color, 1dip)
           col = Paper.bitmap.GetPixel(x - 1, y)
           If col = old_color Then
               fill(x-1, y)
           End If
           col = Paper.bitmap.GetPixel(x + 1, y)
           If col = old_color Then
               fill(x+1, y)
           End If
          col = Paper.bitmap.GetPixel(x, y - 1)
           If col = old_color Then
               fill(x, y-1)
           End If
           col = Paper.bitmap.GetPixel(x, y + 1)
           If col = old_color Then
               fill(x, y+1)
         End If
        
    End Sub

 

[Erel]

There must be an error in the logs.

 

[BenRaam]

There must be an error in the logs.

Ok, I trawled through the log files , and prior to the program crash, it come up with 'FATAL ERROR, stack overflow' so does this mean there's a default stack setting like it visual studio? Or is there a way to edit the base stack size in b4a?

 

[Erel]

There is no default stack setting. It is defined by the OS. Make sure that the recursive calls are not endless.

 

[klaus]

You should try to fill a small area.
Then set a breakpoint at the beginning of the fill routine and look at the evolution of the x and y variables and you'll see that you are in an infinit loop.

Best regards.

 

[Mansie]

Did you manage to resolve this? I'd be interested to see the working recursive flood fill example.

I've had issues with functions which are called from within themselves, like in your recursive example.

Mansie

 

[Erel]

I've had issues with functions which are called from within themselves, like in your recursive example.

There are no issues with recursive functions. If you think that you did encounter such an issue then please post the code.

 

[PenguinHero]

Hi All,

I was looking through the forums for a Flood Fill routine and found this, but it doesn't seem to work.

Could the reason that the overflow was occurring be due to the DrawLine being used to do the update not actually updating the bitmap that the GetPixel is sourcing its information from, so that from the routines view it was never doing any updates as the colour information from the GetPixel would always be the old colour?

If so, can anyone suggest a way of correcting this? So that the source of the GetPixel and the update (via DrawLine or an alternative) are the same thing?

Edit: Okay, I have found that doing the reading and writing using a mutable bitmap works. If I write (using the canvas DrawPoint) and read the same X,Y location back again the colour has changed.
But when I incorporate this into an updated version of the code above, even with checking that it is not trying to read beyond the edge of the canvas, it still gives the stack overflow. Is there an option to increase the stack size, like some other programming languages have? Any other ideas?

Edit2: I dug a bit deeper and added a counter to the fill routine, and wrote it to the log. It only gets to 280 before it fails. Doing some googling on the Android stack size found the following:

API 3 (Android 1.5) = 8KB
API 4-10 (Android 1.6 - Android 2.3.7) = 12KB
API 14-17 (Android 4.0 - Android 4.2.2) = 16KB

There is no way even 16KB is ever going to be enough for this kind of recursion, so in hindsight it no surprise that the overflow is happening. I'll see if I can find a non-recursive algorithm for flood fill.

 

[PenguinHero]

Hi All,

I found a non-recursive algorithm for Flood Fill that had some sample Delphi (I think) code.
I was able to convert it to B4A without too many problems. The use of GOTO commands made me have to use a loop, but otherwise it wasn't too bad.

Anyway, it works, but it would be a no surprise to anyone that knows about recursion Vs non-recursion that it is very slow.
I use a test image which has a rectangle that is roughly 25% of the screen, and it takes around 6 or 7 seconds to fill it on my kindle fire.

I have attached the project if anyone is interested. Feel free to use the code as you see fit. I have included information in the comments about where I found the algorithm/code, and a few other things, including an updated version of the recursive code found at the top of this thread. I expect the recursive version would work if the Android OS had a stack size larger than 16K.

Maybe someone more knowledgeable than me can speed it up - if so please let me know.
Note that it has a bit of hard coding for the screen/image size and the border/fill colours. In the event that you want to use the code you need to make those items dynamic. Should be an easy change.

If anyone knows of a faster non-recursive algorithm then please let me know that too, and I'll have another go using that. I'm still looking...


Regards,
PenguinHero.