# Talk:Bresenham's line algorithm (Python)

## [edit] Provenance

An original implementation, based on the pseudocode which appears in the Wikipedia article on Bresenham's algorithm. --Allan McInnes (talk) 01:05, 18 May 2007 (PDT)

The original implementation has a bug and a performance issue.

As far as performance, this implementation uses division to determine the error, which will result in a floating point value in about half of the cases. While not a major issue in normal Python since Python is so slow, if using something like PyPy this may actually matter.

As for the implementation bug... I found that error was being collected in a way that produced incorrect results.

When using the code on the page, drawing a line from 0,0 to 1,1 produced a line going through 0,0 and 1,0 - not at 0,0 and 1,1 like expected.

Actual:

XX ..

Expected:

X. .X

This problem also shows up in various ways at various other lines. Actual:

XXX. ...X

Expected:

XX.. ..XX

I changed two things to fix these issues:

- Rather than starting the error at error = -deltax / 2, start it at 0
- Rather than comparing to 0, compare (error << 1) >= deltax

These two changes result in a completely correct line being drawn.

Here's a program which you can use to see the differences between the two versions. The fixed version is drawn using '*' and the original using '+', and the two lines are superimposed:

importcurses # map is an array of strings m = [ ]defmap_init():globalm m = [ ] ruler = " " + "0123456789" * 4 m.append(list(ruler))forninrange(20): rule = str(n % 10) m.append(list(rule) + list("." * 40) + list(rule)) m.append(list(ruler)) # curses uses (y,x) rather than (x,y) for coordinatesdefshow_map(scr):globalmforninrange(len(m)): scr.addstr(n, 0, ''.join(m[n]))defdraw_point(x, y, symbol):globalm m[y+1][x+1] = symbol # http://en.literateprograms.org/Bresenham%27s_line_algorithm_%28Python%29defline(x0, y0, x1, y1): # steep steep = abs(y1 - y0) > abs(x1 - x0)ifsteep: x0, y0 = y0, x0 x1, y1 = y1, x1 # endpoint swapifx0 > x1: x0, x1 = x1, x0 y0, y1 = y1, y0 # ystepify0 < y1: ystep = 1else: ystep = -1 # init deltax = x1 - x0 deltay = abs(y1 - y0) error = -deltax / 2 y = y0 # core loopforxinrange(x0, x1+1):ifsteep: draw_point(y, x, '+')else: draw_point(x, y, '+') error = error + deltayiferror > 0: y = y + ystep error = error - deltax # corrected!defline_corrected(x0, y0, x1, y1): # steep steep = abs(y1 - y0) > abs(x1 - x0)ifsteep: x0, y0 = y0, x0 x1, y1 = y1, x1 # endpoint swapifx0 > x1: x0, x1 = x1, x0 y0, y1 = y1, y0 # ystepify0 < y1: ystep = 1else: ystep = -1 # init deltax = x1 - x0 deltay = abs(y1 - y0) error = 0 y = y0 # core loopforxinrange(x0, x1+1):ifsteep: draw_point(y, x, '*')else: draw_point(x, y, '*') error = error + deltayif(error << 1) >= deltax: y = y + ystep error = error - deltax # main loopdefdemo(scr): pos_x = 0 pos_y = 0 key = 0 algorithm = 'both'whilekey != ord('q'): map_init()ifalgorithmin('both', 'original'): line(0, 0, pos_x, pos_y)ifalgorithmin('both', 'fixed'): line_corrected(0, 0, pos_x, pos_y) scr.clear() scr.addstr(22, 0, "Use 'o' to toggle algorithm (now %s)." % algorithm) scr.addstr(23, 0, "Use arrow or vi keys to move, 'q' to quit.") show_map(scr) scr.move(pos_y+1, pos_x+1) key = scr.getch()ifkey == ord('o'):ifalgorithm == 'both': algorithm = 'original'elifalgorithm == 'original': algorithm = 'fixed'else: algorithm = 'both'elifkey == ord('j')orkey == curses.KEY_DOWNorkey == ord('2'): pos_y = min(pos_y+1, 19)elifkey == ord('k')orkey == curses.KEY_UPorkey == ord('8'): pos_y = max(pos_y-1, 0)elifkey == ord('h')orkey == curses.KEY_LEFTorkey == ord('4'): pos_x = max(pos_x-1, 0)elifkey == ord('l')orkey == curses.KEY_RIGHTorkey == ord('6'): pos_x = min(pos_x+1, 39)elifkey == ord('b')orkey == curses.KEY_ENDorkey == ord('1'): pos_x = max(pos_x-1, 0) pos_y = min(pos_y+1, 19)elifkey == ord('n')orkey == curses.KEY_NPAGEorkey == ord('3'): pos_x = min(pos_x+1, 39) pos_y = min(pos_y+1, 19)elifkey == ord('y')orkey == curses.KEY_HOMEorkey == ord('7'): pos_x = max(pos_x-1, 0) pos_y = max(pos_y-1, 0)elifkey == ord('u')orkey == curses.KEY_PPAGEorkey == ord('9'): pos_x = min(pos_x+1, 39) pos_y = max(pos_y-1, 0)if__name__ == '__main__': curses.wrapper(demo)