Bresenham's line algorithm

Bresenham's line algorithm is an implimentation of an Algorithm which determines which points on a 2-dimensional matrix should be plotted in order to form a straight line between two given points.

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." Bresenham later modified his algorithm to produce circles.

There are several known line-drawing algorithms in addition to Bresenham's line algorithm including Xiaolin Wu's two-step line algorithm (which is faster).

---

An example of Bresenham's line algorithm in Visual basic follows. The "Swap" procedure is not shown.

Private Sub BresLine(InitialX As Long, InitialY As Long, FinalX As Long, FinalY As Long)
   ' Bresenham's line algorithm for Microsoft Visual Basic 6.0
   ' Implimentation by Robert Lee <rlee0001@maine.rr.com> July, 2002 Public Domain

   Dim Steep As Boolean
   Dim DeltaX As Long, DeltaY As Long, Delta As Long
   Dim StepX As Long, StepY As Long
   Dim Coord As Long

   Steep = False
   DeltaX = Abs(FinalX - InitialX)
   If (FinalX - InitialX) > 0 Then
       StepX = 1
   Else
       StepX = -1
   End If
   DeltaY = Abs(FinalY - InitialY)
   If (FinalY - InitialY) > 0 Then
       StepY = 1
   Else
       StepY = -1
   End If
   If DeltaY > DeltaX Then
       Steep = True
       Swap InitialX, InitialY
       Swap DeltaX, DeltaY
       Swap StepX, StepY
   End If
   Delta = (DeltaY * 2) - DeltaX
   For Coord = 0 To DeltaX
       If Steep Then
           Me.PSet (InitialY, InitialX)
       Else
           Me.PSet (InitialX, InitialY)
       End If
       While Delta >= 0
           InitialY = InitialY + StepY
           Delta = Delta - (DeltaX * 2)
       Wend
       InitialX = InitialX + StepX
       Delta = Delta + (DeltaY * 2)
   Next Coord
   Me.PSet (FinalX, FinalY)
End Sub