Bresenhams Line Algorithm

Fri May 02 2025 15:06:07 GMT+0100 (British Summer Time) geometry function javascript archived

Raster line

Bresenhams Line Algorithm is a fantastic way to draw a line between 2 points. Unlike the line algorithm in our other pixel line article, this method does not include every point that would be touched by a line between the start and end points, but just those that are crossed by a reasonable amount.

This method is similar or the same as that which would be used by painting software to draw rasterized lines.

View example

This method takes four arguments: x1, y1, which is the starting point of the line, and x2, y2, the ending point of the line. The return value is an array containing the list of points used to create the line between the provided points.


function bresenhamsLine(x1, y1, x2, y2)
{
    line = new Array();
    
    var dx = Math.abs(x2 - x1);
    var dy = Math.abs(y2 - y1);
    
    var sx = (x1 < x2 ? 1 : -1);
    var sy = (y1 < y2 ? 1 : -1);
    
    var error = dx - dy;
    
    var x = x1, y = y1;
    
    while(1)
    {
        line.push([x, y]);
        
        if(x==x2 && y==y2) { break; }
        
        var e2 = 2 * error;
        
        if(e2 >-dy) { error-= dy; x+= sx; }
        if(e2 < dx) { error+= dx; y+= sy; }
    }
    
    return line;
}

Example source code


<!DOCTYPE html>
<html>
<head>

<script type="text/javascript">
var ctx = null, game = null;
var mouseX = -1, mouseY = -1;
var currentLine = null, point1 = [10,20], point2 = [50,20], whichPoint = 1;

window.onload = function() {
    game = document.getElementById('game');
    ctx = game.getContext('2d');
    ctx.font = "bold 10pt sans-serif";

    currentLine = bresenhamsLine(point1[0], point1[1], point2[0], point2[1]);

    game.addEventListener('mouseup', function(e) {
        // Get the position of the mouse click on the page
        mouseX = e.pageX;
        mouseY = e.pageY;

        // Find the offset of the Canvas relative to the document top, left,
        // and modify the mouse position to account for this
        var p = game;
        do
        {
            mouseX-= p.offsetLeft;
            mouseY-= p.offsetTop;

            p = p.offsetParent;
        } while(p!=null);

        // fit the real mouse position to our 10x10 grid
        mouseX = Math.floor(mouseX / 10);
        mouseY = Math.floor(mouseY / 10);

        // Which line end are we changing?  Alternate each time the mouse is clicked.
        if(whichPoint==1)
        {
            point1 = [mouseX, mouseY];
            whichPoint = 2;
        }
        else
        {
            point2 = [mouseX, mouseY];
            whichPoint = 1;
        }

        // Calculate the points on the new line
        currentLine = bresenhamsLine(point1[0], point1[1], point2[0], point2[1]);

        // Show a list of points for information
        var htm = '';
        for(p in currentLine)
        {
            htm+= '<li>' + currentLine[p][0] + ', ' + currentLine[p][1] + '</li>';
        }
        document.getElementById('pointList').innerHTML = htm;
    });

    requestAnimationFrame(drawGame);
};

function bresenhamsLine(x1, y1, x2, y2)
{
    line = new Array();
    
    var dx = Math.abs(x2 - x1);
    var dy = Math.abs(y2 - y1);
    
    var sx = (x1 < x2 ? 1 : -1);
    var sy = (y1 < y2 ? 1 : -1);
    
    var error = dx - dy;
    
    var x = x1, y = y1;
    
    while(1)
    {
        line.push([x, y]);
        
        if(x==x2 && y==y2) { break; }
        
        var e2 = 2 * error;
        
        if(e2 >-dy) { error-= dy; x+= sx; }
        if(e2 < dx) { error+= dx; y+= sy; }
    }
    
    return line;
}

function drawGame()
{
    if(ctx==null) { return; }

    // Clear the Canvas
    ctx.fillStyle = "#ffffff";
    ctx.fillRect(0, 0, 600, 400);

    // Draw the grid
    ctx.strokeStyle = "#999999";
    ctx.beginPath();
    for(y = 0; y < (400/10); ++y)
    {
        for(x = 0; x < (600/10); ++x)
        {
            ctx.rect((x*10), (y*10), 10, 10);
        }
    }
    ctx.closePath();
    ctx.stroke();
    
    // Draw the line
    ctx.fillStyle = "#ff9999";
    ctx.strokeStyle = "#ff3333";
    ctx.beginPath();
    for(p in currentLine)
    {
        ctx.rect(currentLine[p][0] * 10, currentLine[p][1] * 10, 10, 10);
    }
    ctx.closePath();
    ctx.fill();
    ctx.stroke();

    // Show some information...
    ctx.fillStyle = "#ff0000";
    ctx.fillText("Line from " + point1[0] + "," + point1[1] + " to " + point2[0] + "," + point2[1], 10, 20);

    // Ask for the next animation frame
    requestAnimationFrame(drawGame);
}
</script>
</head>
<body>

<p></p>

<canvas id="game" width="600" height="400"></canvas>
<ul id="pointList" style="font-family:monospace;"></ul>

</body>
</html>