Try our Free Online Math Solver!

Design of Line Algorithms
Basic Math Review
SlopeIntercept Formula For Lines
Given a third point on the line:
P = (X,Y)
Slope = (Y  Y_{1})/(X  X_{1})
= (Y_{2}  Y_{1})/(X_{2}  X_{1})
Solve for Y
Y = [(Y_{2}Y_{1})/(X_{2}X_{1})]X
+ [(Y_{2}Y_{1})/(X_{2}X_{1})]X_{1} + Y_{1}
or
Y = mx + b
Other Helpful Formulas
Length of line segment between P_{1} and P_{2}:
L = ¦ [ (X_{2}X_{1})^{2} + (Y_{2}Y_{1})^{2} ]
Midpoint of a line segment between P_{1} and P_{3}:
P_{2} = ( (X_{1}+X_{3})/2 , (Y_{1}+Y_{3})/2 )
Two lines are perpendicular iff:
M_{1} = 1/M_{2}
Parametric Form of the Equation
of a 2D Line
Given points P_{1} = (X_{1}, Y_{1}) and P_{2} = (X_{2}, Y_{2})
X = X_{1} + t(X_{2}X_{1})
Y = Y_{1} + t(Y_{2}Y_{1})
When
t = 0 we get (X_{1},Y_{1})
t = 1 we get (X_{2},Y_{2})
As 0 < t < 1, we get all points between (X_{1},Y_{1}) and (X_{2},Y_{2})
Basic Line Algorithm
Must:
1. Compute integer coordinates of pixels which lie on or near a line.
2. Be efficient.
3. Create visually satisfactory images.
• Lines should appear straight
• Lines should terminate accurately
• Lines should have constant density
• Line density should be independent of line length and angle
4. Always be defined.
Simple DDA Line Algorithm
{Based on the parametric equation of a line }
Procedure DDA(X1,Y1,X2,Y2 :Integer); Var Length, I :Integer; X,Y,Xinc,Yinc : Real ; Begin 
For I := 0 To Length Do Begin Plot (Round(X), Round(Y)); X := X + Xinc; Y := Y + Yinc End {For} End; {DDA} 
Creates good lines, but problems ...
DDA Example
Render the line from (6,9) to (11,12):
Length := Max of (ABS(116), ABS(129)) = 5
Xinc := 1
Yinc := 0.6
Values computed are:
(6,9),
(7,9.6),
(8,10.2),
(9,10.8),
(10,11.4),
(11,12)
Fast Lines Using The Midpoint Method
Assumptions: line between points (0,0) and (a,b) with
Recall: y = mx + B (m is the slope, B is the yintercept)
=>m = b/a and B = 0
=>y = (b/a)x + 0
=>f(x,y) = bx  ay = 0
Two choices for next pixel (T or S),
want the pixel closer to line!
Assume distance between
pixel centers is 1
Midpoint is (x_{i} + 1,y_{i} + 1/2)
e is difference between midpoint and where line crosses between
S and T
If e is positive , line crosses above the midpoint and is closer to T
If e is negative , line crosses below the midpoint and is closer to S
=> don’t need exact value of e
Fast Lines  The Decision Variable
Let
d_{i} is known as the decision variable.
Since a ≥ 0, d_{i} has the same sign as e.
Algorithm:
If d_{i} ≥ 0 then
Choose T = (x_{i} + 1, y_{i} + 1) as next point
else
Choose S = (x_{i} + 1, y_{i}) as next point
Fast Line Algorithm
Calculate initial value for d_{0} directly from f(x,y) at (0,0):
d_{0} = f(0 + 1, 0 + 1/2) = b(1)  a(1/2) = b  a/2
Algorithm for a line from (0,0) to (a,b) in the first octant is:
x := 0; y := 0; d := b  a/2; For i := 0 to a do Begin Plot(x,y); If d ≥ 0 Then Begin x := x + 1; y := y + 1; d := d + b  a End 
Else Begin x := x + 1; d := d + b End End 
The only noninteger value is a/2
How can we get rid of it?
Bresenham’s Line Algorithm
Generalize for lines beginning at points other than (0,0)
Begin {Bresenham for lines with slope between 0 and 1} a := ABS(xend  xstart); b := ABS(yend  ystart); d := 2*b  a; Incr1 := 2*(ba); Incr2 := 2*b; If xstart > xend Then Begin x := xend; y := yend End Else Begin x := xstart; y := ystart End; 
For I := 0 to a Do Begin Plot(x,y); x := x + 1; If d ≥ 0 Then Begin y := y + 1; d := d + incr1 End Else d := d + incr2 End {For Loop} End; {Bresenham} 
Optimizations
Detect cycles in the decision variable
=>correspond to a repeated pattern of pixel choices
Save pattern, reuse if a cycle is detected
Antialiasing
Aliasing caused by finite addressability of CRT
Approximation of lines with discrete points can result in a
staircase appearance or "Jaggies"
Antialiasing  Solutions
Aliasing can be smoothed out by using higher addressability.
Problem: addressability usually fixed
Solution: intensity is variable, so use it
=> two adjacent pixels can give impression of point part way
between
=> perceived location of point dependent upon ratio of
intensities
An antialiased line has virtual pixels “located” at the proper
addresses
Antialiased Bresenham Lines
Use the distance (e = d_{i}/a) value to determine pixel intensities.
Three possible cases for the Bresenham algorithm:
What about color?
Prev  Next 