Bresenham's line algorithm (Python)

From LiteratePrograms

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 1 Here's where we draw the line 2 Get to the point 3 Round and round we go 4 References

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.