Enter Bresenham: The improved approach
Jack Bresenham developed this algorithm while working for IBM in 1962. In short, it plots a straight line but doesn’t leave pixels disconnected from each other. The basic premise is that when drawing a line pixel by pixel, each successive pixel must be at least a distance of 1 in either the x or y (or both) direction. If not, a gap will appear. While the naïve approach we’ve just used creates a plot where all the x values are a distance of 1 apart, the same isn’t always true for the y values. The only way to ensure all x and y values are a distance of 1 apart is to incrementally plot the line from point 1 to point 2, ensuring that either the x or y values are changing by a maximum of 1 with each loop.
Consider the close-up of a steep line being plotted in Figure 3.4:
Figure 3.4: A line being constructed pixel by pixel
The values for dx (change in x values) and dy (change in y values) represent...
