EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 600+ Courses All in One Bundle
  • Login

Line Drawing Algorithm

By Swati TawdeSwati Tawde

Home » Software Development » Software Development Tutorials » Computer Tutorial » Line Drawing Algorithm

Line-Drawing-Algorithm

Introduction to Line Drawing Algorithm

In this article, we will see an outline on the Line Drawing Algorithm. Line drawing on the computer means the computer screen is dividing into two parts rows and columns. Those rows and columns are also known as Pixels. In case we have to draw a line on the computer, first of all, we need to know which pixels should be on. A line is a part of a straight line that extends in the opposite direction indefinitely. The line is defined by two Endpoints. Its density should be separate from the length of the line.
The formula for a line interception of the slope: Y = mx + b
In this formula, m is a line of the slope and b is intercept of y in the line. In positions (x1, y1) and (x2, y2), two endpoints are specified for the line segment.

line segment

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

The value of slope m and b can be determined accordingly
• m = y2 – y1 / x2 – x1
• i.e. M = Δy / Δx

Example: 

Line endpoints are (0,0) and (4,12). Plot the result to calculate each value of y as the x steps of 0 to 4.

Solution: 

So we have a formula of equation of line: Y = mx + b
• m = y2 – y1 / x2 – x1
•m = 12 – 0 / 4 – 0
• m = 3
The y intercept b is then found by linking y1 and x1 to the y = 3 x + b formula, 0 = 3(0) + b. Therefore, b = 0, so the y = 3x line formula.
The goal is to determine the next x, y location as quickly as possible by the previous one.

Types of Line Drawing Algorithm

Below given are the types of the algorithm:

1. Digital Differential Algorithm ( DDA)

An incremental conversion method is a DDA Algorithm and also we called Digital Differential Algorithm (DDA). This approach is characterized by the use of the results from the previous stage in each calculation.

Let us look at the examples given below:

Example #1

End point line are (x1 , y1) and (x2, y2)

Popular Course in this category
All in One Software Development Bundle (600+ Courses, 50+ projects)600+ Online Courses | 3000+ Hours | Verifiable Certificates | Lifetime Access
4.6 (3,144 ratings)
Course Price

View Course

Related Courses
Windows 10 Training (4 Courses, 4+ Projects)JWS Java Web Services Training (4 Courses, 11 Projects)Java Training (40 Courses, 29 Projects, 4 Quizzes)
  • dx = x2 – x1
  • dy = y2 – y1

so, now we will determine the length of the line if abs(dx) >= abs(dy) then length = abs (dx) else length = abs (dy)

  • Δx = dx / length
  • Δy = dy / length
  • X = x1
  • Y = y1

Setpixel (round (x), round (y));

  • i = 1

while ( i <= length )

  • x = x + Δx;
  • y = y + Δy;

setpixel ( round (x) , round (y) );
i = i + 1
end while

Example #2

A line of end points (5, 4) & (6, 9) can be converted with the DDA.

Solution:
• dx = x2 – x1
• dx = 6 – 5 = 1
• dy = y2 – y1
• dy = 9 – 4

dy= 5
As, dx < dy then,
• length = y2 – y1 = 5
• dx = (x2 – x1) / length = 1/5 = 0.2
• dy = (y2- y1) / length = 5/5 = 1
x1 y1 x2 y2 L dx dy i x y

Result:

X1

Y1

X2

Y2

L

Dx

Dy

I

X

Y

Result

3

2

4

7

5

.2

1

0

3.5

5.5

3.5, 5.5

1

3.9

1.5

3.9,1.5

2

4.9

3.5

4.9,3.5

3

5.1

7.5

5.1,7.5

4

3.7

4.5

3.7,4.5

5

4.5

7.5

4.5,7.5

Limitation of DDA Algorithm

  •  Arithmetic for floating and rounding points are time-consuming procedures.
  •  A round-off error may lead to a distance from the true long-line segment path by the measured pixel location.

2. The Bresenham Line Algorithm

The Scan conversion algorithm is Bresenham-algorithm. This algorithm offers the main advantage of using only integer calculations.

1. Endpoints of the row and store the left endpoint in (x1, y1)
2. For the decision parameter to get the first value Δx i.e. Dx, Δy i.e. Dy, 2 Δy and 2 Δx.
3. Initialize starting
4. Initialize i =1 as a counter,
Otherwise, the next point to plot is (xk + 1, yk + 1) and Repeat step 4 ( Δx – 1 ) times.
Adjustment
For m > 1, we can say if we increase x every time we increase y.
After the decision variable pk will be resolved the formula is very similar, only the x and y in the equation will be replaced.

Bresenham Line Algorithm Summary

These are the following advantages to the Bresenham line algorithm:
• A fast incremental algorithm.
• This uses only integer calculations.
DDA has the following problems when compared with the DDA algorithm:
• The pixelated line can be distant from the expected accumulation of round-off errors.
• Time is required for rounding operations and floating points arithmetic.

Recommended Articles

This has been a guide to Line Drawing Algorithm. Here we discuss what is line drawing algorithm along with the various examples. You may also have a look at the following articles to learn more–

  1. Machine Learning Algorithms
  2. SVM Algorithm
  3. Simple Linear Regression
  4. Multivariate Regression

All in One Software Development Bundle (600+ Courses, 50+ projects)

600+ Online Courses

3000+ Hours

Verifiable Certificates

Lifetime Access

Learn More

1 Shares
Share
Tweet
Share
Primary Sidebar
Computer Tutorial
  • Computer Basics
    • New Technologies of Computer
    • Application of Computer Graphics
    • Types of Computer Architecture
    • Types of Computer Software
    • Line Drawing Algorithm
    • SOAP Web Services Interview Questions
    • Web Services Interview Questions
    • Microservices Interview Questions
    • What is Windows 10?
    • Windows 10 Desktop Mode
    • Windows Commands  
    • Windows Interview Questions
    • Windows Networking Commands
    • Windows Operators
    • Windows Server Interview Questions
    • Introduction to Windows
    • Top Windows Phone Apps
    • Windows Monitoring Tool
    • Productivity tricks for Windows 10
    • Computer Network Advantages and Disadvantages
    • Computer Network Interview Questions
    • Introduction To Computer Network
    • What is Embedded Systems
    • Components of Embedded System
    • Embedded Systems Security
    • Types of Computer Network
    • Types of Computer Operating System
    • Evolution of Operating System
    • NAS Storage Device
    • Windows Administrator Interview
    • Types of Communication Network
    • What is Automata
    • Types of Mainframe Computers
    • Types of Computer Hardware
    • Types of Sensors
    • What is Server
    • What is RPC
    • What is Microservices
    • Types of Computer Virus
    • Types of Computer Keyboard
    • Types of Motherboard
    • Sensor Device
    • What is Computer Graphic Design
    • Computer Architecture Interview
    • What is Computer Science?
    • What is Bluetooth?
    • What is VLAN?
    • Types of VLAN
    • Types of LAN
    • How does LAN switches work
    • What is VLAN Network?
    • What is Native VLAN?
    • How does LAN Switches work?
    • Switching Modes
    • What is Storage?
    • What is Object Storage?
    • What is Block Storage?
    • Block Level Storage
    • Cordova Local Storage
    • Threads in Operating System
    • What is Gateway?
    • What is Ethernet?
    • What is Virtual Machine?
    • What is a Trunk Port?
    • VPN Applications for Android
    • What is a NAS Drive?
    • What is Ring Topology?
    • Point to Point Topology
    • What is Mesh Topology?
    • Extended Star Topology
    • Token Ring Topology
    • Physical Topology
    • What is a Hybrid Topology?
    • Hybrid Network Topology
    • Star Network Topology
    • Star Bus Topology
    • Zariski Topology
    • Ethernet Topology
    • Logical Topology
    • Partial Mesh Topology
    • Types of Computer Cables
    • Types of Computer Language
    • Features of Operating System
    • Functions of Operating System
    • Multithreading in Operating System
    • Ethernet Frame Format
    • Types of Memory in Computer
    • What is Heap Memory?
    • What is Register?
    • Types of Registers
    • What is Arduino?
    • Arduino Operators
    • What is iSCSI?
    • Computer Science Interview Questions
    • Types of USB Ports
    • What is Port
    • Daisy Chain Network
    • What is a Monitor?
    • What is Printer?
    • Types of Printers
    • What is WPS
    • What is Mouse?
    • Types of Socket
    • Transmission Modes
    • Computers Output Devices
    • Memory Units
    • Secondary Memory
    • What is Memory Card?
    • Types of Memory Cards
    • What is Intranet?
    • Central Processing Unit
    • Computer Ports
    • What is CPU Register
    • Types of CPU
    • Types of Compact Disc
    • Cache Memory Types
    • What is a Motherboard?
    • Types of LED
    • Types of Processor
    • Types of Primary Memory
    • Helpdesk Tool
    • What is Optical Fiber?

Related Courses

Windows 10 Training Course

Java Web Services Training Course

Java Training Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Java Tutorials
  • Python Tutorials
  • All Tutorials
Certification Courses
  • All Courses
  • Software Development Course - All in One Bundle
  • Become a Python Developer
  • Java Course
  • Become a Selenium Automation Tester
  • Become an IoT Developer
  • ASP.NET Course
  • VB.NET Course
  • PHP Course

© 2020 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA Login

Forgot Password?

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

Special Offer - All in One Software Development Bundle (600+ Courses, 50+ projects) Learn More