**What are Line Drawing Algorithms?**- “The Line drawing algorithm is a graphical algorithm that is used to represent the line segment on discrete graphical media, i.e., printer and pixel-based media.” A line contains two points The point is an important element of a line. A line algorithm is a method for estimating a line segment on discrete graphical media such as pixel-based screens and printers in graphics.
- Lines are rasterized in one color using basic methods. Spatial anti-aliasing is a sophisticated approach that allows for a better representation of
- numerous color gradations.
- To draw a line on a continuous medium, however, no algorithm is required. Cathode-ray
- oscilloscopes, for example, use analog phenomena to create lines and curves.
- The formula for a slope line interception is:
- Y = mx + b
- In this formula, m is the slope line and b is the line’s intercept of y.
- Two endpoints for the line segment are supplied in coordinates (x1, y1) and (x2, y2).
- In this formula, m is the slope line and b is the line’s intercept of y.
- Two endpoints for the line segment are supplied in coordinates (x1, y1) and (x2, y2).

- Properties of a Line Drawing Algorithm:
**Input: At least one or more inputs must be accepted a good algorithm. Output: At least one output must produce**an algorithm. An algorithm should be precise: - The algorithm’s each step must well-define.
- Finiteness: Finiteness is required in an algorithm. It signifies that the algorithm will come to a halt once all of the steps have been completed.
- Correctness: An algorithm must implement correctly.
- Uniqueness: The result of an algorithm should be based on the given input and all steps of the algorithm should be clearly and uniquely defined.
- Effectiveness: An algorithm’s steps must be correct and efficient.
- Easy to understand: Learners must be able to understand the solution in a more natural way thanks to an algorithm.
**Characteristics of Line Drawing Algorithm:**- The line should appear Straight:
- We must appropriate the line by choosing addressable points close to it.
- If we choose well, the line will appear straight, if not, we shall produce crossed lines.

- The lines must be generated parallel or at 45° to the x and y-axes.
- Other lines cause a problem: a line segment through it starts and finishes at addressable points, may happen to pass through no other addressable point in between.

- Lines should have constant density:
- Line density is proportional to the no. of dots displayed divided by the length of the line.
- To maintain constant density, dots should be equally spaced.
- Line density should be independent of line length and angle:
- This can be done by computing an approximating line-length estimate and using a line generation algorithm that keeps line density constant to within the accuracy of this estimate.
- The line should be drawn rapidly: This computation should be performed by special-purpose hardware.

**DDA algorithm**

DDA stands for Digital Differential Analyzer.

It is an incremental method of scan conversion of line. In this method calculation is

performed at each step but by using results of previous steps.

We sample the line at unit intervals in one coordinate and find corresponding integer values

nearest the line path for the other coordinate.

Consider first a line with positive slope and slope is less than or equal to We sample at unit x

interval (Ax= 1) and calculate each successive y value as follow:

The line of equation for step i

Yi = mxi+b………………….equation 1

Next value will be

yi+1=mxi+1+b……………..equation 2

m = DDA Algorithm

yi+1-yi = ∆y…………………..equation 3 yi+1-xi = ∆x………………….equation 4 yi+1 = yi+∆y ∆y = m∆x yi+1 = yi+m∆x ∆x = ∆y/m Case1: When |M|<1 then (assume that x12) x = x1, y = y1 set ∆x = 1 yi+1 = y1+m, x = +1 Until x = x2 Case2: When |M|<1 then (assume that y12) x = x1, y = y1 set ∆y = 1 xi+1 = DDA Algorithm, y=y+1 Until y → y2 DDA Algorithm:

Void lineDDA (int xa, int ya, int xb, int yb) { int dx = xb – xa, dy = yb – ya, steps, k; float xincrement, yincrement, x = xa, y = ya; if (abs(dx)>abs(dy)) { Steps = abs (dx); } else { Steps = abs (dy); } xincrement = dx/(float) steps; yincrement = dy/(float) steps; setpixel (ROUND (x), ROUND (y)); for (k=0; k<steps; k++) {

x += xincrement;

y += yincrement;

setpixel (ROUND (x), ROUND (y));

}

Steps of Algorithms

Step1: Start Algorithm

Step2: Declare x1, y1, x2, y2, dx, dy, x, y as integer variables.

Step3: Enter value of x1, y1, x2, y2.

Step4: Calculate dx = x2-x1

Step5: Calculate dy = y2-y1

Step6: If ABS (dx) > ABS (dy)

Then step = abs (dx) Else

Step7: xinc = dx/step

yinc = dy/step

assign x = x1

assign y = y1

Step8: Set pixel (x, y)

Step9: x = x + xinc

y = y + yinc

Set pixels (Round (x), Round (y))

Step10: Repeat step 9 until x = x2

Step11: End Algorithm

**Advantage:**- It is a faster method than method of using direct use of line equation.
- This method does not use multiplication theorem.
- It allows us to detect the change in the value of x and y, so plotting of same point twice is
- not possible.
- This method gives overflow indication when a point is repositioned. It is an easy method because each step involves just two additions.
- Disadvantage:
- It involves floating point additions rounding off is done. Accumulations of round-off error cause accumulation of error.
- Rounding-off operations and floating point operations consume a lot of time.
- It is more suitable for generating lines using the software. But it is less suited for hardware implementation.