13,046,679 members (78,903 online)
Tip/Trick
Add your own
alternative version

#### Stats

7.3K views
55 downloads
2 bookmarked
Posted 18 Sep 2012

# Boundary Trace FloodFill

, 18 Sep 2012
 Rate this:
Please Sign up or sign in to vote.
Because the FloodFill algorithms I encountered all used a stack or recursion, I decided to benchmark the Boundary Trace algorithm against some of them.

## Introduction

While I was playing with a Mandelbrot set in VB6 I faced the problem of filling the set quickly. I looked into Floodfill algorithms and stumbled upon a Boundary Trace by Michael R. Ganss. Because the FloodFill algorithms I encountered all used a stack or recursion, I decided to benchmark the Boundary Trace algorithm against some of them. I rewrote it so the code is more transparent. It proved faster, with little load on resources.

## Background

I usually program in Visual Basic but decided on VC10 for the benchmark. I used an application (floodfill.cpp) by Lode VandeVenne that benchmarked some FloodFill algorithms, and added my versions of the Boundary Trace.

The author of the original is Michael R. Ganss. This is his explanation:

Boundary Tracing Generation Method, traces the outline of areas of a single color and fills them in. We start from pixel (x,y) going right and keeping the "wall" to our left until we get back to the starting point. For each pixel, the next pixel visited will be computed thus:

1. check pixel to left (looking in the current direction, i.e. if the current direction is right, the pixel to the left is the one above it). If it's part of the wall (i.e. offscreen or a different color than the one we're tracking), go to b). If it's not, it is the next pixel.
2. do same for pixel straight ahead. Go there if it's not part of the wall.
3. ditto for pixel to the right. If this pixel is also part of the wall, go back one pixel. When we're back at the starting point we trace the boundary once more. Now, whenever we move up, we plot pixels to the right of the current one until we hit the wall.

Source: Michael R. Ganss

An algorithm based on the same principle, but visiting every pixel is described here http://www.davdata.nl/math/floodfill.html (completely nonrecursive, but slow). I rewrote the original algorithm (used on a Mandelbrot set) to perform floodfill.

## Using the Code

The source code contains several Floodfill algorithms, including four versions of Boundary Trace, the algorithm that performed best. The idea of `BoundaryTrace` is to trace the outlines of the area to be filled by going left as much as possible, keeping a 'wall' of pixels that should not be filled to the (relative) left side. The same algorithm is used to trace a maze. After tracing the complete boundary, filling all the boundary pixels with the fill color, and reaching the start spot again, a second tracing is done while filling the area between the boundaries.

The function `BoundaryTrace` shows the basic algorithm, however it has limitations : if the fill area is 1 pixel wide on the edge it gives an incomplete fill, and if there are 'islands' in the fill area it gives an incomplete fill as well. `BoundaryTrace2` adresses those problems, and in case there are 'islands' it calls `BoundaryTrace2a` (recursive if needed : if several 'islands' are on top of each other), where the wall is kept to the right, thus going around the edges of the island.

`BoundaryTrace3` does the same as BoundaryTrace2, however the code is optimized for performance - this gives a slight improvement but the code becomes much less transparent.

`BoundaryTrace4` is like `BoundaryTrace2` but uses a stack, collecting all the boundary points that are used to fill the area by going down untill we hit a pixel that is not the fillcolor nor the original color - in other words, we hit the opposite boundary. So we don't need a second tracing. And then of course I had to test the stack option with `BoundaryTrace3` code. It is faster sometimes, but not always. All this code is in the source download. On this page I give the basic algorithm as code snippet.

Feel free to use this code if you are looking for a faster FloodFill.

## Initializing

```void BoundaryTrace(int x, int y, Uint32 fillcolor, Uint32 oldcolor)
{
//we start at screen position x, y where a MouseClick event happened
// no need to fill if fillcolor is oldcolor
if(fillcolor == oldcolor) return;
// storage for 4 points
int PtX[4];
int PtY[4];
//h = height, w = width
int t = h-1;
int q = w-1;
//find a starting point (boundary spot) by going down untill we hit a different color
while(screenBuffer[x][y]==oldcolor)
{
y++;
if (y > t)
break;
}
y--;
bool IsTraced = FALSE;
// The direction we are going (0 = Right, 1 = Down, 2 = Left, 3 = Up), select one to start
int iDir =2;
int Y3;
//save the starting point
int sX = x;
int sY = y;
bool onEdge;```

## The First Loop

The first loop terminates if we are back at our starting point (`sX`, `sY`) We do 2 things in the first loop

1. check of we are on an edge of the screen, if so, move along the edge.
2. if we are not on the edge, calculate the 4 neighbour points of the current position.

So, first check the edges:

```while (!IsTraced)
{               // in case we are at the edge of the screen, trace the edge
onEdge = FALSE;
if (x==0) //edge
{
while ((screenBuffer[x][y-1]==oldcolor || screenBuffer[x][y-1]==fillcolor) && y>0)
{
y--;
screenBuffer[x][y] = fillcolor;
}
iDir = 0;
}
if (y==0) //edge
{

while ((screenBuffer[x+1][y]==oldcolor || screenBuffer[x+1][y]==fillcolor) && x<q)
{
x++;
screenBuffer[x][y] = fillcolor;
}
iDir = 1;
}
if (x==q) //edge
{
while ((screenBuffer[x][y+1]==oldcolor || screenBuffer[x][y+1]==fillcolor) && y<t)
{
y++;
screenBuffer[x][y] = fillcolor;
}
iDir = 2;
}
if (y==t) //edge
{
while ((screenBuffer[x-1][y]==oldcolor || screenBuffer[x-1][y]==fillcolor) && x>0)
{
x--;
screenBuffer[x][y] = fillcolor;
//we might encounter the starting point here, because we defined the starting point sX, sY at the bottom of the fill area
if (sX==x && sY==y)
{
IsTraced = TRUE;
onEdge = TRUE;
break;
}
}
iDir = 3;
if (!IsTraced && x==0) onEdge = TRUE;

}
```

If we are not on an edge, we calculate 4 neighbour points, it depends on the Direction (iDir) in what order they are checked (always the left one relative to the direction first, then straigt ahead, then right, finally going back.

```if (!onEdge) //trace boundary
{
switch (iDir)
{
case 0: //going Right
PtX[0] = x;
PtY[0] = y - 1;
PtX[1] = x + 1;
PtY[1] = y;
PtX[2] = x;
PtY[2] = y + 1;
PtX[3] = x - 1;
PtY[3] = y;
break;
case 1: //going Down
PtX[0] = x + 1;
PtY[0] = y;
PtX[1] = x;
PtY[1] = y + 1;
PtX[2] = x - 1;
PtY[2] = y;
PtX[3] = x;
PtY[3] = y - 1;

break;
case 2: //going Left
PtX[0] = x;
PtY[0] = y + 1;
PtX[1] = x - 1;
PtY[1] = y;
PtX[2] = x;
PtY[2] = y - 1;
PtX[3] = x + 1;
PtY[3] = y;

break;
case 3: //going Up
PtX[0] = x - 1;
PtY[0] = y;
PtX[1] = x;
PtY[1] = y - 1;
PtX[2] = x + 1;
PtY[2] = y;
PtX[3] = x;
PtY[3] = y + 1;

break;
}
//proceed to next pixel on the left (relative to Direction) and change Direction
if (screenBuffer[PtX[0]][PtY[0]]==oldcolor || screenBuffer[PtX[0]][PtY[0]]==fillcolor)
{
x = PtX[0];
y = PtY[0];
iDir = (iDir + 3)%4;
}
else
{
//if we did hit the wall proceed straight ahead (relative to direction)
if (screenBuffer[PtX[1]][PtY[1]]==oldcolor || screenBuffer[PtX[1]][PtY[1]]==fillcolor)
{
x = PtX[1];
y = PtY[1];
}
else
{
// if we did hit the wall go right (relative to Direction) and change Direction
if (screenBuffer[PtX[2]][PtY[2]]==oldcolor || screenBuffer[PtX[2]][PtY[2]]==fillcolor)
{
x = PtX[2];
y = PtY[2];
iDir = (iDir + 1)%4;
}
else
// we hit the wall in all directions so we go back to the previous pixel
{
x = PtX[3];
y = PtY[3];
iDir = (iDir + 2)%4;
}
}
}
screenBuffer[x][y] = fillcolor;

if (sX==x && sY==y)
// we are back at the starting point
IsTraced = TRUE;
}
}```

So in the first loop we have traced the complete boundary of the area to be filled, and we gave the boundary pixels we encountered the value of fillcolor.

Now we are going to trace the boundary once again, this time we will fill the area : each time we have direction Right (so we are at the top of the fill area) we go down from the current pixel untill we hit the opposite border at the bottom of the fill area, filling the pixels on the way with fillcolor. We fill in case `y = 0` (if we are on the top edge) or in case iDir = 0 (=Right)

```	// trace the boundary once again, this time filling
IsTraced = FALSE;
iDir = 2;
while (!IsTraced)
{
onEdge = FALSE;
if (x==0)
{
while (screenBuffer[x][y-1]==fillcolor && y>0) y--;
iDir = 0;
}
if (y==0)
{
while ( screenBuffer[x+1][y]==fillcolor && x<q)
{
Y3 = y ;
//fill 1 line going down untill we hit the opposite wall
while (screenBuffer[x][Y3] ==oldcolor || screenBuffer[x][Y3]==fillcolor)
{
screenBuffer[x][Y3]=fillcolor;
Y3++;
if (Y3 == t)
break;
}
x++;
}
Y3 = y ;
//fill last line going down
while (screenBuffer[x][Y3] ==oldcolor || screenBuffer[x][Y3]==fillcolor)
{
screenBuffer[x][Y3]=fillcolor;
Y3++;
if (Y3 == t)
break;
}
iDir = 1;
}
if (x==q)
{
while (screenBuffer[x][y+1]==fillcolor && y<t) y++;
iDir = 2;
}
if (y==t)
{
while (screenBuffer[x-1][y]==fillcolor && x>0)
{
x--;
if (sX==x && sY==y)
{
IsTraced = TRUE;
onEdge = TRUE;
break;
}
}
iDir = 3;
if (!IsTraced && x==0) onEdge = TRUE;
}
if (!onEdge)
{
switch (iDir)
{
case 0:
PtX[0] = x;
PtY[0] = y - 1;
PtX[1] = x + 1;
PtY[1] = y;
PtX[2] = x;
PtY[2] = y + 1;
PtX[3] = x - 1;
PtY[3] = y;
Y3 = y ;
//fill 1 line going down untill we hit the opposite wall
while (screenBuffer[x][Y3] ==oldcolor || screenBuffer[x][Y3]==fillcolor)
{
screenBuffer[x][Y3]=fillcolor;
Y3++;
if (Y3 == t)
break;
}
break;
case 1:
PtX[0] = x + 1;
PtY[0] = y;
PtX[1] = x;
PtY[1] = y + 1;
PtX[2] = x - 1;
PtY[2] = y;
PtX[3] = x;
PtY[3] = y - 1;

break;
case 2:
PtX[0] = x;
PtY[0] = y + 1;
PtX[1] = x - 1;
PtY[1] = y;
PtX[2] = x;
PtY[2] = y - 1;
PtX[3] = x + 1;
PtY[3] = y;

break;
case 3:
PtX[0] = x - 1;
PtY[0] = y;
PtX[1] = x;
PtY[1] = y - 1;
PtX[2] = x + 1;
PtY[2] = y;
PtX[3] = x;
PtY[3] = y + 1;
break;
}
if (screenBuffer[PtX[0]][PtY[0]]==fillcolor)
{
x = PtX[0];
y = PtY[0];
iDir = (iDir + 3)%4;
}
else
{
if (screenBuffer[PtX[1]][PtY[1]]==fillcolor)
{
x = PtX[1];
y = PtY[1];
}
else
{
if (screenBuffer[PtX[2]][PtY[2]]==fillcolor)
{
x = PtX[2];
y = PtY[2];
iDir = (iDir + 1)%4;
}
else
{
x = PtX[3];
y = PtY[3];
iDir = (iDir + 2)%4;
}
}
}
if (sX==x && sY==y)	IsTraced = TRUE;
}
}
}```

This code has some limitations :

• If the fill area is 1 pixel wide at the edge it finds its starting point too early
• If there are 'islands' in the fill area it gives an incomplete fill

Hence `BoundaryTrace2` and `BoundaryTrace3` (using recursion for 'islands'). `BoundaryTrace2` is a compact code, while `BoundaryTrace3` is written to optimize performance, giving up on code transparency.

In `BoundaryTrace4` and `BoundaryTrace5` we use a stack to speed things up (put the pixels on the top of the fill area on stack, so the second trace is not needed). Actually, the stack does not always perform better. Despite the differences the basic algorithm is the same for all functions, as explained above These functions are given in the source download.

## Points of Interest

I enjoyed (re)writing this code a lot, sometimes however I had to get used to VC10 again after working in VB for a long time. Though the algorithm is not mine, I have never seen it used for FloodFill before.

How to use the demo : use left mouse button to draw a shape (make sure its boundaries are uninterrupted). Then click inside the area to be filled with the right mouse button. To perform a benchmark test, press SPACE thereafter. The time is in milliseconds (for 600 iterations).

## License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

## About the Author

 Retired Netherlands
My name is Franciska Ruessink. I studied IT at The Hague Hogeschool (University) and was employed in IT as software developer, database developer, network administrator, and IT project manager for several years.
After an early retirement I continue to write software for the fun of it and to help friends, I also did some web development. I usually work with VB but started again with VC++ recently.

## Comments and Discussions

 First Prev Next
 My vote of 5 Kanasz Robert19-Sep-12 4:36 Kanasz Robert 19-Sep-12 4:36
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Jul-17 19:06 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170713.1 | Last Updated 18 Sep 2012
Article Copyright 2012 by FranciskaR
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid