## Line Drawing Algorithms-

In computer graphics, popular algorithms used to generate lines are-

1. Digital Differential Analyzer (DDA) Line Drawing Algorithm
2. Bresenham Line Drawing Algorithm
3. Mid Point Line Drawing Algorithm

## DDA Algorithm-

DDA Algorithm is the simplest line drawing algorithm.

 Given the starting and ending coordinates of a line,DDA Algorithm attempts to generate the points between the starting and ending coordinates.

### Procedure-

Given-

• Starting coordinates = (X0, Y0)
• Ending coordinates = (Xn, Yn)

The points generation using DDA Algorithm involves the following steps-

### Step-01:

Calculate ΔX, ΔY and M from the given input.

These parameters are calculated as-

• ΔX = Xn – X0
• ΔY =Yn – Y0
• M = ΔY / ΔX

### Step-02:

Find the number of steps or points in between the starting and ending coordinates.

if (absolute (ΔX) > absolute (ΔY))

Steps = absolute (ΔX);

else

Steps = absolute (ΔY);

### Step-03:

Suppose the current point is (Xp, Yp) and the next point is (Xp+1, Yp+1).

Find the next point by following the below three cases-

### Step-04:

Keep repeating Step-03 until the end point is reached or the number of generated new points (including the starting and ending points) equals to the steps count.

## Problem-01:

Calculate the points between the starting point (5, 6) and ending point (8, 12).

## Solution-

Given-

• Starting coordinates = (X0, Y0) = (5, 6)
• Ending coordinates = (Xn, Yn) = (8, 12)

### Step-01:

Calculate ΔX, ΔY and M from the given input.

• ΔX = Xn – X0 = 8 – 5 = 3
• ΔY =Yn – Y0 = 12 – 6 = 6
• M = ΔY / ΔX = 6 / 3 = 2

### Step-02:

Calculate the number of steps.

As |ΔX| < |ΔY| = 3 < 6, so number of steps = ΔY = 6

### Step-03:

As M > 1, so case-03 is satisfied.

Now, Step-03 is executed until Step-04 is satisfied.

 Xp Yp Xp+1 Yp+1 Round off (Xp+1, Yp+1) 5 6 5.5 7 (6, 7) 6 8 (6, 8) 6.5 9 (7, 9) 7 10 (7, 10) 7.5 11 (8, 11) 8 12 (8, 12)

## Problem-02:

Calculate the points between the starting point (5, 6) and ending point (13, 10).

## Solution-

Given-

• Starting coordinates = (X0, Y0) = (5, 6)
• Ending coordinates = (Xn, Yn) = (13, 10)

### Step-01:

Calculate ΔX, ΔY and M from the given input.

• ΔX = Xn – X0 = 13 – 5 = 8
• ΔY =Yn – Y0 = 10 – 6 = 4
• M = ΔY / ΔX = 4 / 8 = 0.50

### Step-02:

Calculate the number of steps.

As |ΔX| > |ΔY| = 8 > 4, so number of steps = ΔX = 8

### Step-03:

As M < 1, so case-01 is satisfied.

Now, Step-03 is executed until Step-04 is satisfied.

 Xp Yp Xp+1 Yp+1 Round off (Xp+1, Yp+1) 5 6 6 6.5 (6, 7) 7 7 (7, 7) 8 7.5 (8, 8) 9 8 (9, 8) 10 8.5 (10, 9) 11 9 (11, 9) 12 9.5 (12, 10) 13 10 (13, 10)

## Problem-03:

Calculate the points between the starting point (1, 7) and ending point (11, 17).

## Solution-

Given-

• Starting coordinates = (X0, Y0) = (1, 7)
• Ending coordinates = (Xn, Yn) = (11, 17)

### Step-01:

Calculate ΔX, ΔY and M from the given input.

• ΔX = Xn – X0 = 11 – 1 = 10
• ΔY =Yn – Y0 = 17 – 7 = 10
• M = ΔY / ΔX = 10 / 10 = 1

### Step-02:

Calculate the number of steps.

As |ΔX| = |ΔY| = 10 = 10, so number of steps = ΔX = ΔY = 10

### Step-03:

As M = 1, so case-02 is satisfied.

Now, Step-03 is executed until Step-04 is satisfied.

 Xp Yp Xp+1 Yp+1 Round off (Xp+1, Yp+1) 1 7 2 8 (2, 8) 3 9 (3, 9) 4 10 (4, 10) 5 11 (5, 11) 6 12 (6, 12) 7 13 (7, 13) 8 14 (8, 14) 9 15 (9, 15) 10 16 (10, 16) 11 17 (11, 17)

The advantages of DDA Algorithm are-

• It is a simple algorithm.
• It is easy to implement.
• It avoids using the multiplication operation which is costly in terms of time complexity.

The disadvantages of DDA Algorithm are-

• There is an extra overhead of using round off( ) function.
• Using round off( ) function increases time complexity of the algorithm.
• Resulted lines are not smooth because of round off( ) function.
• The points generated by this algorithm are not accurate.

To gain better understanding about DDA Algorithm,

Watch this Video Lecture

Next Article- Bresenham Line Drawing Algorithm

Get more notes and other study material of Computer Graphics.

Watch video lectures by visiting our YouTube channel LearnVidFun.
The text passage describes the Digital Differential Analyzer (DDA) Line Drawing Algorithm, including its procedure and several problems with solutions that demonstrate how to calculate the points between the starting and ending coordinates of a line.
multiple_questions_with_answers
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
## Line Drawing Algorithms-

In computer graphics, popular algorithms used to generate lines are-

1. Digital Differential Analyzer (DDA) Line Drawing Algorithm
2. Bresenham Line Drawing Algorithm
3. Mid Point Line Drawing Algorithm

## DDA Algorithm-

DDA Algorithm is the simplest line drawing algorithm.

 Given the starting and ending coordinates of a line,DDA Algorithm attempts to generate the points between the starting and ending coordinates.

### Procedure-

Given-

• Starting coordinates = (X0, Y0)
• Ending coordinates = (Xn, Yn)

The points generation using DDA Algorithm involves the following steps-

### Step-01:

Calculate ΔX, ΔY and M from the given input.

These parameters are calculated as-

• ΔX = Xn – X0
• ΔY =Yn – Y0
• M = ΔY / ΔX

### Step-02:

Find the number of steps or points in between the starting and ending coordinates.

if (absolute (ΔX) > absolute (ΔY))

Steps = absolute (ΔX);

else

Steps = absolute (ΔY);

### Step-03:

Suppose the current point is (Xp, Yp) and the next point is (Xp+1, Yp+1).

Find the next point by following the below three cases-

### Step-04:

Keep repeating Step-03 until the end point is reached or the number of generated new points (including the starting and ending points) equals to the steps count.

## Problem-01:

Calculate the points between the starting point (5, 6) and ending point (8, 12).

## Solution-

Given-

• Starting coordinates = (X0, Y0) = (5, 6)
• Ending coordinates = (Xn, Yn) = (8, 12)

### Step-01:

Calculate ΔX, ΔY and M from the given input.

• ΔX = Xn – X0 = 8 – 5 = 3
• ΔY =Yn – Y0 = 12 – 6 = 6
• M = ΔY / ΔX = 6 / 3 = 2

### Step-02:

Calculate the number of steps.

As |ΔX| < |ΔY| = 3 < 6, so number of steps = ΔY = 6

### Step-03:

As M > 1, so case-03 is satisfied.

Now, Step-03 is executed until Step-04 is satisfied.

 Xp Yp Xp+1 Yp+1 Round off (Xp+1, Yp+1) 5 6 5.5 7 (6, 7) 6 8 (6, 8) 6.5 9 (7, 9) 7 10 (7, 10) 7.5 11 (8, 11) 8 12 (8, 12)

## Problem-02:

Calculate the points between the starting point (5, 6) and ending point (13, 10).

## Solution-

Given-

• Starting coordinates = (X0, Y0) = (5, 6)
• Ending coordinates = (Xn, Yn) = (13, 10)

### Step-01:

Calculate ΔX, ΔY and M from the given input.

• ΔX = Xn – X0 = 13 – 5 = 8
• ΔY =Yn – Y0 = 10 – 6 = 4
• M = ΔY / ΔX = 4 / 8 = 0.50

### Step-02:

Calculate the number of steps.

As |ΔX| > |ΔY| = 8 > 4, so number of steps = ΔX = 8

### Step-03:

As M < 1, so case-01 is satisfied.

Now, Step-03 is executed until Step-04 is satisfied.

 Xp Yp Xp+1 Yp+1 Round off (Xp+1, Yp+1) 5 6 6 6.5 (6, 7) 7 7 (7, 7) 8 7.5 (8, 8) 9 8 (9, 8) 10 8.5 (10, 9) 11 9 (11, 9) 12 9.5 (12, 10) 13 10 (13, 10)

## Problem-03:

Calculate the points between the starting point (1, 7) and ending point (11, 17).

## Solution-

Given-

• Starting coordinates = (X0, Y0) = (1, 7)
• Ending coordinates = (Xn, Yn) = (11, 17)

### Step-01:

Calculate ΔX, ΔY and M from the given input.

• ΔX = Xn – X0 = 11 – 1 = 10
• ΔY =Yn – Y0 = 17 – 7 = 10
• M = ΔY / ΔX = 10 / 10 = 1

### Step-02:

Calculate the number of steps.

As |ΔX| = |ΔY| = 10 = 10, so number of steps = ΔX = ΔY = 10

### Step-03:

As M = 1, so case-02 is satisfied.

Now, Step-03 is executed until Step-04 is satisfied.

 Xp Yp Xp+1 Yp+1 Round off (Xp+1, Yp+1) 1 7 2 8 (2, 8) 3 9 (3, 9) 4 10 (4, 10) 5 11 (5, 11) 6 12 (6, 12) 7 13 (7, 13) 8 14 (8, 14) 9 15 (9, 15) 10 16 (10, 16) 11 17 (11, 17)

The advantages of DDA Algorithm are-

• It is a simple algorithm.
• It is easy to implement.
• It avoids using the multiplication operation which is costly in terms of time complexity.

The disadvantages of DDA Algorithm are-

• There is an extra overhead of using round off( ) function.
• Using round off( ) function increases time complexity of the algorithm.
• Resulted lines are not smooth because of round off( ) function.
• The points generated by this algorithm are not accurate.

To gain better understanding about DDA Algorithm,

Watch this Video Lecture

Next Article- Bresenham Line Drawing Algorithm

Get more notes and other study material of Computer Graphics.

Watch video lectures by visiting our YouTube channel LearnVidFun.
user
The text passage describes the Digital Differential Analyzer (DDA) Line Drawing Algorithm, including its procedure and several problems with solutions that demonstrate how to calculate the points between the starting and ending coordinates of a line.

TYPE: MULTIPLE_QUESTIONS_WITH_ANSWERS