473,322 Members | 1,719 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

Line algorithim for python and numeric

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
8 1819
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
> 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
"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
"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
"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
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
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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

226
by: Stephen C. Waterbury | last post by:
This seems like it ought to work, according to the description of reduce(), but it doesn't. Is this a bug, or am I missing something? Python 2.3.2 (#1, Oct 20 2003, 01:04:35) on linux2 Type...
1
by: Tim Bradshaw | last post by:
I'd like to be able to install python with stow, and then to install various modules which use distutils, also with stow. This currently pretty much won't work, because Python chases symlinks to...
1
by: youngdubliner | last post by:
I'm having a problem ........ I've stripped all my code to help isolate the problem. Its seems to be with importing numarray when python is embedded in C. I have a simple C program it Opens...
7
by: Jive | last post by:
Here's my sitch: I use gnuplot.py at work, platform Win32. I want to upgrade to Python 2.4. Gnuplot.py uses extension module Numeric. Numeric is now "unsupported." The documentation says "If...
0
by: Cedric | last post by:
This is a 3 weeks old problem, but having found a solution (and having looked for one here, finding only this message), I'm replying now. From: Jive (someone@microsoft.com) Subject: Upgrade...
2
by: martino | last post by:
Hi, I am trying to install NumPy (v23.8) onder Macosx (panther version). Python (v2.3) is bundled into panther and I installed the IDE on top of that. After having untarred the source distribution...
32
by: David | last post by:
Hi I'm trying to teach myself python and so far to good, but I'm having a bit of trouble getting a function to work the way I think it should work. Right now I'm taking a simple program I wrote in...
0
by: ronysk | last post by:
Hi, I am posting here to seek for help on type conversion between Python (Numeric Python) and C. Attachment A is a math function written in C, which is called by a Python program. I had...
28
by: DaemonCoder | last post by:
The challenge is to create the shortest algorithim, In any programming language. RULES: 1. All code must be on one line. 2. Languages that prevent this are disallowed. I.E Assembly, and of...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.