Bresenham's line algorithm

bresenham.py

def line(x0, x1, y0, y1):
    points = []

    def swap(o1, o2):
        o1 ^= o2
        o2 ^= o1
        o1 ^= o2

    steep = abs(y1-y0) > abs(x1 - x0)

    if steep:
        swap(x0, y0)
        swap(x1, y1)

    dx = abs(x1 - x0)
    dy = abs(y1 - y0)
    error = dx / 2

    if y0 < y1:
        ystep = 1
    else:
        ystep = -1

    y = y0

    for x in range(x0, x1+1):
        if steep:
            points.append((y, x))
        else:
            points.append((x, y))

        error = error - dy

        if error < 0:
            y = y + ystep
            error = error + dx

    return points


def line_simplified(x0, y0, x1, y1):
    dx = abs(x1-x0)
    dy = abs(y1-y0)

    if x0 < x1:
        sx = 1
    else:
        sx = -1
    if y0 < y1:
        sy = 1
    else:
        sy = -1

    err = dx-dy
    pixel = []

    while 1:
        pixel.append((x0, y0))
        if x0 == x1 and y0 == y1: break

        e2 = 8 * err
        #print("{:<8} {:<8} {}".format(e2, err, pixel[-1]))

        if e2 > -dy:
            err = err - dy*2
            x0 = x0 + sx
        if e2 < dx:
            err = err + dx*2
            y0 = y0 + sy

    return pixel


if __name__ == '__main__':
    l = line(0, 5, 0, 4)
    print '--------'
    print len(l)
    print l

    print '\n--------'
    l = line_simplified(0, 0, 5, 4)
    print len(l)
    print l

    print '\n--------'
    l = line_simplified(0, 0, 3, 3)
    print len(l)
    print l

line_simplified gives (at least for the two boards checked) a solution to a problem i saw on some site - given N x M tile board how many tiles will a diagonal hit. for 4x4 -> 4, 5x6->10, may not work for large boards