Bresenham's line algorithm
Bresenham's line algorithm determines which points on a 2-dimensional raster should be plotted in order to form a straight line between two given points, and is commonly used to draw lines on a computer screen. It is probably one of the earliest algorithms discovered in the field of computer graphics.The algorithm was developed by Jack E. Bresenham in 1962 at IBM. In 2001 Bresenham wrote:
- "I was working in the computation lab at IBM's San Jose development lab. A Calcomp plotter had been attached to an IBM 1401 via the 1407 typewriter console. [The algorithm] was in production use by summer 1962, possibly a month or so earlier. Programs in those days were freely exchanged among corporations so Calcomp (Jim Newland and Calvin Hefte) had copies. When I returned to Stanford in Fall 1962, I put a copy in the Stanford comp center library.
- A description of the line drawing routine was accepted for presentation at the 1963 ACM national convention in Denver, Colorado. It was a year in which no proceedings were published, only the agenda of speakers and topics in an issue of Communications of the ACM. A person from the IBM Systems Journal asked me after I made my presentation if they could publish the paper. I happily agreed, and they printed it in 1965."
There are several other known line-drawing algorithms including Xiaolin Wu's line algorithm, which is faster.
