Editing Bresenham's line algorithm (section)

=== Algorithm for integer arithmetic ===
Alternatively, the difference between points can be used instead of evaluating f(x,y) at midpoints. This alternative method allows for integer-only arithmetic, which is generally faster than using floating-point arithmetic. To derive the other method, define the difference to be as follows: 
:<math>
D_i = f(x_i+1,y_i+\tfrac 1 2) - f(x_0,y_0)
</math>
For the first decision, this formulation is equivalent to the midpoint method since <math>f(x_0,y_0)=0</math> at the starting point. Simplifying this expression yields:
:<math>\begin{array}{rclcl}
D_0 & = & \left[ A(x_0+1) + B \left(y_0+\frac{1}{2}\right) + C \right] & - & \left[ A x_0 + B y_0 + C \right] \\
& = & \left[ Ax_0 + B y_0+ C + A + \frac {1}{2} B\right]  & - & \left[ A x_0 + B y_0 + C \right] \\
& = & A + \frac{1}{2} B = \Delta y - \frac{1}{2} \Delta x
\end{array}</math>

Just as with the midpoint method, if <math>D_0</math> is positive, then choose <math>(x_0+1,y_0+1)</math>, otherwise choose <math>(x_0+1,y_0)</math>.

If <math>(x_0+1,y_0)</math> is chosen, the change in <math>D_i</math> will be: 
:<math>\begin{array}{lclcl}
\Delta D &=& f(x_0+2,y_0+\tfrac 1 2) - f(x_0+1,y_0+\tfrac 1 2) &=& A &=& \Delta y \\
\end{array}</math>
If <math>(x_0+1,y_0+1)</math> is chosen the change in <math>D_i</math> will be:
:<math>\begin{array}{lclcl}
\Delta D &=& f(x_0+2,y_0+\tfrac 3 2) - f(x_0+1,y_0+\tfrac 1 2) &=& A+B &=& \Delta y - \Delta x
\end{array}</math>

If the new D is positive then <math>(x_0+2,y_0+1)</math> is chosen, otherwise <math>(x_0+2,y_0)</math>. This decision can be generalized by accumulating the error on each subsequent point.

[[File:Line 1.5x+1 -- points.svg|300px|thumb|Plotting the line from (0,1) to (6,4) showing a plot of grid lines and pixels]]

All of the derivation for the algorithm is done.  One performance issue is the 1/2 factor in the initial value of D.  Since all of this is about the sign of the accumulated difference, then everything can be multiplied by 2 with no consequence.

This results in an algorithm that uses only integer arithmetic.

 plotLine(x0, y0, x1, y1)
     dx = x1 - x0
     dy = y1 - y0
     D = 2*dy - dx
     y = y0
 
     '''for''' x from x0 to x1
         plot(x, y)
         '''if''' D > 0
             y = y + 1
             D = D - 2*dx
         '''end if'''
         D = D + 2*dy

Running this algorithm for <math>f(x,y) = x-2y+2</math> from (0,1) to (6,4) yields the following differences with dx=6 and dy=3:

 D=2*3-6=0
 Loop from 0 to 6
  * x=0: '''plot(0, 1)''', D≤0: D=0+6=6
  * x=1: '''plot(1, 1)''', D>0: D=6-12=-6, y=1+1=2, D=-6+6=0
  * x=2: '''plot(2, 2)''', D≤0: D=0+6=6
  * x=3: '''plot(3, 2)''', D>0: D=6-12=-6, y=2+1=3, D=-6+6=0
  * x=4: '''plot(4, 3)''', D≤0: D=0+6=6
  * x=5: '''plot(5, 3)''', D>0: D=6-12=-6, y=3+1=4, D=-6+6=0
  * x=6: '''plot(6, 4)''', D≤0: D=0+6=6

The result of this plot is shown to the right.  The plotting can be viewed by plotting at the intersection of lines (blue circles) or filling in pixel boxes (yellow squares).  Regardless, the plotting is the same.