# Line algorithim for python and numeric

Paul McGuire ptmcg at austin.rr._bogus_.com
Fri Oct 13 17:36:02 CEST 2006

```"Paul McGuire" <ptmcg at austin.rr._bogus_.com> wrote in message
> "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.