Scanline Flood Fill
Comments: 6 - Date: February 8th, 2011 - Categories: Programming
After spending a while looking for a decent scanline flood fill algorithm and not finding one, I built my own. The above interactive example shows how both scanline and simple flood filling work. You can draw and test any of the four different flood fills to see how they compare. Once you have filled an area, clicking and holding the “Show pixels tested” button shows a “heat” map of the number of times each pixel has been tested (from green:1 to red:8).
The scanline flood fill algorithm works by scanning a line, and adding ranges on the next/previous lines to a stack. For a shape with no loops or thin walls which are filled on both sides the scanline algorithm will only test each pixel once. It achieves this by skipping testing the range of pixels that the current line was filled from.
A rough outline of the algorithm is:
- Add the starting range [x, y] to a stack.
- While there is a range to fill:
- Extend the current range left and right.
- Add new ranges on the previous and next lines that overlap the current range to the stack. Skip testing the range of pixels that the current range was created from.
This implementation is nice, clean, fast and supports 8-way (diagonal) filling. All the values needed are passed in as parameters to floodFillScanline
. The test(x, y)
function returns true for pixels that need filling, the paint(x, y)
function paints the pixel. This function will fill all connected pixels starting from (x, y) as long as test
and paint
are defined over x:[0, width) and y:[0, height) and a painted pixel does not test true.
function floodFillScanline(x, y, width, height, diagonal, test, paint) {
// xMin, xMax, y, down[true] / up[false], extendLeft, extendRight
var ranges = [[x, x, y, null, true, true]];
paint(x, y);
while(ranges.length) {
var r = ranges.pop();
var down = r[3] === true;
var up = r[3] === false;
// extendLeft
var minX = r[0];
var y = r[2];
if(r[4]) {
while(minX>0 && test(minX-1, y)) {
minX--;
paint(minX, y);
}
}
var maxX = r[1];
// extendRight
if(r[5]) {
while(maxX<width-1 && test(maxX+1, y)) {
maxX++;
paint(maxX, y);
}
}
if(diagonal) {
// extend range looked at for next lines
if(minX>0) minX--;
if(maxX<width-1) maxX++;
}
else {
// extend range ignored from previous line
r[0]--;
r[1]++;
}
function addNextLine(newY, isNext, downwards) {
var rMinX = minX;
var inRange = false;
for(var x=minX; x<=maxX; x++) {
// skip testing, if testing previous line within previous range
var empty = (isNext || (x<r[0] || x>r[1])) && test(x, newY);
if(!inRange && empty) {
rMinX = x;
inRange = true;
}
else if(inRange && !empty) {
ranges.push([rMinX, x-1, newY, downwards, rMinX==minX, false]);
inRange = false;
}
if(inRange) {
paint(x, newY);
}
// skip
if(!isNext && x==r[0]) {
x = r[1];
}
}
if(inRange) {
ranges.push([rMinX, x-1, newY, downwards, rMinX==minX, true]);
}
}
if(y<height)
addNextLine(y+1, !up, true);
if(y>0)
addNextLine(y-1, !down, false);
}
}
Comment by neha - February 28, 2013 @ 4:03 am
smart
Comment by Troy - August 5, 2013 @ 9:01 pm
Your code seems to be displaying wrong for me in both Chrome on Windows, and Iceweasel on Debian.
In the first while loop in the extendRight routine, the browser is seeing a huge HTML tag that is supposed to be a less-than compare, some code, and an unrelated greater-than compare.
Thanks for sharing, though.
Comment by Sly1024 - December 29, 2013 @ 4:27 pm
Very nice and quick algrorithm.
For others: do right click and view page source, you’ll see a block of javascript, that’s the correct code.
There’s a bug in it: the line “if(y<height)" should be "if(y<height-1)".
Thanks!
Comment by JM - May 15, 2015 @ 5:44 pm
Some of your function header’s variables are just meaningless nonsense! I’m talking about:
“diagonal, test, paint”
What on Earth are these?
If you *must* include meaningless nonsense in your header then you should have a comment on top that explains what’s expected.
Anyway, a professional generic FloodFill function must only accept 3 variables. These are X,Y, and Color.
Comment by Sky - June 11, 2015 @ 8:38 am
JM: Incorrect, about the Diagonal variable. Effectively it allows a single function to be used for both 4-directional adjacency and 8-directional adjacency filling. I do agree that the names could have been chosen better, though.
Also, you are incorrect again about the “Test” variable. While it could have been named better, it is the array of values for checking flood fill. How do you expect to flood fill an image when you aren’t even provided the area *to* fill? A better function might look like this:
function floodFill(image, x, y, width, height, is8Way)
While you might say that width, height are implied from the image, if you are working in a C-like paradigm that is not always true. If floodFill were linked to an image object, or the image object is able to keep track of its width and height,
function floodFill(image, x, y, is8Way)
could also be good.
Comment by JM - June 30, 2015 @ 11:53 pm
The idea of Floodfill() is to start changing the pixel’s color at (X,Y) and continue painting pixels until it either reaches the end of the screen or a pixel that is colored different to the one at (X,Y).
Therefore FloodFill(X,Y,Color) is all the variables you’ll ever need.
So the first thing your floodfill function should do is to check what color it landed on at (x,y) and continue looking for similar pixels that are continuous.
I’d happily post source of FloodFills (mine and others in C++ and Pascal) from the 80s/90s when the heat was on, but it’s not very convenient form me right now to dig up old archives.
Anyway, good luck with everything.
Leave a comment