Slope-intersept equation for a straight line is
Y=mx+b

**Line Drawing algorithm**

Slope-intersept
equation for a straight line is

Y=mx+b

m- slope
of the line. b-constant

Two end
points of the line segment are (x1,y1) , (x2,y2) Slope m = y2-y1 / x2-x1 --
> Δy/Δx

Δx- x
interval – x2-x1 Δy – y interval – y2-y1

Δy = m.
Δx Δx=Δy/m

If the interval is known, we can find the next point. xi+1= x i+ Δx --
> xi+ Δy/m

yi+1= y
i+ Δy -- > yi+ m. Δx

we sample at unit x interval and y interval then this equation becomes
xi+1= x i+ Δx -- > xi+ (1/m)

yi+1= y
i+ Δy -- > yi+ m.1

The above
equations are for the lines which are processed from left to right.

The
equations are for the lines which are processed from right to left is xi+1= x
i+ Δx -- > xi- (1/m)

yi+1= y
i+ Δy -- > yi- m.1

Since m
can be any real number between 0 and 1 the y value must be rounded to the
nearest integer.

**DDA Algorithm (Digital differential analyze)**

1. Get the
two end points

2. Calculate
the Horizontal and vertical difference between two end points (dx,dy)

3. The
greatest difference value is taken as the length value.

4. Calculate
the step value dx=dx/length, dy=dy / length

5. Start
plotting the line from the first point.

6. Repeat
through 9 step up to length value times

7. if
dx>dy and xa<xb then increment x by 1 and increment y by m

8. if
dx>dy and xa>xb then decrement x by 1 and decrement y by m

9. if
dx<dy ya<yb then increment y by 1 and increment x by 1/m

10.
if dx<dy and ya>yb then decrement y by 1 and
decrement x by 1/m

**DDA Line Algorithm**

It
generates lines from their differencial equations.

**Advantages**

1. It is the
faster method for calculating pixel positions.

2. It is
simplest algorithm.It does not require special skills for implementation.

**Disadvantages**

Floating
point arithmetic in DDA algorithm is still time consuming

The
algorithm is orientation dependent.Hence end point accuracy is poor.

**Bresenham’s Line Algorithm**

This
algorithm uses only integer addition, subtraction, and multiplication by 2. So
it is efficient for scan converting algorithms. This algorithm increments
either x or y by one unit depending on the slope of the line. The increment in
the other variable is determined by examine the distance between the actual
line location and the nearest pixel. This distance is called **decision variable **or the** error.**

In matemetical terms the error or decision variable
is defined as e = Db – Da

If e>0
then the pixel above the line is closer to the true line.

Else the
pixel below the line is closer to the true line.

Assume
the current pixel is (xk,yk)

We have
to find the next pixel position either ((xk+1,yk) and (xk+1,yk+1) The y
coordinate on the line at the pixel position xk+1 Is y = m (xk+1 ) + c Then the
distance d1= y - yk = m (xk+1 ) + c-yk

d2=
(yk+1-y)= yk+1-m (xk+1 ) + c

d1-d2 = m (xk+1) + c-yk -yk--1-(yk+1)+m (xk+1 ) + c
= 2m (xk+1)-2 yk +2c-1

The error
term is initially set as e = 2Δy-Δx where Δy=y2-y1 , Δx=x2-x1

**Bresenhams algorithm**

1. Get the
two end points

2. Calculate
the values dx,dy,2dy and 2dy-2dx where dx=X2-X1 and dy=Y2-Y1

3. Calculate
the starting decision parameter d=2dy-dx

4. plot the
first point

5. 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 Otherwise the
next point to plot is (Xk+1,Yk+1) Pk+1=pk+2dy-2dx 6. Repeat step 5 for dx
times.

The
following program is used to for generalized bresenham algorithm, which will
work for all the four coordinates.

**Parallel Line algorithm**

We can
calculate the pixel position along the path simultaneously by partitioning the
computations among the various processors available. One approach to the
partitioning problem is to adapt an exsisting sequential algorithm to take
advantage of multiple processors. Alternatively, we can look for other ways to
set up the processing so that pixel positions can be calculated efficiently in
parallel.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.