Line algorithim for python and numeric

[Paul McGuire]

"Tim Chase" <python.list at tim.thechases.com> wrote in message 
news:mailman.451.1160752377.11739.python-list at python.org...
>>>   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
>
>
No need for Bresenham's algorithm here.  The point behind BA is to draw a 
connected line using best selection of points, going cell-by-adjacent-cell 
through the pixel map, so that you actually get a solid line in the result. 
The OP's problem is much simpler - he/she (is "Theresaak" a boy name or a 
girl name?) just wants the array of grid coordinates between a starting and 
ending cell, so "continuousness" of the line is not an issue.

-- Paul