Question
• What is an algorithm?
Plotting points and lines
• Plotting points
Illuminate a phosphor dot on a CRT
• Plotting lines
i. Specify the endpoint coordinates of each
line segment
ii. Fill the straight line path between the
end-points
• Line drawing is accomplished by calculating
intermediate positions along the line path between
two specified end point positions.
• An output device is then directed to fill in these
positions between the end points
• Discrete coordinate positions along the line path are
calculated from the equation of the line.
Line /Circle drawing Drawing
Algorithms
• Digital Differential Analyzer (DDA)
Algorithm
• Bresenham’s Line Algorithm
• Bresenham's Circle Drawing Algorithm
: know the algorithm and apply it given end
coordinates.
The DDA algorithm
1. The DDA Algorithm
Algorithm Description:
Step 1 : Accept Input as two endpoint pixel positions
Step 2: Horizontal and vertical differences between the endpoint positions are
assigned to parameters dx and dy (Calculated dx= xb - xa and dy = yb - ya).
Step 3: The difference with the greater magnitude determines the value of
parameter steps.
Step 4 : Starting with pixel position (xa, ya), determine the offset (m) needed at
each step to generate the next pixel position along the line path.
Step 5: Loop the following process for steps number of times
• a. Use a unit of increment or decrement in the x and y direction
• b. if xa is less than xb the values of increment in the x and y directions are 1 and
m
• c. if xa is greater than xb then the decrements -1 and – m are used.
Example : Consider the line from (0,0) to
(4,6)
1. xa=0, ya =0 and xb=4 yb=6
2. dx=xb-xa = 4-0 = 4 and
dy=yb-ya=6-0= 6
3. x=0 and y=0
4. 4 > 6 (false) so, steps (m) =6
5. Calculate xIncrement = dx/steps = 4 / 6 = 0.66 and yIncrement = dy/steps =6/6=1
6. Iterate the calculation for xIncrement and yIncrement for steps(6)
{yk+1 = yk + m ; xk+1 = xk + (1/m) } or
{yk+1 = yk – m ; xk+1 = xk-1(1/m) for Δx=-1 }
8. Tabulation of the each iteration
DDA
Advantages of DDA
• 1. It is the simplest algorithm
• 2. It is a is a faster method for calculating pixel
positions
Disadvantages of DDA Algorithm
• 1. Floating point arithmetic in DDA algorithm is
still time-consuming
• 2. End point accuracy is poor
Practice Question
• Explain the stages of the DDA algorithm,
and use it to plot the line from point (1,1)
to (5,7)
[10]
Bresenham Line-Drawing algorithm
2. Bresenham Line Algorithm
• A more efficient approach
• Basis of the algorithm:
Start position
• From start position decide A or B next 14
In general:
Note:
• For a line with gradient 1
d0 = 2dx – dy
if di 0 then xi+1 = xi
di+1 = di + 2dx
if di ≥ 0 then xi+1 = xi + 1
di+1 = di + 2(dx – dy)
yi+1 = yi + 1
16
Bresenham Line Drawing
To illustrate the algorithm, we digitize the line with endpoints (20, 10) and (30, 18).
This line has a slope of 0.8, with
∆x = 10, ∆ y =8
The initial decision parameter has the value:
p0 = 2 ∆ y − ∆ x =6
and the increments for calculating successive decision parameters are
2 ∆ y = 16, 2 ∆ y − 2 ∆ x = −4
We plot the initial point (x0, y0) = (20, 10), and determine successive pixel positions
along the line path from the decision parameter as:
Bresenham Line Drawing
Practice Question
• Use Bresenham’s line drawing algorithm to
draw a line from point (1,1) to (5,7).
• Use Bresenham’s line drawing algorithm to draw a
line from point (5,5) to (15,20).
3. Bresenham’s Circle algorithm
• Step through x-axis to determine y-
values
21
Circle Algorithms
• Use 8-fold symmetry and only compute pixel
positions for the 45° sector.
(-x, y) (x, y)
(-y, x) (y, x)
45°
(-y, -x) (y, -x)
(-x, -y) (x, -y)
22
Bresenham’s Circle Algorithm
p1 p3
yi
D(si)
yi - 1 D(ti)
p2
xi xi + 1
After point p1, do we choose p2 or p3?
x0 = 0
y0 = r
p0 = 3 – 2r
if pi < 0 then
yi+1 = yi
pi+1 = pi + 4xi + 6
xi+1 = xi + 1
else if pi ≥ 0 then
yi+1 = yi – 1
pi+1 = pi + 4(xi – yi) + 10
• Stop when xi ≥ yi and determine symmetry points in the
other octants
24
r = 10
p0 = 3 – 2r = -17
Initial point (x0, y0) = (0, 10)
10
i pi xi, yi 9
0 -17 (0, 10) 8
7
1 -11 (1, 10)
6
2 -1 (2, 10)
5
3 13 (3, 10) 4
4 -5 (4, 9) 3
5 17 (5, 9) 2
1
7
0
0 1 2 3 4 5 6 7 8 9 10
25
• Draw the circle with r = 12 using the
Bresenham algorithm.
• Draw the circle with r = 14 and center at (15,
10).
26
