Small Basic - Flood Fill

  • Article

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.