Line algorithim for python and numeric

[Paul McGuire]

"Paul McGuire" <ptmcg at austin.rr._bogus_.com> wrote in message 
news:kdOXg.47125$DU3.14756 at tornado.texas.rr.com...
> "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
>

Hmmm, maybe I was a little hasty.  Re-reading the OP's post, he/she may in 
fact want the Bresenham-type traversal of the grid from point A to point B.

Need a little more info on requirements, Theresaak.

-- Paul