# 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.

## Contents |

## [edit] 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>>=forxinrange(x0, x1):ifsteep: self.draw_point(y, x, color)else: self.draw_point(x, y, color)if(error << 1) >= deltax: y = y + 1 error = error + 2*(deltay - deltax)else: error = error + 2*deltay

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 = 0 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)ifsteep: 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>>=ifx0 > 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>>=

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>>=defdraw_line(self, x0, y0, x1, y1, color="red"): steep endpoint swap ystep init core loop

## [edit] 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>>=classBresenhamCanvas(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>>=defdraw_point(self, x, y, color="red"): self.create_line(x, y, x, y, fill=color)

## [edit] 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>>=fromTkinterimport* BresenhamCanvas draw_point draw_lineif__name__ == "__main__":importmath CANVAS_SIZE = 400 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 = 200 angle_step = (2 * math.pi) / n_linesforiinrange(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()

## [edit] References

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

Download code |