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)): canvas.draw(x,y)

** 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.

### Update

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)) ...etc...

## 3 comments

Comments feed for this article

October 4, 2006 at 12:34 pm

xyzDo not express your knowledge in this way,

we have a better solution then you, ok?

March 24, 2007 at 5:04 pm

floalgorithm doesn’t work

July 12, 2013 at 9:07 am

yahkobits not an exact code for line drawing.showing some errors..