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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Line algorithim for python and numeric
On 13 Oct 2006 07:33:17 -0700, [EMAIL PROTECTED] [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Line algorithim for python and numeric
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Line algorithim for python and numeric
Theerasak Photha [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] On 13 Oct 2006 07:33:17 -0700, [EMAIL PROTECTED] [EMAIL PROTECTED] 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) -- http://mail.python.org/mailman/listinfo/python-list
Re: Line algorithim for python and numeric
Tim Chase [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Line algorithim for python and numeric
Paul McGuire [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] Tim Chase [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Line algorithim for python and numeric
On 10/13/06, Paul McGuire [EMAIL PROTECTED] wrote: Theerasak Photha [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] On 13 Oct 2006 07:33:17 -0700, [EMAIL PROTECTED] [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Line algorithim for python and numeric
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Line algorithim for python and numeric
On 10/13/06, Fredrik Lundh [EMAIL PROTECTED] wrote: 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 -- http://mail.python.org/mailman/listinfo/python-list