Line algorithim for python and numeric

[Tim Chase]

>>   I'm wondering if anyone knows of a way to extract data from a numeric
>> array along a line. I have a gridded dataset which I would like to be
>> able to choose two points and extract a 1-d array of the data values
>> along the line between the two points. Any ideas?
> 
> Are these all 45 degree lines or what?
> 
> If not, you'll have to use trigonometry and approximate the closest
> matching cell. (Don't worry, Python has maths functions!! :))


There are a couple of optimal/easy cases where the run is 
horizontal, vertical, or as you describe, 45-degrees (where 
x_step = y_step or x_step = -y_step)

Any other set of arbitrary points, and you will have to specify 
the behavior a little more finely.

You can use something like Bresenham's algorithm to march either 
"over" or "up and over" to just pick out the "one point at each 
step that falls closest to the actual line" along the run. 
There's also the Wu Anti-aliasing line algorithm which takes 
something akin to Bresenham's algorithm and then samples the 
potential points to yield an "anti-aliased" result which averages 
the two potential  data-points (traditionally colors, but they 
could really be any average-able data values).

I'm not sure I've seen either of them implemented in Python 
before (though actually *looking* for them might increase those 
odds ;-)

http://en.wikipedia.org/wiki/Xiaolin_Wu's_line_algorithm

has details and a pseudo-code implementation (which shouldn't be 
too far from the Python code).  It's also got links to stuff on 
Bresenham's.

-tkc