In 1965 Jack Elton Bresenham published the paper Algorithm for computer control of a digital plotter in the IBM Systems Journal, volume 4, number 1. It explained how a line could be approximated on an integer grid. The algorithm is still used today as a rasterization technique for rendering lines on video displays or printers. As Bresenham's paper suggests, however, it was originally devised for a plotter, capable of moving from one grid point to one of the adjacent eight grid points.
We consider drawing a line from to on an integer grid by choosing the points that lie close to the true line. We also assume that and . The method is easily extended to the general case with arbitrary starting and ending points.
The line has the form
and we aim to sample the line at the grid points with for and .
We now associate with each step an error term,
The interpretation of this error term is important: It expresses the difference at between the line's true -coordinate, , and the midpoint between the previously chosen -coordinate, , and its successor, . The factor is there to make all quantities integral. The sign of is thus crucial:
- If then lies closest to the line (it is a tie for ).
- If then should be chosen.
Note how the magnitude of also tells exactly how far from the true line the chosen grid point is. It is straightforward to show that for .
To determine the 's we start with the base case:
For we get
We now split into the two cases for and get
These expressions determine all the 's which, in turn, determines all the 's.