By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
444,199 Members | 1,120 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 444,199 IT Pros & Developers. It's quick & easy.

Line algorithim for python and numeric

P: n/a
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

Oct 13 '06 #1
Share this Question
Share on Google+
8 Replies


P: n/a
On 13 Oct 2006 07:33:17 -0700, bc*******@gmail.com <bc*******@gmail.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
Oct 13 '06 #2

P: n/a
> 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
Oct 13 '06 #3

P: n/a
"Theerasak Photha" <ha********@gmail.comwrote in message
news:ma**************************************@pyth on.org...
On 13 Oct 2006 07:33:17 -0700, bc*******@gmail.com <bc*******@gmail.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.272727272727273, 37.272727272727273)
(58.545454545454547, 64.545454545454547)
(85.818181818181813, 91.818181818181813)
(113.09090909090909, 119.09090909090909)
(140.36363636363637, 146.36363636363637)
(167.63636363636363, 173.63636363636363)
(194.90909090909091, 200.90909090909091)
(222.18181818181819, 228.18181818181819)
(249.45454545454547, 255.45454545454547)
(276.72727272727275, 282.72727272727275)
(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)
Oct 13 '06 #4

P: n/a
"Tim Chase" <py*********@tim.thechases.comwrote in message
news:ma**************************************@pyth on.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
Oct 13 '06 #5

P: n/a
"Paul McGuire" <pt***@austin.rr._bogus_.comwrote in message
news:kd*******************@tornado.texas.rr.com...
"Tim Chase" <py*********@tim.thechases.comwrote in message
news:ma**************************************@pyth on.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
Oct 13 '06 #6

P: n/a
On 10/13/06, Paul McGuire <pt***@austin.rr._bogus_.comwrote:
"Theerasak Photha" <ha********@gmail.comwrote in message
news:ma**************************************@pyth on.org...
On 13 Oct 2006 07:33:17 -0700, bc*******@gmail.com <bc*******@gmail.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
Oct 13 '06 #7

P: n/a
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>

Oct 13 '06 #8

P: n/a
On 10/13/06, Fredrik Lundh <fr*****@pythonware.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
Oct 13 '06 #9

This discussion thread is closed

Replies have been disabled for this discussion.