Bresenham line doesn't terminate

Question

I've implemented the Bresenham algorithm from Wikipedia in python but for some lines it doesn't work, like from 1,0 to 0,1 it doesn't stop and keeps going on to make a super long line

def line(x0, y0, x1, y1):
    dx = x1 - x0
    dy = y1 - y0
    sx = x0 < x1 and 1 or -1
    sy = y0 < y1 and 1 or -1
    err = dx - dy

    points = []
    x, y = x0, y0
    while True:
        points += [(x, y)]
        if x == x1 and y == y1:
            break
        e2 = err * 2
        if e2 > -dy:
            err -= dy
            x += sx
        if e2 < dx:
            err += dx
            y += sy
    return points

rodrigo rodrigo · Accepted Answer · 2011-08-23T10:08:03

You are missing the call to abs in the initialization of dx and dy:

dx = abs(x1 - x0)
dy = abs(y1 - y0)

Bresenham line doesn't terminate

2 Answers