Line algorithim for python and numeric
Tim Chase
python.list at tim.thechases.com
Fri Oct 13 17:07:25 CEST 2006
>> 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
More information about the Python-list
mailing list