Pulling from Wikipedia:

function line(x0, x1, y0, y1)
     boolean steep := abs(y1 - y0) > abs(x1 - x0)
     if steep then
         swap(x0, y0)
         swap(x1, y1)
     if x0 > x1 then
         swap(x0, x1)
         swap(y0, y1)
     int deltax := x1 - x0
     int deltay := abs(y1 - y0)
     int error := 0
     int ystep
     int y := y0
     if y0 < y1 then ystep := 1 else ystep := -1
     for x from x0 to x1
         if steep then plot(y,x) else plot(x,y)
         error := error + deltay
         if 2×error ≥ deltax
             y := y + ystep
             error := error - deltax

So next step (for me at least) is to implement this in Python. What I’d really like is to create a Python generator in C, to take real advantage of the speed, but it’ll work as-is, and I can probably afford to be a little bit wasteful on a prototype that I doubt anyone will see anyways.

def line((x0, y0), (x1, y1)):
    steep = abs(y1 - y0) > abs(x1 - x0)
    if steep:
        x0, y0 = y0, x0
        x1, y1 = y1, x1
    if x0 > x1:
        x0, x1 = x1, x0
        y0, y1 = y1, y0
    deltax = x1 - x0
    deltay = abs(y1 - y0)
    error = 0
    y = y0
    ystep = (y0 = deltax:
            y += ystep
            error -= deltax

I haven’t worked much with rolling my own generators (only Twisted’s deferred generators **). I think this code would work:

for x, y in line((0,0), (4,5)):

** Twisted’s deferred generators allow you to write blocking code… in a framework that runs entirely with nonblocking asynchronous callback-based functions… in a language that is inherently blocking. I suppose it’s not that bad, given that Python doesn’t actually multithead. Ever. But i’m not trying to write PySQUID, I just want a darned discrete line.


The algorithm didn’t work because I had my arguments in the wrong order. It’s fixed, and I ran it through a few manual tests like this:

def evaluate((x0,y0), (x1,y1)):
    print "line (%d %d) -> (%d %d)" % (x0, y0, x1, y1)
    segments = [ "(%d %d)" % xy for xy in line((x0,y0), (x1,y1)) ]
    print "\n".join(segments)

evaluate((0,0), (5,5))
evaluate((0,0), (-5,5))
evaluate((0,0), (5,-5))
evaluate((0,0), (-5,-5))