Bresenham's line algorithm (Python)
 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): if steep: 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) 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.
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"):
 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
<<BresenhamCanvas>>= class BresenhamCanvas(Canvas):
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 * if __name__ == "__main__": import math 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_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()
- NIST, Bresenham's algorithm, accessed 2007-05-18.