Bresenham's Line Algorithm - Derivation - Algorithm

Algorithm

Clearly, the starting point is on the line

only because the line is defined to start and end on integer coordinates (though it is entirely reasonable to want to draw a line with non-integer end points).

Keeping in mind that the slope is less-than-or-equal-to one, the problem now presents itself as to whether the next point should be at or . Perhaps intuitively, the point should be chosen based upon which is closer to the line at . If it is closer to the former then include the former point on the line, if the latter then the latter. To answer this, consider the midpoint between these two points:

If the value of this is negative then the midpoint lies above the line, and if the value of this is positive then the midpoint lies below the line. If the midpoint lies below the line then should be chosen since it is closer; otherwise should be chosen. This observation is crucial to understand! The value of the line function at this midpoint is the sole determinant of which point should be chosen.

The image to the right shows the blue point (2,2) chosen to be on the line with two candidate points in green (3,2) and (3,3). The black point (3, 2.5) is the midpoint between the two candidate points.

Alternatively, the difference between points can be used instead of evaluating f(x,y) at midpoints. The difference for the first decision is

If this difference, D, is positive then chose otherwise .

The decision for the second point can be written as

If the difference is positive then is chosen, otherwise . This decision can be generalized by accumulating the error.

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.

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

Running this algorithm for from (0,1) to (6,4) yields the following differences with dx=6 and dy=3:

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

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.