# Bresenham's line algorithm (Python)

Bresenham's line algorithm is an algorithm for drawing a line on a raster display. It was originally developed by Jack Bresenham in 1962.

## Here's where we draw the line

The basic approach taken in Bresenham's algorithm is to step along the line from one end to the other in the x-direction, coloring successive pixels in a given row until the error between the actual line and the row being colored grows too great.

```<<core loop>>=
for x in range(x0, x1 + 1): # We add 1 to x1 so that the range includes x1
if steep:
self.draw_point(y, x, color)
else:
self.draw_point(x, y, color)
error = error + deltay
if error > 0:
y = y + ystep
error = error - deltax
```

The error is essentially a function of the gradient of the line (i.e. `deltay/deltax`. But in order to avoid floating point arithmetic, the expressions involving error are multiplied through by `deltax` (this may be an unnecessary optimization in Python, but is done here for consistency with other implementations). The initial values of `y` and the error are

```<<init>>=
deltax = x1 - x0
deltay = abs(y1 - y0)
error = -deltax / 2
y = y0
```

The loop shown above contains a conditional over the variable `steep`. Since the basic Bresenham algorithm only works for lines with a slope less than 1, if the line to be plotted is "steep" then we step along the y-direction instead. That is:

```<<steep>>=
steep = abs(y1 - y0) > abs(x1 - x0)
if steep:
x0, y0 = y0, x0
x1, y1 = y1, x1
```

Similarly, the basic algorithm can only really handle lines that start on an x-value closer to the origin than the end-point. Thus, to provide a more general capability for drawing lines we swap the end-points if necessary, to ensure that the preceding condition holds.

```<<endpoint swap>>=
if x0 > x1:
x0, x1 = x1, x0
y0, y1 = y1, y0
```

The direction in which the y-values are stepped depends on whether the end-point of the line is above or below the start-point.

```<<ystep>>=
if y0 < y1:
ystep = 1
else:
ystep = -1
```

For convenience, we'll wrap the whole Bresenham implementation in a method which simply takes the end-points of the line to be drawn, and then draws the specified line.

```<<draw_line>>=
def draw_line(self, x0, y0, x1, y1, color="red"):
steep
endpoint swap
ystep
init
core loop
```

## Get to the point

In order to draw lines, we need to be able to draw points. We'll use the standard Python `Tkinter` library to produce graphics, and do our drawing on a customized `Canvas`.

```<<BresenhamCanvas>>=
class BresenhamCanvas(Canvas):
```

The `Canvas` object doesn't directly support drawing points, so we implement a point-drawing function by drawing a zero-length line (yes, it's a little silly to implement a line-drawing algorithm by using lines - just ignore how `draw_point` is actually implemented internally, and focus on the fact that it produces points).

```<<draw_point>>=
def draw_point(self, x, y, color="red"):
self.create_line(x, y, x, y, fill=color)
```

## Round and round we go

To test the implementation of the Bresenham line algorithm, we should try to draw lines with a wide variety of slopes (both >1 and <1), as well as various end-points. One way to accomplish that task is to plot a circular pattern of radial lines at different angles. The test function defined below does exactly that.

```<<bresenham_line.py>>=
from Tkinter import *
BresenhamCanvas
draw_point
draw_line
if __name__ == "__main__":
import math
CANVAS_SIZE = 600
root = Tk()
canvas = BresenhamCanvas(root, width=CANVAS_SIZE, height=CANVAS_SIZE)
canvas.pack()
margin = CANVAS_SIZE / 10
xcenter = int(CANVAS_SIZE / 2)
ycenter = int(CANVAS_SIZE / 2)
line_length = ((CANVAS_SIZE / 2) - margin)
n_lines = 100
angle_step = (2 * math.pi) / n_lines
for i in range(n_lines):
theta = angle_step * i
xstart = int(margin * math.cos(theta)) + xcenter
ystart = int(margin * math.sin(theta)) + ycenter
xend = int(line_length * math.cos(theta)) + xcenter
yend = int(line_length * math.sin(theta)) + ycenter
canvas.draw_line(xstart, ystart, xend, yend, color="blue")
root.mainloop()
```

## References

• NIST, Bresenham's algorithm, accessed 2007-05-18.