Talk:Bresenham's line algorithm (Python)

From LiteratePrograms
Jump to: navigation, search

[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:

  1. Rather than starting the error at error = -deltax / 2, start it at 0
  2. 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:

import curses

# map is an array of strings
m = [ ]

def map_init():
    global m
    m = [ ]
    ruler = " " + "0123456789" * 4
    m.append(list(ruler))
    for n in range(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 coordinates
def show_map(scr):
    global m
    for n in range(len(m)):
        scr.addstr(n, 0, ''.join(m[n]))

def draw_point(x, y, symbol):
    global m
    m[y+1][x+1] = symbol

# http://en.literateprograms.org/Bresenham%27s_line_algorithm_%28Python%29
def line(x0, y0, x1, y1):
    # steep
    steep = abs(y1 - y0) > abs(x1 - x0)
    if steep:
        x0, y0 = y0, x0
        x1, y1 = y1, x1
    # endpoint swap
    if x0 > x1:
        x0, x1 = x1, x0
        y0, y1 = y1, y0
    # ystep
    if y0 < y1:
        ystep = 1
    else:
        ystep = -1
    # init
    deltax = x1 - x0
    deltay = abs(y1 - y0)
    error = -deltax / 2
    y = y0
    # core loop
    for x in range(x0, x1+1):
        if steep:
            draw_point(y, x, '+')
        else:
            draw_point(x, y, '+')
        error = error + deltay
        if error > 0:
            y = y + ystep
            error = error - deltax

# corrected!
def line_corrected(x0, y0, x1, y1):
    # steep
    steep = abs(y1 - y0) > abs(x1 - x0)
    if steep:
        x0, y0 = y0, x0
        x1, y1 = y1, x1
    # endpoint swap
    if x0 > x1:
        x0, x1 = x1, x0
        y0, y1 = y1, y0
    # ystep
    if y0 < y1:
        ystep = 1
    else:
        ystep = -1
    # init
    deltax = x1 - x0
    deltay = abs(y1 - y0)
    error = 0
    y = y0
    # core loop
    for x in range(x0, x1+1):
        if steep:
            draw_point(y, x, '*')
        else:
            draw_point(x, y, '*')
        error = error + deltay
        if (error << 1) >= deltax:
            y = y + ystep
            error = error - deltax
            
# main loop
def demo(scr):
    pos_x = 0 
    pos_y = 0
    key = 0
    algorithm = 'both'
    while key != ord('q'):
        map_init()
        if algorithm in ('both', 'original'):
            line(0, 0, pos_x, pos_y)
        if algorithm in ('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()
        if key == ord('o'):
            if algorithm == 'both':
                algorithm = 'original'
            elif algorithm == 'original':
                algorithm = 'fixed'
            else:
                algorithm = 'both'
        elif key == ord('j') or key == curses.KEY_DOWN or key == ord('2'):
            pos_y = min(pos_y+1, 19)
        elif key == ord('k') or key == curses.KEY_UP or key == ord('8'):
            pos_y = max(pos_y-1, 0)
        elif key == ord('h') or key == curses.KEY_LEFT or key == ord('4'):
            pos_x = max(pos_x-1, 0)
        elif key == ord('l') or key == curses.KEY_RIGHT or key == ord('6'):
            pos_x = min(pos_x+1, 39)
        elif key == ord('b') or key == curses.KEY_END or key == ord('1'):
            pos_x = max(pos_x-1, 0)
            pos_y = min(pos_y+1, 19)
        elif key == ord('n') or key == curses.KEY_NPAGE or key == ord('3'):
            pos_x = min(pos_x+1, 39)
            pos_y = min(pos_y+1, 19)
        elif key == ord('y') or key == curses.KEY_HOME or key == ord('7'):
            pos_x = max(pos_x-1, 0)
            pos_y = max(pos_y-1, 0)
        elif key == ord('u') or key == curses.KEY_PPAGE or key == ord('9'):
            pos_x = min(pos_x+1, 39)
            pos_y = max(pos_y-1, 0)

if __name__ == '__main__':
    curses.wrapper(demo)
hijacker
hijacker
hijacker
hijacker