Line algorithim for python and numeric

[bcdonovan]

Hi everyone,

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?

Thanks,
Brian

[Theerasak Photha]

On 13 Oct 2006 07:33:17 -0700, bc*******@gmail .com <bc*******@gmai l.comwrote:

Hi everyone,

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!! :))

-- Theerasak

[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.or g/wiki/Xiaolin_Wu's_li ne_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

[Paul McGuire]

"Theerasak Photha" <ha********@gma il.comwrote in message
news:ma******** *************** *************** @python.org...

On 13 Oct 2006 07:33:17 -0700, bc*******@gmail .com <bc*******@gmai l.com>
wrote:

>Hi everyone,

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!! :))

-- Theerasak

No need for that messy trig stuff - simpler and faster would be to use
linear interpolation, since you know the starting and ending cell
coordinates, and how many values you want, compute the array of... oh, hell,
here it is:

start = (4,10)
end = (304,310)
n = 11

dn = ((end[0]-start[0])/float(n),(end[1]-start[1])/float(n))
interpedNodes = [ (start[0]+dn[0]*x, start[1]+dn[1]*x) for x in range(n+1) ]

for nod in interpedNodes:
print nod
print

cellNodes = map(lambda ii: (int(round(ii[0])), int(round(ii[1]))),
interpedNodes)
for nod in cellNodes:
print nod

Prints out:
(4.0, 10.0)
(31.27272727272 7273, 37.272727272727 273)
(58.54545454545 4547, 64.545454545454 547)
(85.81818181818 1813, 91.818181818181 813)
(113.0909090909 0909, 119.09090909090 909)
(140.3636363636 3637, 146.36363636363 637)
(167.6363636363 6363, 173.63636363636 363)
(194.9090909090 9091, 200.90909090909 091)
(222.1818181818 1819, 228.18181818181 819)
(249.4545454545 4547, 255.45454545454 547)
(276.7272727272 7275, 282.72727272727 275)
(304.0, 310.0)

(4, 10)
(31, 37)
(59, 65)
(86, 92)
(113, 119)
(140, 146)
(168, 174)
(195, 201)
(222, 228)
(249, 255)
(277, 283)
(304, 310)

[Paul McGuire]

"Tim Chase" <py*********@ti m.thechases.com wrote in message
news:ma******** *************** *************** @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.or g/wiki/Xiaolin_Wu's_li ne_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

[Paul McGuire]

"Paul McGuire" <pt***@austin.r r._bogus_.comwr ote in message
news:kd******** ***********@tor nado.texas.rr.c om...

"Tim Chase" <py*********@ti m.thechases.com wrote in message
news:ma******** *************** *************** @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
(traditional ly 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.or g/wiki/Xiaolin_Wu's_li ne_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

[Theerasak Photha]

On 10/13/06, Paul McGuire <pt***@austin.r r._bogus_.comwr ote:

"Theerasak Photha" <ha********@gma il.comwrote in message
news:ma******** *************** *************** @python.org...

On 13 Oct 2006 07:33:17 -0700, bc*******@gmail .com <bc*******@gmai l.com>
wrote:

Hi everyone,

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!! :))

-- Theerasak

No need for that messy trig stuff - simpler and faster would be to use
linear interpolation, since you know the starting and ending cell
coordinates, and how many values you want, compute the array of... oh, hell,
here it is:

I'm not in kolluge yet and I just learned about linear interpolation
today---although I don't think it would necessarily apply to this
problem, where the increments set by the grid might be more discrete
than the line itself (hope you see what my innumerate self is trying
to say!!), thanx for teaching me something new. :)

To myself: Gee duh, Theerasak, it make sense now!

-- Theerasak

[Fredrik Lundh]

Theerasak Photha wrote:

I'm not in kolluge yet and I just learned about linear interpolation
today---although I don't think it would necessarily apply to this
problem, where the increments set by the grid might be more discrete
than the line itself

that's usually solved by stepping along the grid in one direction, and
interpolating in the other.

</F>

[Theerasak Photha]

On 10/13/06, Fredrik Lundh <fr*****@python ware.comwrote:

Theerasak Photha wrote:

I'm not in kolluge yet and I just learned about linear interpolation
today---although I don't think it would necessarily apply to this
problem, where the increments set by the grid might be more discrete
than the line itself

that's usually solved by stepping along the grid in one direction, and
interpolating in the other.

Could rounding still be an issue? I sketched a line w/ m = 1/3 and
could see different possible outcomes for certain points on the line
in between each 3rd point on the x axis.

-- Theerasak