444,199 Members | 1,120 Online
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
8 Replies

 P: n/a On 13 Oct 2006 07:33:17 -0700, bc*******@gmail.com

 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 beable to choose two points and extract a 1-d array of the data valuesalong 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" wrote: >Hi everyone, I'm wondering if anyone knows of a way to extract data from a numericarray along a line. I have a gridded dataset which I would like to beable to choose two points and extract a 1-d array of the data valuesalong 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" > I'm wondering if anyone knows of a way to extract data from a numericarray along a line. I have a gridded dataset which I would like to beable to choose two points and extract a 1-d array of the data valuesalong 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 closestmatching 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" >> I'm wondering if anyone knows of a way to extract data from a numericarray along a line. I have a gridded dataset which I would like to beable to choose two points and extract a 1-d array of the data valuesalong 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 closestmatching 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 thebehavior 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 fallsclosest to the actual line" along the run. There's also the WuAnti-aliasing line algorithm which takes something akin to Bresenham'salgorithm 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 datavalues).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_algorithmhas details and a pseudo-code implementation (which shouldn't be too farfrom 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 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. Oct 13 '06 #8

 P: n/a On 10/13/06, Fredrik Lundh

### This discussion thread is closed

Replies have been disabled for this discussion.