Bresenham Line Drawing Algorithm


Reading time: 25 minutes | Coding time: 10 minutes

Bresenham Line Algorithm is a optimistic & incremental scan conversion Line Drawing Algorithm which calculates all intermediate points over the interval between start and end points, implemented entirely with integer numbers and the integer arithmetic. It only uses addition and subtraction and avoids heavy operations like multiplication and division.

Algorithm

Bresenham Line Drawing Algorithm determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. To draw the line we have to compute first the slope of the line form two given points.
Bresenham Line Drawing Algorithm contains two phases :
1. slope(m) < 1.
2.1 slope(m) > 1.
2.2 slope(m) = 1.

  • According to slope Decision Parameter is calculated, which is used to make decision for selection of next pixel point in both the phases.

  • Derivation of Decision Parameter Pk
    * For slope(m) < 1 :
    * In below figure, the y coordinate on the mathematical line at xk+1 is โˆ’

    Bresenham Line Drawing Algorithm


    Bresenham Line Drawing Algorithm

              Y = m(Xk+1) + b

dupper and dlower are given as โˆ’

               dlower = y โˆ’ yk 
                      = m(Xk + 1) + b โˆ’ Yk
               dupper = (yk + 1) โˆ’ y 
                      = Yk + 1 โˆ’ m(Xk + 1) โˆ’ b                           
  • dupper and dlower are used to make a simple decision about which pixel is closer to the mathematical line. This simple decision is based on the difference between the two pixel positions.
  • dlower โˆ’ dupper = 2m(xk + 1) โˆ’ 2yk + 2b โˆ’ 1
  • substitute m with dy/dx where dx and dy are the differences between the end-points.
           dx(dlowerโˆ’dupper) = dx(2dy.dx(xk + 1) โˆ’ 2yk + 2b โˆ’ 1)
                             = 2dy.xk โˆ’ 2dx.yk + 2dy + 2dx(2b โˆ’ 1)
                             = 2dy.xk โˆ’ 2dx.yk + C                                    
  • So, a decision parameter Pk for the kth step along a line is given by โˆ’
             pk = dx(dlower โˆ’ dupper)
                = 2dy.xk โˆ’ 2dx.yk + C
  • The sign of the decision parameter Pk is the same as that of dlowerโˆ’dupper.

  • If pk is negative, choose the lower pixel, otherwise choose the upper pixel.

  • At step k+1, the decision parameter is given as โˆ’
    * pk + 1 = 2dy.xk + 1 โˆ’ 2dx.(yk+1) + C

    Subtracting pk from above statement we get โˆ’
    * pk + 1 โˆ’ pk = 2dy((xk+1) โˆ’ xk) โˆ’ 2dx((yk+1) โˆ’ yk)
    But, xk+1 is the same as (xk) + 1. Hence โˆ’
    * pk + 1 = pk + 2dy โˆ’ 2dx((yk+1) โˆ’ yk)
    Where, (Yk+1) โ€“ Yk is either 0 or 1 depending on the sign of Pk.

  • The first decision parameter p0 is evaluated at (x0, y0) is given as โˆ’
    * p0 = 2dy โˆ’ dx

Similarly,

  • For slope(m) > 1 && slope(m) = 1 :
Bresenham Line Drawing Algorithm
  • Decesion parameter -
    • pk + 1 = pk + 2dx โˆ’ 2dy((xk+1) โˆ’ xk)
  • The first decision parameter p0 is evaluated at (x0,y0) is given as โˆ’
    • p0 = 2dx โˆ’ dy

Pseudocode

  • Step 1 : Except the two end points of Line from User.
  • Step 2 : Calculate the slope(m) of the required Line.
  • Step 3 : Identify the value of slope(m).
    • Step 3.1 : If slope(m) is Less than 1 i.e: m < 1
      * Step 3.1.1 : Calculate the constants dx, dy, 2dy, and (2dy โ€“ 2dx) and get the first value for the decision parameter as -
      * p0 = 2dy โˆ’ dx
      * Step 3.1.2 : At each Xk along the line, starting at k = 0, perform the following test โˆ’
      * If pk < 0, the next point to plot is (xk + 1,yk) and
      pk+1 = pk + 2dy
      else
      * plot (xk,yk + 1)
      * pk+1 = pk + 2dy โˆ’ 2dx
      * Step 3.1.3 : Repeat step 4(dx - 1) times.

    • Step 3.2 : If slope(m) is greater than or equal to 1 i.e: m >= 1
      * Step 3.2.1 : Calculate the constants dx, dy, 2dy, and (2dy โ€“ 2dx) and get the first value for the decision parameter as -
      * p0 = 2dx โˆ’ dy
      * Step 3.2.2 : At each Yk along the line, starting at k = 0, perform the following test โˆ’
      * If pk < 0, the next point to plot is (xk,yk + 1) and
      pk+1 = pk + 2dx
      else
      * plot (xk + 1,yk)
      * pk+1 = pk + 2dx โˆ’ 2dy
      * Step 3.2.3 : Repeat step 4(dy - 1) times.

  • Step 3.3 : Exit.

Implementation


#include <iostream>

class BresenhamLineDrawingAlgorithm
{

public:
    void bresenhamLineDrawing() const;

    void getCoordinates();

private:
    int x1_, x2_, y1_, y2_;

};

void BresenhamLineDrawingAlgorithm::bresenhamLineDrawing() const
{
    //calculating range for line between start and end point
    int dx = X2 - X1;
    int dy = Y2 - Y1;

    int x = X1;
    int y = Y1;

    //this is the case when slope(m) < 1
    if(abs(dx) > abs(dy))
    {
        putpixel(x,y,GREEN);    //this putpixel is for very first pixel of the line
        int pk = (2 * abs(dy)) - abs(dx);

        for(int i = 0; i < abs(dx) ; i++)
        {
            x = x + 1;
            if(pk < 0)
                pk = pk + (2 * abs(dy));
            else
            {
                y = y + 1;
                pk = pk + (2 * abs(dy)) - (2 * abs(dx));
            }
            putpixel(x,y,GREEN);
            delay(10);
        }
        delay(30);
    }
    else
    {
        //this is the case when slope is greater than or equal to 1  i.e: m>=1
        putpixel(x,y,GREEN);    //this putpixel is for very first pixel of the line
        int pk = (2 * abs(dx)) - abs(dy);

        for(int i = 0; i < abs(dy) ; i++)
        {
            y = y + 1;
            if(pk < 0)
                pk = pk + (2 * abs(dx));
            else
            {
                x = x + 1;
                pk = pk + (2 * abs(dx)) - (2 *abs(dy));
            }

            putpixel(x,y,GREEN);    // display pixel at coordinate (x, y)
            delay(10);
        }

        delay(30);
    }
}

void BresenhamLineDrawingAlgorithm::getCoordinates()
{
    std::cout << "\nEnter the First Coordinate ";
    std::cout << "\nEnter X1 : ";
    std::cin >> x1_;
    std::cout << "\nEnter Y1 : ";
    std::cin >> y1_;
    std::cout << "\nEnter the Second Coordinate ";
    std::cout << "\nEnter X2 : ";
    std::cin >> x2_;
    std::cout << "\nEnter Y2 : ";
    std::cin >> y2_;

}

int main()
{
    BresenhamLineDrawingAlgorithm b;
    b.getCoordinates();
    int gd=DETECT,gm;
    initgraph(&gd,&gm,NULL);
    b.bresenhamLineDrawing();

}

Which line drawing algorithm is faster ?

Bresenham
DDA

Advantage

  • Use of only Addition and Substraction unlike heavy operations in DDA like Multiplication and Division which require special math co-processor to get good performance.

  • No required of additional hardware in Bresenham Line Drawing Algorithm.

  • No need of floor or ceil function for displayn in Bresenham Line Drawing Algorithm.

Complexity

The time and space complexity of Bresenham Line Drawing Algorithm are:

  • Worst case time complexity: ฮ˜(n)
  • Average case time complexity: ฮ˜(n)
  • Best case time complexity: ฮ˜(n)
  • Space complexity: ฮ˜(1)

where N is the number of intermediate point between end and start points.

Further reading

For learn another Line Drawing Algorithm, read: