Area fill algorithm: crayons and coloring book


Kids know how to use crayons and a  coloring book. How do you write such a program?


 


In my last post (Which pixels do you turn on when you draw a line?) I showed how to draw a line. Now suppose you have some lines or shapes already drawn. How would you write code to fill in an area bounded by the drawn pixels?


 


IOW, imagine you’ve drawn a circle. You want to fill the circle with a color. Right click inside. What code should run? What if the figure were more complex, like a large block “W” or a curled up snake.


 


More formally: Given an array of pixels that represents the outline of a shape, and a point’s  x,y coordinate within that shape, how would you area fill that shape?


 


Perhaps you could write some code that will check all pixels to the East, North, West, South until it reached a pixel that was already painted. Then what?


 


What sort of algorithm and data structure would you use?


 


 


Below are C# and VB versions of a simple implementation that isn’t very efficient, but is quite simple.


 


The code is identical to the last post (the drawing parts) except for the areas delimited by “AREA”. This makes it easier for you to cut/paste the code.


 


Start Visual Studio 2008


Choose  File->New->Project->C# or VB->Windows Forms Application.


Choose View->Code


 


Paste in the VB or C# version of the code below, hit F5 to run it. Draw a shape, right click to fill.


 


How would you improve it? Why isn’t it efficient?


 


Try making the form bigger and paint more pixels. What happens?


 


Clue:  look at the source code for MineSweeper that I wrote to take advantage of the (then) new feature Collections. It’s part of the Task Pane for Visual Foxpro 9.0


 


See also:


Remove double spaces from pasted code samples in blog


 


 


<C# Sample>


#define AREA 


using System;


using System.Collections.Generic;


using System.ComponentModel;


using System.Data;


using System.Drawing;


using System.Linq;


using System.Text;


using System.Windows.Forms;


 


namespace WindowsFormsApplication1


{


    public partial class Form1 : System.Windows.Forms.Form


    {


        Size m_numCells = new Size(350, 200);// we’ll use an array of Cells


        Boolean[,] m_cells; // the array of cells: whether they’ve been drawn or not


        Size m_cellSize = new Size(8, 8);  // cell height & width


        Size m_Offset = new Size(0, 0);


        bool m_MouseDown = false;


        Button btnErase;


        Point? m_PtOld;


        SolidBrush m_brushMouse = new SolidBrush(Color.Red);


        SolidBrush m_brushGenerated = new SolidBrush(Color.Black);


        delegate bool DrawCellDelegate(Point ptcell, Brush br);


        Graphics m_oGraphics;


        public Form1()


        {


            this.Load += new EventHandler(this.Loaded);


        }


        void Loaded(Object o, EventArgs e)


        {


            this.Width = 600;


            this.Height = 400;


            this.btnErase = new Button();


            this.btnErase.Text = “&Erase”;


            this.btnErase.Click += new EventHandler(this.btnErase_Click);


            this.Controls.Add(this.btnErase);


            this.BackColor = Color.White;


            btnErase_Click(null, null);


        }


        void btnErase_Click(object sender, System.EventArgs e)


        {


            m_oGraphics = Graphics.FromHwnd(this.Handle);


            m_numCells.Width = this.Width / m_cellSize.Width;


            m_numCells.Height = this.Height / m_cellSize.Height;


            m_cells = new Boolean[m_numCells.Width, m_numCells.Height];


            m_oGraphics.FillRectangle(Brushes.White, new Rectangle(0, 0, this.Width, this.Height));


        }


        Point PointToCell(Point p1)


        {


            Point ptcell = new Point(


            (p1.X – m_Offset.Width) / m_cellSize.Width,


            (p1.Y – m_Offset.Height) / m_cellSize.Height);


            return ptcell;


        }


        protected override void OnMouseDown(MouseEventArgs e)


        {


            if (e.Button == MouseButtons.Left)


            {


                m_MouseDown = true;


                m_PtOld = new Point(e.X, e.Y);


                CheckMouseDown(e);


            }


#if AREA


            else


            {


                AreaFill(PointToCell(new Point(e.X, e.Y)));


            }


#endif


        }


        protected override void OnMouseMove(MouseEventArgs e)


        {


            if (m_MouseDown)


            {


                CheckMouseDown(e);


            }


        }


        protected override void OnMouseUp(MouseEventArgs e)


        {


            m_MouseDown = false;


        }


        void CheckMouseDown(MouseEventArgs e)


        {


            Point ptMouse = new Point(e.X, e.Y);


            Point ptcell = PointToCell(ptMouse);


            if (ptcell.X >= 0 && ptcell.X < m_numCells.Width &&


                ptcell.Y >= 0 && ptcell.Y < m_numCells.Height)


            {


                DrawLineOfCells(PointToCell(m_PtOld.Value), ptcell, new DrawCellDelegate(DrawACell));


                m_PtOld = ptMouse;


            }


        }


 


        bool DrawACell(Point ptcell, Brush br)


        {


            bool fDidDraw = false;


            if (!m_cells[ptcell.X, ptcell.Y]) // if not drawn already


            {


                m_cells[ptcell.X, ptcell.Y] = true;


                //*


                m_oGraphics.FillRectangle(br,


                    m_Offset.Width + ptcell.X * m_cellSize.Width,


                    m_Offset.Height + ptcell.Y * m_cellSize.Height,


                    m_cellSize.Width,


                    m_cellSize.Height);


                /*/


                 g.DrawRectangle(new Pen(Color.Blue,1),


                    m_Offset.Width + ptcell.X * m_cellSize.Width,


                    m_Offset.Height + ptcell.Y * m_cellSize.Height,


                    m_cellSize.Width,


                    m_cellSize.Height);


                


                  //*/


                fDidDraw = true;


            }


            return fDidDraw;


        }


        void DrawLineOfCells(Point p1, Point p2, DrawCellDelegate drawit)


        {


            // http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm


            Brush br =  m_brushMouse;


            int x0 = p1.X;


            int y0 = p1.Y;


            int x1 = p2.X;


            int y1 = p2.Y;


            int x, cx, deltax, xstep,


                y, cy, deltay, ystep,


                 error;


            bool st;


 


            // find largest delta for pixel steps


            st = (Math.Abs(y1 – y0) > Math.Abs(x1 – x0));


 


            // if deltay > deltax then swap x,y


            if (st)


            {


                x0 ^= y0; y0 ^= x0; x0 ^= y0; // swap(x0, y0);


                x1 ^= y1; y1 ^= x1; x1 ^= y1; // swap(x1, y1);


            }


 


            deltax = Math.Abs(x1 – x0);


            deltay = Math.Abs(y1 – y0);


            error = (deltax / 2);


            y = y0;


 


            if (x0 > x1) { xstep = -1; }


            else { xstep = 1; }


 


            if (y0 > y1) { ystep = -1; }


            else { ystep = 1; }


 


            for (x = x0; (x != (x1 + xstep)); x += xstep)


            {


                cx = x; cy = y; // copy of x, copy of y


 


                // if x,y swapped above, swap them back now


                if (st)


                {


                    cx ^= cy; cy ^= cx; cx ^= cy;


                }


                if (drawit(new Point(cx, cy), br))


                {


                    br = m_brushGenerated;


                }


 


                error -= deltay; // converge toward end of line


                if (error < 0)


                { // not done yet


                    y += ystep;


                    error += deltax;


                }


            }


        }


 


#if AREA


 


        SolidBrush m_brushFill = new SolidBrush(Color.Blue);


        Color m_oColor = Color.Black;


        /*


        /*/


                void AreaFill(Point ptcell)


                {


                    if (ptcell.X >= 0 && ptcell.X < m_numCells.Width)


                    {


                        if (ptcell.Y >= 0 && ptcell.Y < m_numCells.Height)


                        {


        //                    System.Threading.Thread.Sleep(100);


                            if (DrawACell(ptcell, m_brushFill))


                            {


                                m_oColor = Color.FromArgb((int)(((((uint)m_oColor.ToArgb() & 0xffffff) + 140) & 0xffffff) | 0xff000000));


                                m_brushFill = new SolidBrush(m_oColor);


                                AreaFill(new Point(ptcell.X – 1, ptcell.Y));


                                AreaFill(new Point(ptcell.X + 1, ptcell.Y));


                                AreaFill(new Point(ptcell.X, ptcell.Y + 1));


                                AreaFill(new Point(ptcell.X, ptcell.Y – 1));


                            }


                        }


                    }


                }


        //*/


#endif


    }


}


 


</C# Sample>


 


<VB Sample>


#Const AREA = True


Public Class Form1


    Dim m_numCells = New Size(350, 300) ‘ we’ll use an array of cells


    Dim m_cells(,) As Boolean   ‘ the array of cells: whether they’ve been drawn or not


    Dim m_cellSize = New Size(8, 8) ‘ cell size & width


    Dim m_Offset = New Size(0, 0)


    Dim m_MouseDown = False


    Dim WithEvents btnErase As Button


    Dim m_PtOld As Point?


    Dim m_brushGenerated = New SolidBrush(Color.Black)


    Dim m_brushMouse = New SolidBrush(Color.Red)


    Dim m_oGraphics As Graphics


    Delegate Function DrawCellDelegate(ByVal ptCell As Point, ByVal br As Brush) As Boolean


 


    Sub Form_Load() Handles Me.Load


        Me.Width = 600


        Me.Height = 400


        Me.btnErase = New Button()


        Me.btnErase.Text = “&Erase”


        Me.Controls.Add(Me.btnErase)


        Me.BackColor = Color.White


        btnErase_Click()


 


    End Sub


    Sub btnErase_Click() Handles btnErase.Click


        m_oGraphics = Graphics.FromHwnd(Me.Handle)


        m_numCells.Width = Me.Width / m_cellSize.Width


        m_numCells.Height = Me.Height / m_cellSize.Height


        ReDim m_cells(m_numCells.Width, m_numCells.Height)


        m_oGraphics.FillRectangle(Brushes.White, New Rectangle(0, 0, Me.Width, Me.Height))


 


    End Sub


    Function PointToCell(ByVal p1 As Point) As Point


        Dim ptcell = New Point( _


            (p1.X – m_Offset.Width) / m_cellSize.Width, _


            (p1.Y – m_Offset.Height) / m_cellSize.Height)


        Return ptcell


 


    End Function


    Protected Overrides Sub OnMouseDown(ByVal e As System.Windows.Forms.MouseEventArgs)


        If e.Button = Windows.Forms.MouseButtons.Left Then


            m_MouseDown = True


            m_PtOld = New Point(e.X, e.Y)


            CheckMouseDown(e)


#If AREA Then


        Else


            AreaFill(PointToCell(New Point(e.X, e.Y)))


#End If


        End If


    End Sub


    Protected Overrides Sub OnMouseMove(ByVal e As System.Windows.Forms.MouseEventArgs)


        If m_MouseDown Then


            CheckMouseDown(e)


        End If


    End Sub


    Protected Overrides Sub OnMouseUp(ByVal e As System.Windows.Forms.MouseEventArgs)


        m_MouseDown = False


    End Sub


    Sub CheckMouseDown(ByVal e As MouseEventArgs)


        Dim ptMouse = New Point(e.X, e.Y)


        Dim ptcell = PointToCell(ptMouse)


        If (ptcell.X >= 0 And ptcell.X < m_numCells.Width And _


            ptcell.Y >= 0 And ptcell.Y < m_numCells.Height) Then


 


            DrawLineOfCells(PointToCell(m_PtOld.Value), ptcell, New DrawCellDelegate(AddressOf DrawACell))


            m_PtOld = ptMouse


        End If


    End Sub


    Function DrawACell(ByVal ptCell As Point, ByVal br As Brush) As Boolean


        Dim fDidDraw = False


        If Not m_cells(ptCell.X, ptCell.Y) Then


            m_cells(ptCell.X, ptCell.Y) = True


            m_oGraphics.FillRectangle(br, _


                    m_Offset.Width + ptCell.X * m_cellSize.Width, _


                    m_Offset.Height + ptCell.Y * m_cellSize.Height, _


                    m_cellSize.Width, _


                    m_cellSize.Height)


            fDidDraw = True


        End If


        Return fDidDraw


    End Function


    Sub DrawLineOfCells(ByVal p0 As Point, ByVal p1 As Point, ByVal drawit As DrawCellDelegate)


        Dim br = m_brushMouse


        Dim x0 = p0.X


        Dim y0 = p0.Y


        Dim x1 = p1.X


        Dim y1 = p1.Y


        Dim fSwapped = False


        Dim dx = Math.Abs(x1 – x0)


        Dim dy = Math.Abs(y1 – y0)


        If dy > dx Then


            fSwapped = True ‘ swap x0<=>y0, x1<->y1


            x0 = p0.Y


            y0 = p0.X


            x1 = p1.Y


            y1 = p1.X


            dx = Math.Abs(x1 – x0)


            dy = Math.Abs(y1 – y0)


        End If


        Dim err = CInt(dx / 2)


        Dim y = y0


        Dim xstep = 1


        If x0 > x1 Then


            xstep = -1


        End If


        Dim ystep = 1


        If y0 > y1 Then


            ystep = -1


        End If


        Dim x = x0


        While x <> x1 + xstep


            Dim cx = x, cy = y ‘ copy of x,y


            If fSwapped Then


                cx = y


                cy = x


            End If


            If drawit(New Point(cx, cy), br) Then ‘ if it wasn’t already drawn


                br = m_brushGenerated


            End If


            err -= dy


            If err < 0 Then


                y += ystep


                err += dx


            End If


            x += xstep


        End While


    End Sub


#If AREA Then


    Dim m_brushFill = New SolidBrush(Color.Blue)


    Dim m_oColor = Color.Black


    Sub AreaFill(ByVal ptcell As Point)


        If (ptcell.X >= 0 And ptcell.X < m_numCells.Width) Then


 


            If (ptcell.Y >= 0 And ptcell.Y < m_numCells.Height) Then


                                    System.Threading.Thread.Sleep(100);


                If (DrawACell(ptcell, m_brushFill)) Then


                    Me.m_oColor = Color.FromArgb((((Me.m_oColor.ToArgb And &HFFFFFF) + 140) And &HFFFFFF) Or &HFF000000)


 


                        m_oColor = Color.FromArgb((int)(((((uint)m_oColor.ToArgb() & 0xffffff) + 140) & 0xffffff) | 0xff000000));


                    m_brushFill = New SolidBrush(m_oColor)


                    AreaFill(New Point(ptcell.X – 1, ptcell.Y)) ‘ West


                    AreaFill(New Point(ptcell.X + 1, ptcell.Y)) ‘ East


                    AreaFill(New Point(ptcell.X, ptcell.Y + 1)) ‘ South


                    AreaFill(New Point(ptcell.X, ptcell.Y – 1)) ‘ North


                End If


            End If


        End If


    End Sub


#End If


 


End Class


 


</VB Sample>