Will Thimbleby

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:

1. Add the starting range [x, y] to a stack.
2. While there is a range to fill:
   1. Extend the current range left and right.
   2. 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);
    }
}