Small Basic – Flood Fill


A recent Small Basic post about filling a region left by Turtle trails revived an old flood fill program I wrote a while ago.

This is the forum thread, turtle small basic.

And this is the program to flood fill regions.

'FloodFill example - for some theory see http://en.wikipedia.org/wiki/Flood_fill
'Draw regions with left mouse button and fill with right mouse button
 
gw = GraphicsWindow.Width
gh = GraphicsWindow.Height
GraphicsWindow.MouseMove = OnMouseMove
GraphicsWindow.MouseDown = OnMouseDown
GraphicsWindow.MouseUp = OnMouseUp
 
mouseMove = 0
mouseDown = 0
rightClick = 0
 
While ("True")
  If (mouseDown = 1 And mouseMove = 1) Then
    xM = GraphicsWindow.MouseX
    yM = GraphicsWindow.MouseY
    GraphicsWindow.DrawLine(xMLast,yMLast,xM,yM)
    xMLast = xM
    yMLast = yM
    mouseMove = 0
  ElseIf (rightClick = 1) Then
    fillRegion()
    rightClick = 0
  EndIf
  Program.Delay(20)
EndWhile
 
Sub fillRegion
  Stack.PushValue("X",xMLast)
  Stack.PushValue("Y",yMLast)
  colOld = GraphicsWindow.GetPixel(xMLast,yMLast)
  colFill = GraphicsWindow.PenColor
  While (Stack.GetCount("X") > 0)
    x = Stack.PopValue("X")
    y = Stack.PopValue("Y")
    If (GraphicsWindow.GetPixel(x,y) <> colFill) Then 'We could have multiple entries in the stack at x,y so only process those we haven't dealt with
      GraphicsWindow.SetPixel(x,y,colFill)
      If (x > 0) Then
        If (GraphicsWindow.GetPixel(x-1,y) = colOld) Then
          Stack.PushValue("X",x-1)
          Stack.PushValue("Y",y)
        EndIf
      EndIf
      If (x < gw-1) Then 'X pixels go from 0 to gw-1
        If (GraphicsWindow.GetPixel(x+1,y) = colOld) Then
          Stack.PushValue("X",x+1)
          Stack.PushValue("Y",y)
        EndIf
      EndIf
      If (y > 0) Then
        If (GraphicsWindow.GetPixel(x,y-1) = colOld) Then
          Stack.PushValue("X",x)
          Stack.PushValue("Y",y-1)
        EndIf
      EndIf
      If (y < gh-1) Then ''Y pixels go from 0 to gh-1
        If (GraphicsWindow.GetPixel(x,y+1) = colOld) Then
          Stack.PushValue("X",x)
          Stack.PushValue("Y",y+1)
        EndIf
      EndIf
    EndIf
  EndWhile
EndSub
 
Sub OnMouseMove
  mouseMove = 1
EndSub
 
Sub OnMouseDown
  GraphicsWindow.PenColor = GraphicsWindow.GetRandomColor()
  xMLast = GraphicsWindow.MouseX
  yMLast = GraphicsWindow.MouseY
  If (Mouse.IsLeftButtonDown) Then
    mouseDown = 1
  ElseIf (Mouse.IsRightButtonDown) Then
    rightClick = 1
  EndIf
EndSub
 
Sub OnMouseUp
  mouseDown = 0
EndSub

 

While this program works fine, it is slow.

I added a new method to the LitDev extension to do a 'flood fill' quicker.  Internally it uses exactly the same method, but doesn't have to load the drawing bitmap and other over-heads for each end every pixel check or change.

The new command is about 100 times faster and replaces fillRegion() with LDGraphicsWindow.FloodFill(GraphicsWindow.MouseX,GraphicsWindow.MouseY,GraphicsWindow.PenColor) in the code sample.

Comments (3)

  1. anonymouscommenter says:

    nice one ..

    <a href:http://makeinindia-modi.blogspot.in>make in india</a>

  2. miskei says:

    GraphicsWindow.Width=800

    GraphicsWindow.Height=600

    GraphicsWindow.PenColor="#000099"

    GraphicsWindow.DrawRectangle(320,220,100,100)

    GraphicsWindow.DrawEllipse(350,250,100,100)

    x=400

    y=300

    if GraphicsWindow.GetPixel(x,y)="#000000" Then

     Stack.PushValue("festx",x)

     Stack.PushValue("festy",y)

     While Stack.GetCount("festx")>0

       x=stack.PopValue("festx")

       y=stack.PopValue("festy")

       GraphicsWindow.SetPixel(x,y,"#000099")

       For i=-1 to 1

         For j=-1 To 1

           if GraphicsWindow.GetPixel(x+i,y+j)="#000000" Then

             Stack.PushValue("festx",x+i)

             Stack.PushValue("festy",y+j)

             GraphicsWindow.SetPixel(x+i,y+j,"#000099")

           EndIf

         EndFor

       EndFor    

     EndWhile

    EndIf

  3. litdev says:

    Nice variant miskei, using a loop to detect neighbour points – since the SetPixel and GetPixel are slow, best to use them as little as possible.  For eample the SetPixel in the For i, For j loops is unnexessary, and we don'tneed to check for some combinations of i and j (e.g. i=j=0 or i=j=1).

    This works just as well I think, but is a bit faster.

        For i=-1 to 1
          For j=-1 To 1
            If (i*j = 0 And i+j <> 0) Then
              if GraphicsWindow.GetPixel(x+i,y+j)="#000000" Then
                Stack.PushValue("festx",x+i)
                Stack.PushValue("festy",y+j)
              EndIf
            EndIf
          EndFor
        EndFor    

Skip to main content