Home » Algorithms

Line Drawing Algorithm



In this article, we are going to learn about Line-Drawing algorithms by DDA (Digital Differential analyzer) algorithms and Bresenham’s algorithm in computer graphics.
Submitted by Abhishek Kataria, on July 27, 2018

Line drawing algorithms

  • The equation for a straight line is y=mx+b
  • In this m represent a slope of a line which can be calculated by the m=y2-y1/x2-x1 where (x1, y1) are the starting position of the points and (x2, y2) are the end positions of the points.
  • There are generally three cases arises, which are:
    1. If an angle is greater than 45 degree then it means the slope is greater than 1 which also mean that dy/dx>1.
    2. If an angle is less than 45 degree then it means the slope is less than 1 which also mean that dy/dx<1.
    3. If an angle is equal to 45 degrees then it means the slope is 1 which also means that dy/dx=1.
  • The increment in x can be calculated by the x2-x1 divided by a total number of steps. Similarly increment of y can be calculated by the y2-y1 divided by the total number of steps.

DDA Algorithm

This is a line drawing algorithm which is named as Digital Differential Analyzer (DDA). Basically, it uses the floor function which takes the extra time for generating a line. The DDA algorithm is a faster method for calculating a pixel position for a direct use of it. In some cases, the line drawn by the DDA algorithm is not smooth.

    Algorithm DDA (x1, y1, x2, y2)
    {
        dx=x2-x1;
        dy=y2-y1;

        if (abs(dx)>abs(dy))
            step=abs(dx)
        else
            step=abs(dy)
    
        x increment= dx/step
        y increment= dy/step
    
        for(i=1;i<=step;i++)
        {
            putpixel (x1,y1);
            x1=x1+increment;
            y1=y1+increment;
        }
    }



Conclusion:

In this algorithm for finding a position of a point, there can be an increment in both x coordinate or can be in a y coordinate. On the basis of it, there are three cases generated which are as given below:

  1. If the value of m is less than 1, then x=x+1 and y=y+m.
  2. If the value of m is greater than 1, then x=x+m and y=y+1.
  3. If the value of m is equal to 1, then x=x and y=y.

Bresenham’s Algorithm

This is an algorithm which is used for drawing a line accurately and efficiently which was developed by Bresenham’s. Here generally, decision parameter is used for finding the next value from the initial one. According to this algorithm value of x will always be incremented but the value of y will be incremented or not it depends upon the decision parameter. This is a faster algorithm and less expensive to implement. There are no criteria of a round of the value in this algorithm which makes this algorithm faster and accurate.

Steps for implementing Bresenham’s algorithm:

    1.	Read the end points (x1, y1) and (x2, y2).
    2.	dx=x2-x1 
        dy=y2-y1
    3.	x=x1, y=y1
    4.	e=2dy-dx where, e is a decision parameter.
    5.	While(e>=0)
        {
          y=y+1
          e=e-2dx
        }
        X=x+1
        e=e+2dy
    6.	i<=dx , here i is only dependent upon the value of x. 





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.




Quick links
Latest articles, Internship, Members
New...
Coding problems, Algorithms, Discrete Mathematics, Big data
Languages
C, C++, C++ STL, Java, Data Structure, C#.Net, Android, Kotlin, SQL
Web
PHP, Python, JavaScript, CSS, Ajax, Node.js, Web prog.
Programs
C, C++, DS, Java, C#, Python
Aptitude
C, C++, Java, DBMS
Interview
C, Embedded C, Java, SEO, HR
CS Subjects
CS Basics O.S. Networks DBMS Embedded Systems Cloud Computing Machine learning CS Organizations Linux DOS
More...
Articles, Puzzles, News/Updates


Recommended posts
C Tips & Tricks, C++ Tips & Tricks
Introduction to Linux (Its modes, Safety, Most popular Applications)
Linux Best Distros of 2018
C programming optimization techniques
Differences b/w C & Embedded C?
Embedded C Interview Q. & A.
C programming tips for Embedded Development
Basic rules of writing a C program
Important points (rules) to remember while writing C/C++ program
Top 5 Websites for solving programming challenges
Read more...


Others...
Computer G.K. (MCQ)
Most viewed pages...
Categories...



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.