Partilhar via

Small Basic - Flood Fill

  • Artigo

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 https://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

  • Anonymous
    September 26, 2014
    nice one .. <a href:http://makeinindia-modi.blogspot.in>make in india</a>

  • Anonymous
    September 28, 2014
    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

  • Anonymous
    September 29, 2014
    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