Line Drawing Techniques
There are three techniques to be discussed to draw a line
involving different time complexities that will be discussed
along. These techniques are:
▪ DDA line algorithm
▪ Midpoint line algorithm
DDA
Problem
Draw a line from (1,1) to (8,7) using DDA
Disadvantage
Use of floating point calculation
An algorithm based on integer type calculations is likely to be
more efficient
2- Midpoint Algorithm for line plotting
midpoint algorithm finds the closest integer coordinates to
the actual line, using only integer math. Assuming that the
slope is positive and less than 1, moving 1 step in the x
direction, y either stays the same, or increases by 1. A
decision function is required to resolve this choice.
Midpoint Algorithm
midpoint algorithm finds the closest integer coordinates to the
actual line, using only integer math.
Assuming that:
the slope is positive and less than 1,
moving 1 step in the x direction,
y either stays the same, or increases by 1.
Midpoint Algorithm
Which pixel
should be
plotted
next? NE
–East?
–Northeast? E
Midpoint Algorithm
Which pixel should
be plotted next?
– East?
f <0
– Northeast?
Line equation
NE
y = mx + b
f(x,y) = mx + b – y f>0
M
E
Midpoint Algorithm
Which pixel should be
plotted next?
– East?
– Northeast? f <0
Line equation
NE
y = mx +b
f >0
M
E
y = mx + B.
y = (dy/dx)x + B or (dy)x + B(dx) - y(dx) = 0
Let F(x, y) = (dy)x - y(dx) + B(dx) -----(1)
-> For all points (x,y) on the line,
the solution to F(x, y) is 0.
-> For all points (x,y) above the line,
F(x, y) result in a negative number.
-> And for all points (x,y) below the line,
F(x, y) result in a positive number.
Midpoint Algorithm
Which pixel should be
plotted next?
– East?
– Northeast? f <0
Line equation
NE
y = mx +b
f >0
M
E
Calculation For initial value of decision parameter d0:
d0 = F(X1+1 , Y1+1/2)
= a(X1 + 1) + b(Y1 + 1/2) +c
= aX1+ bY1 + c + a + b/2
= F(X1,Y1) + a + b/2
= a + b/2 (as F(X1, Y1) = 0 )
d0 = dy – dx/2. (as a = dy, b = -dx)
Mid-Point Algorithm
Evaluate d for next pixel, Depends on whether E or NE Is chosen :
If E chosen :
1 1
d new = F ( x p + 2, y p + ) = a( x p + 2) + b( y p + ) + c
2 2
But recall :
NE
E So :
Previous Choices for
Pixel Choices for Next pixel d new = d old + dy
(xp,yp) Current pixel
Case 1: If E is chosen then for next point :
dnew = F(Xp+2, Yp+1/2)
= a(Xp+2) + b(Yp+1/2) + c
dold = a(Xp+1) + b(Yp+1/2) + c
Difference (Or delta) of two distances:
DELd = dnew – dold
= a(Xp+2)- a(Xp+1)+ b(Yp+1/2)- b(Yp+1/2)+ c-c
= a(Xp) +2a – a(Xp) – a
= a.
Therefore, dnew = dold + dy. (as a = dy)
Decision variable.
If NE was chosen :
3 3
d new = F ( x p + 2, y p + ) = a( x p + 2) + b( y p + ) + c
2 2
M So :
NE
d new = d old + dy − dx
E
Previous Choices for
Pixel Choices for Next pixel
(xp,yp) Current pixel
Case 2: If NE is chosen then for next point :
dnew = F(Xp+2, Yp+3/2)
= a(Xp+2) + b(Yp+3/2) + c
dold = a(Xp+1) + b(Yp+1/2) + c
Difference (Or delta) of two distances:
DELd = dnew –dold
= a(Xp+2)- a(Xp+1)+ b(Yp+3/2)- b(Yp+1/2)+ c-c
= a(Xp) + 2a – a(Xp) – a + b(Yp) + 3/2b – b(Yp) -1/2b
=a+b
Therefore, dnew = dold + dy – dx. (as a = dy , b = -dx)
Algorithm
Input (X1,Y1) and (X2,Y2)
dy = Y2- Y1 dx = X2 - X1
// initial value of decision parameter d
d = dy - (dx/2)
x = X1 , y = Y1
// plot initial given point
Plot(x , y)
// iterate through value of X
while(x < X2)
x = x+1
if (d < 0) // 'E' is chosen
d = d + dy
else // 'NE' is chosen
d = d + dy - dx
y = y+1
Plot(x,y)
Summary of mid-point
algorithm
Choose between 2 pixels at each step
based upon the sign of a decision
variable.
Update the decision variable based upon
which pixel is chosen.
Start point is simply first endpoint (x y ).
1, 1
Need to calculate the initial value for d
Line drawing Exercise
Go through the steps of the Midpoint
drawing algorithm for a line going
from (4,8) to (9,12)
(4,8) to (9,12)
E:
d new = d old + dy
SE :
d new = d old + dy − dx
Line drawing Exercise
Go through the steps of the Midpoint
drawing algorithm for a line going
from (2,2) to (8,5)
(2,2) to (8,5)
E:
d new = d old + dy
SE :
d new = d old + dy − dx