Click here to Skip to main content
15,867,686 members
Articles / Programming Languages / Javascript
Article

Drawing lines in Mozilla based browsers and the Internet Explorer

Rate me:
Please Sign up or sign in to vote.
4.78/5 (15 votes)
28 Nov 20068 min read 158.7K   1.5K   47   22
Implementing the Bresenham line drawing algorithm in JavaScript to be used in browsers.

Introduction

In this article, I want to explain and deduce the line drawing algorithm by Bresenham. Afterwards, I will show an optimized version which can be used to draw lines in Gecko based browsers like Mozilla or Firefox and Microsoft's Internet Explorer. As you know, HTML itself is not able to describe lines. Therefore, there is no built-in features in the above-mentioned browsers for drawing lines. By implementing the Bresenham algorithm with JavaScript while applying some tricks, we will be able to draw lines in a good manner in respect to the browser's runtime and memory footprints.

The Bresenham algorithm

The Bresenham algorithm aims at drawing an approximation of the mathematically correct line, which can be described in the form of a linear mathematical function. The demand for this algorithm came to hand when the first raster display or digital plotters were developed. These devices were unable to draw a continuous line in a strict mathematical sense. Rather, they were designed to plot a single pixel with a certain height and width on a screen coordinate. The approximation is based on finding the best and closest path on this raster display from the starting point to the end point.

The ideal line

The mathematical formula for describing a line is the following linear equation: y = m*x + b. In other words, a mathematical line is defined by a slope (variable m) and a pitch from the x-axis (variable b). By choosing two different points, we can, therefore, exactly define a line. To determine the two missing pieces of information (the slope and the pitch), we have to solve the following two equations:

I) y1 = m*x1 + b
II) y2 = m*x2 + b
 
=> I) 
b = y1 - m*x1
=> II) 
y2 = m*x2 + y1 - m*x1
y2 = m*(x2 - x1) + y1
m = (y2 - y1) / (x2 - x1)      | x1 != x2

dy = y2 - y1
dx = x2 - x1
m = dy / dx
=> I)
b = y1 - (dy / dx) * x1

The following image illustrates the variables slope and pitch, and how they can be determined by two different points:

To draw a line from the starting point to the end point, we only have to loop from x1 to x2 and calculate the corresponding y-value. Our first approach for an algorithm to do this kind of drawing would look like the following:

JavaScript
function drawline1(x1, y1, x2, y2)
{
    if (x1 == x2 && y1 == y2) {
        setPixel(x1, y1);
        return;
    }
    var dx = x2 - x1; var sx = (dx < 0) ? -1 : 1;
    var dy = y2 - y1; var sy = (dy < 0) ? -1 : 1;
    var m = dy / dx;
    var b = y1 - m * x1;
    
    while (x1 != x2)
    {
        var y = parseInt(Math.round(m*x1 + b));
        setPixel(x1, y);
        x1 += sx;
    }
}

In the attached source files of this article, you will find a file called article_illustrations.html. Please open this file and refer to illustration A to test this algorithm directly. You have to choose two different points in the grid, and have to press the drawline button afterwards.

Imperfections of this algorithm

Drawing lines which slope reveals some of the imperfections of this algorithm. One major problem is that, in such a circumstance, the line becomes discontinuous in respect to the y-direction. An easy solution to this problem is to distinguish between those cases. When dy is greater than dx, the inner-loop of the algorithm must run stepwise in y-direction, otherwise vise versa in x-direction. This means that, we just change the x- and y-axis, or rotate the whole coordinate system by 90 degrees, making the new dy less than dx.

Making the algorithm work

When we apply this distinction, the algorithm will draw correct lines in respect to our wanted approximation.

JavaScript
function drawline2(x1, y1, x2, y2)
{
    if (x1 == x2 && y1 == y2) {
        setPixel(x1, y1);
        return;
    }
    var dx = x2 - x1; var sx = (dx < 0) ? -1 : 1;
    var dy = y2 - y1; var sy = (dy < 0) ? -1 : 1;
    
    if (Math.abs(dy) < Math.abs(dx))
    {    
        var m = dy / dx;
        var b = y1 - m * x1;
        
        while (x1 != x2)
        {
            setPixel(x1, parseInt(Math.round(m*x1 + b)));
            x1 += sx;
        }
    } 
    else 
    {
        var m = dx / dy;
        var b = x1 - m * y1;
        
        while (y1 != y2)
        {
            setPixel(parseInt(Math.round(m*y1 + b)), y1);
            y1 += sy;
        }    
    }
}

Please refer to illustration B within article_illustrations.html.

Optimizing the inner loops

The implemented algorithm, so far, draws lines quite well, but lacks on good performance. There are two reasons why the performance is pure. If you take a look at the operations which are performed in the inner loops of the algorithm, then you will recognize that the mathematical function, m*x + b is evaluated each time. Therefore, our first optimization efforts will be, to get rid of this evaluation, especially the multiplication. We do this by incrementally calculating the right y- or x-value. For the sake of simplicity, I will assume that dy is less than dx. Under this circumstance, we have to calculate the right y-value and the starting point will be y1. Because the slope of the line is less than or equal to one, we can only reduce or increase the y-position in each step of the inner loop maximally by one. But this is only done when the fraction becomes greater than one. Applying this trick to the algorithm allows us to leave the mathematical function beside. But due to the fact that the slope of the line has to be a floating value, these operations are still slow.

JavaScript
function drawline3(x1, y1, x2, y2)
{
    if (x1 == x2 && y1 == y2) {
        setPixel(x1, y1);
        return;
    }
    var dx = x2 - x1; var sx = 1;
    var dy = y2 - y1; var sy = 1;
    
    if (dx < 0)    {
        sx = -1;
        dx = -dx;
    }
    if (dy < 0)    {
        sy = -1;
        dy = -dy;
    }
    
    if (dy < dx)
    {    
        var m = dy / dx;
        var fraction = 0.5 + m;
        
        while (x1 != x2)
        {
            if (fraction > 1)
            {
                y1 += sy;
                fraction -= 1;
            }
            fraction += m;
            setPixel(x1, y1);
            x1 += sx;
        }
    } 
    else 
    {
        var m = dx / dy;
        var fraction = 0.5 + m;
        
        while (y1 != y2)
        {
            if (fraction > 1)
            {
                x1 += sx;
                fraction -= 1;
            }
            fraction += m;
            setPixel(x1, y1);
            y1 += sy;
        }    
    }
}

But we can prevent this, by multiplying the slope with 2*dx or 2*dy, accordingly. This prevents the slope from becoming less than one, which allows us to use integer values.

JavaScript
var  fraction = dx + 2*dy;
while (x1 != x2)
{
    if (fraction > 2*dx)
    {
        y1 += sy;
        fraction -= 2*dx;
    }
    fraction += 2*dy;
    this.setPixel(x1, y1);
    x1 += sx;
}

If you look at the above code, there are some more optimizations left. First, there are a lot of places where 2*dx or 2*dy is used. Pre-calculating these values is a real performance burst. Finally, microcontrollers are faster when it comes to testing variables against zero. Therefore, the if statement will be modified to test against zero, and not 2*dx, which means, that we have to subtract 2*dx from the fraction. Frankly, I do not know if this optimization has any effect in a script language like JavaScript, but the original Bresenham algorithm proposes this, so I have mentioned this here.

The final Bresenham algorithm

JavaScript
function drawline4(x1, y1, x2, y2)
{
    var dx = x2 - x1; var sx = 1;
    var dy = y2 - y1; var sy = 1;
    
    if (dx < 0)    {
        sx = -1;
        dx = -dx;
    }
    if (dy < 0)    {
        sy = -1;
        dy = -dy;
    }
    
    dx = dx << 1;
    dy = dy << 1;
    this.setPixel(x1, y1);
    if (dy < dx)
    {    
        var fraction = dy - (dx>>1);
        while (x1 != x2)
        {
            if (fraction >= 0)
            {
                y1 += sy;
                fraction -= dx;
            }
            fraction += dy;
            x1 += sx;
            setPixel(x1, y1);
        }
    } 
    else 
    {
        var fraction = dx - (dy>>1);        
        while (y1 != y2)
        {
            if (fraction >= 0)
            {
                x1 += sx;
                fraction -= dy;
            }
            fraction += dx;
            y1 += sy;
            setPixel(x1, y1);
        }    
    }
}

See illustration C in article_illustrations.html.

Using the Bresenham algorithm to draw lines in browsers

Now, we have a quite optimized JavaScript version of the line drawing algorithm by Bresenham. In the inner loops of this algorithm, there are calls to an obscure setPixel function. Currently, this function sets a style attribute of the grid's corresponding cell element. Because this is not sufficient, we have to consider how we will print pixels in browsers. A straightforward solution is, to create a floating div element at the corresponding position whose height and width is exactly one pixel. As HTML is able to position elements absolutely, this is a possible way to draw pixels in the browser's drawing area. But you can imagine, that creating div elements for every pixel of a line is a very slow and exaggerated activity. Never mind, what kind of data structures the browser has to manage to create and show an element like this. Therefore, our implementation and adaptation of this line drawing algorithm will exactly create one div element for each step of the rasterized approximation. The illustration below shows what the adapted algorithm will do:

Instead of drawing each pixel of a line separately, it will union them appropriately in a line based manner, creating one div element for each of these combined lines. If you look at the illustration, this means, that instead of creating 16 elements, the algorithm will create only four different div tags, leading to nearly four times better runtime characteristics.

The code below adapts this idea to our line drawing algorithm. When the fraction is greater than zero, we have to change the corresponding x- or y-direction. At this point, the new algorithm draws a line, unifying all pixels in a row or column. Using this technique, we have amazing speed and memory benefits, especially when it come to long lines, the benefits are more than what I told you in the above illustration.

JavaScript
function drawline5(x1, y1, x2, y2)
{    
    //Always draw from left to right. 
    //This makes the algorithm much easier...
    if (x1 > x2)    {
        var tmpx = x1; var tmpy = y1;
        x1 = x2; y1 = y2;
        x2 = tmpx; y2 = tmpy;
    }
    
    var dx = x2 - x1;    
    var dy = y2 - y1; var sy = 1;    
    if (dy < 0)    {
        sy = -1;
        dy = -dy;
    }
    
    dx = dx << 1; dy = dy << 1;
    if (dy <= dx)
    {    
        var fraction = dy - (dx>>1);
        var mx = x1;
        while (x1 != x2)
        {
            x1++;
            if (fraction >= 0)
            {
                setPixel2(mx, y1,x1-mx,1);
                y1 += sy;
                mx = x1;
                fraction -= dx;
            }
            fraction += dy;
        }
        setPixel2(mx,y1,x1-mx,1);
    } 
    else 
    {
        var fraction = dx - (dy>>1);
        var my = y1;
        if (sy > 0)
        {        
            while (y1 != y2)
            {
                y1++;
                if (fraction >= 0)
                {
                    setPixel2(x1++, my,1,y1-my);
                    my = y1;
                    fraction -= dy;
                }
                fraction += dx;
            }    
            setPixel2(x1,my,1,y1-my);
        }
        else
        {
            while (y1 != y2)
            {
                y1--;
                if (fraction >= 0)
                {
                    setPixel2(x1++, y1,1,my-y1);
                    my = y1;
                    fraction -= dy;
                }
                fraction += dx;
            }    
            setPixel2(x1,y1,1,my-y1);        
        }
    }
}

How to use the drawline function

There are two ways of using this code in your web pages which is provided and encapsulated by a JavaScript class called Graphics. The first way is, to directly draw into the document when the page is being loaded and processed. You can achieve this, by placing the following code somewhere within the body element. This code writes JavaScript statements for creating each div element in the document. When the page is loaded, your lines are visible immediately. In this case, the coordinate system of the graphics context which is responsible for drawing the lines starts from the upper left corner of the browser's visible drawing area.

JavaScript
var g = new Graphics();
g.drawLine(100,50,200,70);
g.paint();

The other way to use this code is by drawing the lines after the page has been loaded. In this mode, the lines are drawn and connected with a container. Normally, this container can be another div element. To create a graphics context and connect it with a container, you have to set the id of the container while you create the context. The coordinate system, in this case, starts from the upper left corner of the container. The following code is needed to achieve the functionality:

JavaScript
var linecanvas_graphics = new Graphics('linecanvas');
function drawCanvas()
{
    try {
        var x1 = parseInt(document.getElementById('in_x1').value);
        var y1 = parseInt(document.getElementById('in_y1').value);
        var x2 = parseInt(document.getElementById('in_x2').value);
        var y2 = parseInt(document.getElementById('in_y2').value);
        var start = (new Date()).getTime();
        linecanvas_graphics.drawLine(x1, y1, x2, y2);
        linecanvas_graphics.paint();
        var stop = (new Date()).getTime();
        alert("This operation took " + (stop-start) + "ms");
    } catch(e) {
        alert("an error has occured, when the input values were parsed" + e);
    }
}

Conclusions and future work

I had the idea for this code when I saw Julijan Sribar's article about a 3D charting control, which can be found here. Some years ago, I had to code such a control in a server-side version, where only the graphics was drawn and send to the client's browser. As you can imagine, this approach does not provide much functionality on the client. Therefore, I thought of drawing this charting graphic on the client, but the lack of drawing capabilities of modern browsers frustrated me. I now have started working on a JavaScript based drawing library, which is capable of drawing most of the same elements the Windows API provides. This line drawing code is an extract of the code. I hope to finish this library someday and post it here. (Hey, where else, right? ;) For now, this line drawing code works quite well on Mozilla based browsers and the Internet Explorer. Actually, I have some problems with the IE, because it creates the div elements much slower than Mozilla, and I don't have a clue, why this happens. Another thing is that, IE does not draw the lines as clean and well as Mozilla. I hope to fix that in future. Please, try this code out and give me some feedback.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Chief Technology Officer W3L
Germany Germany
-Since 1th August 2007: Chief Technology Officer of W3L
-2002/08/01-2007/07/31: PhD student
-1997/10/15-2002/07/31: Studied Electrical Engineering and Computer Science

Comments and Discussions

 
QuestionMy vote of 5+ Pin
Petr Kohout10-Dec-12 10:45
Petr Kohout10-Dec-12 10:45 
GeneralMy vote of 5 Pin
Manoj Kumar Choubey26-Mar-12 0:26
professionalManoj Kumar Choubey26-Mar-12 0:26 
GeneralA More Efficient Solution Pin
Gapjumper20-Mar-10 22:16
Gapjumper20-Mar-10 22:16 
GeneralRe: A More Efficient Solution Pin
Doga Arinir1-Apr-10 3:55
Doga Arinir1-Apr-10 3:55 
Generalneed help with drawing the line Pin
tibang1-Sep-09 5:54
tibang1-Sep-09 5:54 
Generalabout in IE Error Pin
Dhiraj Gautame17-Jun-09 1:59
Dhiraj Gautame17-Jun-09 1:59 
Hi i want draw graph like on graph paper i just made function as following'

var linecanvas_graphics = new Graphics('WSBODY');
linecanvas_graphics
var inputspace=0;

//for Horizontal Lines

for(var i=0; i<50; i++)
{
linecanvas_graphics.drawLine(0,inputspace,1000,inputspace);
inputspace=inputspace+20;
linecanvas_graphics.paint();
}

//for vertical Lines

var inputspace=0;
for(var i=0; i<50; i++)
{
linecanvas_graphics.drawLine(inputspace,0,inputspace,1000);
inputspace=inputspace+20;
linecanvas_graphics.paint();
}

i have master page concept in content page i have <ifrane> in which i am drawing graph but i got error in
this.container.insertAdjacentHTML("BeforeEnd", this.backbuffer);

it got null i have passes canvas as parameter when i debug it got in fucntion

function Graphics(container);

but in
this.container = document.getElementById(container);

here it gives null this.container is null what i do please hlep me urgent

reply me on dhiraj.gautame@itcube.net
GeneralIE BUG Pin
titanboy70072-Sep-08 4:16
titanboy70072-Sep-08 4:16 
Generalthanks for posting this up Pin
kypronite20-Jul-08 6:08
kypronite20-Jul-08 6:08 
GeneralContinued Developement... Pin
Jason R Seney7-Jul-08 13:26
Jason R Seney7-Jul-08 13:26 
QuestionNice -- Can i use? Pin
multimedia919-Feb-08 2:48
multimedia919-Feb-08 2:48 
GeneralRe: Nice -- Can i use? Pin
Doga Arinir28-Mar-08 0:43
Doga Arinir28-Mar-08 0:43 
GeneralIs there sth wrong [modified] Pin
dkth1nh25-Sep-07 18:04
dkth1nh25-Sep-07 18:04 
Generalworth a look: Open-jACOB Draw2D Pin
freegroup25-Jan-07 11:21
freegroup25-Jan-07 11:21 
GeneralRe: worth a look: Open-jACOB Draw2D Pin
Doga Arinir25-Jan-07 21:59
Doga Arinir25-Jan-07 21:59 
GeneralAnother lib Pin
alex.barylski30-Nov-06 21:21
alex.barylski30-Nov-06 21:21 
GeneralRe: Another lib Pin
Doga Arinir30-Nov-06 23:31
Doga Arinir30-Nov-06 23:31 
QuestionWhat about VML or SVG? Pin
Dustin Metzgar30-Nov-06 7:33
Dustin Metzgar30-Nov-06 7:33 
AnswerRe: What about VML or SVG? Pin
Doga Arinir30-Nov-06 8:41
Doga Arinir30-Nov-06 8:41 
GeneralRe: What about VML or SVG? Pin
Dustin Metzgar30-Nov-06 9:14
Dustin Metzgar30-Nov-06 9:14 
GeneralRe: What about VML or SVG? Pin
Doga Arinir30-Nov-06 10:37
Doga Arinir30-Nov-06 10:37 
GeneralRe: What about VML or SVG? Pin
dadeval11-Dec-06 6:04
dadeval11-Dec-06 6:04 
GeneralRe: What about VML or SVG? Pin
Spiff Dog4-Dec-06 9:31
Spiff Dog4-Dec-06 9:31 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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