A Flood-Fill Implementation in JavaScript

Below is a simple implementation of a floodfill algorithm in JavaScript. When run, the program will draw a green background on a canvas, render the word “FLOOD” over it in orange, and then flood-fill the background with cyan, leaving the interiors (and outside edges, due to a “tolerance” setting of 0) of the “O” and “D” characters with the original background. To see the code in action, copy it into an .html file and open that file in a web browser that runs JavaScript.

The floodFill() function extends the existing CanvasRenderingContext2D class.
The function takes as its arguments the x and y position of the first pixel to fill, followed by an argument named “colorDifferenceTolerance”. The algorithm uses the A* (“A-star”) algorithm to identify contiguous pixels to be filled with the specified fill color. If the color tolerance is set to 0, as in the sample below, only contiguous pixels that exactly match the color of the first pixel will be overwritten with the fill color.

Floodfill.png


<html>
<body>


<script type="text/javascript">

// main
function main()
{
    var canvasSize = new Coords(100, 100);

    var canvas = document.createElement("canvas");
    canvas.width = canvasSize.x;
    canvas.height = canvasSize.y;
    document.body.appendChild(canvas);

    var graphics = canvas.getContext("2d");

    graphics.fillStyle = "DarkGreen";
    graphics.fillRect(0, 0, canvasSize.x, canvasSize.y);

    var fontHeight = canvasSize.y * .25;
    graphics.font = fontHeight + "px sans-serif";
    graphics.fillStyle = "Orange";
    graphics.fillText
    (
        "FLOOD", 
        fontHeight * .25, 
        (canvasSize.y - fontHeight) / 2 + fontHeight 
    );

    graphics.fillStyle = "Cyan";
    graphics.floodFill(0, 0, 0);
}

// extensions

function CanvasRenderingContext2DExtensions()
{
    // extension class
}
{
    CanvasRenderingContext2D.prototype.floodFill = function(x, y, colorDifferenceTolerance)
    {    
        var canvas = this.canvas;
        var imageSize = new Coords(canvas.width, canvas.height);
        var imageSizeMinusOnes = imageSize.clone().subtract(new Coords(1, 1));

        var colorToFillOverRGBA = this.getImageData(x, y, 1, 1).data;

        var pixelPos = new Coords(x, y);
        var pixelIndexStart = pixelPos.y * imageSize.x + pixelPos.x;
        var pixelIndicesToTest = [ pixelIndexStart ];
        var pixelIndicesAlreadyTested = [];

        var neighborOffsets = 
        [
            new Coords(-1, 0),
            new Coords(1, 0),
            new Coords(0, -1),
            new Coords(0, 1)
        ];

        while (pixelIndicesToTest.length > 0)
        {
            var pixelIndex = pixelIndicesToTest[0];
            pixelIndicesToTest.splice(0, 1);
            pixelIndicesAlreadyTested[pixelIndex] = pixelIndex;

            pixelPos.x = pixelIndex % imageSize.x;
            pixelPos.y = Math.floor(pixelIndex / imageSize.x);

            var pixelRGBA = this.getImageData(pixelPos.x, pixelPos.y, 1, 1).data;
            var pixelDifference = Math.abs
            (
                pixelRGBA[0] - colorToFillOverRGBA[0]
                + pixelRGBA[1] - colorToFillOverRGBA[1]
                + pixelRGBA[2] - colorToFillOverRGBA[2]
            );

            if (pixelDifference <= colorDifferenceTolerance)
            {
                this.fillRect(pixelPos.x, pixelPos.y, 1, 1);

                var neighborPos = new Coords();

                for (var n = 0; n < neighborOffsets.length; n++)
                {
                    var neighborOffset = neighborOffsets[n];

                    neighborPos.overwriteWith
                    (
                        pixelPos
                    ).add
                    (
                        neighborOffset
                    );

                    if (neighborPos.isInRange(imageSize) == true)
                    {
                        var neighborIndex = 
                            neighborPos.y * imageSize.x + neighborPos.x;
                        var isPixelIndexAlreadyUnderConsideration = 
                        (
                            pixelIndicesToTest.indexOf(neighborIndex) >= 0 
                            || pixelIndicesAlreadyTested[neighborIndex] != null
                        )  
                        if (isPixelIndexAlreadyUnderConsideration == false)
                        {
                            pixelIndicesToTest.push(neighborIndex);
                        }
                    }
                }
            }                
        }
    }
}

// classes

function Coords(x, y)
{
    this.x = x;
    this.y = y;
}
{
    Coords.prototype.add = function(other)
    {
        this.x += other.x;
        this.y += other.y;
        return this;
    }

    Coords.prototype.clone = function()
    {
        return new Coords(this.x, this.y);
    }

    Coords.prototype.isInRange = function(max)
    {
        var returnValue = 
        (
            this.x >= 0 
            && this.x <= max.x
            && this.y >= 0 
            && this.y <= max.y
        );
        return returnValue;
    }

    Coords.prototype.overwriteWith = function(other)
    {
        this.x = other.x;
        this.y = other.y;
        return this;
    }

    Coords.prototype.subtract = function(other)
    {
        this.x -= other.x;
        this.y -= other.y;
        return this;
    }
}

// run

main();

</script>

</body>
</html>

Advertisements
This entry was posted in Uncategorized and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s