Finding near-misses between lines in 3D
October 14, 2016 11:04 AM Subscribe
Is there a good (read: well-known/efficient) way to find the "near-miss" intersection of 3 lines in 3D space? The lines almost, but don't quite, cross each other (image in an attempt to illustrate the problem)
(I'm doing this in MATLAB at the moment, but would appreciate general/conceptual ideas as well.)
What I've been doing so far is to map each of the three vectors onto a regular 3D point cloud using linear interpolation (matlab's "scattered interpolant") and then summing the three point grids to find points crossed by all three lines. This seems to work as long as I define a sufficiently dense point grid, but it also feels to me like an extremely inefficient way of doing things - for an NxNxN point cloud I end up having to sit through matlab chugging along interpolating N^3 points, most of which are zeros.
The problem of finding near-misses between lines seems like it would be the kind of thing that someone a lot smarter than me would have thought about before. Is there some sort of generally accepted solution for this kind of thing, or is it one of those conceptually simple problems that end up being a lot more complicated than it seems? Assume I have very little knowledge of, say computer graphics or any other area where this problem might be applicable - I'm just stumbling around and trying not to reinvent the wheel, here. Thanks!
(I'm doing this in MATLAB at the moment, but would appreciate general/conceptual ideas as well.)
What I've been doing so far is to map each of the three vectors onto a regular 3D point cloud using linear interpolation (matlab's "scattered interpolant") and then summing the three point grids to find points crossed by all three lines. This seems to work as long as I define a sufficiently dense point grid, but it also feels to me like an extremely inefficient way of doing things - for an NxNxN point cloud I end up having to sit through matlab chugging along interpolating N^3 points, most of which are zeros.
The problem of finding near-misses between lines seems like it would be the kind of thing that someone a lot smarter than me would have thought about before. Is there some sort of generally accepted solution for this kind of thing, or is it one of those conceptually simple problems that end up being a lot more complicated than it seems? Assume I have very little knowledge of, say computer graphics or any other area where this problem might be applicable - I'm just stumbling around and trying not to reinvent the wheel, here. Thanks!
The algebra isn't too hard to work through, but: Wikipedia on finding the shortest distance between Skew Lines . There's a lot of other stuff out there, I first went to Graphics Gems (volume 1), page 304 has notes on finding the intersection, and remarks that distance falls out of that if they don't intersect.
posted by straw at 11:21 AM on October 14, 2016 [2 favorites]
posted by straw at 11:21 AM on October 14, 2016 [2 favorites]
Best answer: Oh, and I realized I answered the wrong question: Not only does distance fall out in 2 line distance calculations, but location along the line also falls out. So you could calculate all closest distances, and then look for clusters of the closest points. Not a cheap set of calculations, although there's lots of literature on speeding it up, but not undoable.
posted by straw at 12:07 PM on October 14, 2016 [2 favorites]
posted by straw at 12:07 PM on October 14, 2016 [2 favorites]
Best answer: Dan Sunday has working code for finding closest points on two 3D lines, as well as laying out all the math he did to solve it.
I adapted this code for my app FlagWaver (to do hit testing for wireframe stuff) and it worked for me. His site has a lot of 3D algorithms like this.
posted by w0mbat at 12:43 PM on October 14, 2016 [1 favorite]
I adapted this code for my app FlagWaver (to do hit testing for wireframe stuff) and it worked for me. His site has a lot of 3D algorithms like this.
posted by w0mbat at 12:43 PM on October 14, 2016 [1 favorite]
Best answer: One way to do it would be to find the point the minimizes the sum of the squares of the distances of the point to each of the three lines.
A convenient way to define a line in 3-space is parametrically with a point on the line (Q) and a vector (v); then the line is defined by L=Q+vt. When you define the line this way, the distance from a point (P) to the line is given by |(P-Q) ⨯ v| / |v|. Since we can multiply our vector v by a constant and still have the same line, let's require that v be a unit vector, and the denominator falls out. Then the square of the distance of the point to the line is |(P-Q) ⨯ v|2. Calculate the sum of the squares of the distances of P to each of the three lines, and then find the point which minimizes that sum.
As a very simple example, let's consider these three lines:
L1: The x-axis. Q1=(0,0,0) v1={1,0,0}
L2: A line passing through (1,1,0) and parallel to the z-axis. Q2=(1,1,0) v2={0,0,1}
L3: A line in the yz plane, passing through (0,0,2) and with slope 4/3: Q3=(0,0,2) v3={0, 3/5, 4/5}
Let P=(x,y,z); D1 is the distance from P to L1, etc.
D12 = |(P-Q1) ⨯ v1|2 = |{x,y,z} ⨯ {1,0,0}|2 = y2+z2
D22 = |(P-Q2) ⨯ v2|2= |{x-1,y-1,z} ⨯ {0,0,1}|2 = (x-1)2 + (y-1)2 = x2-2x+y2-2y+2
D32 = |(P-Q3) ⨯ v3|2= |{x,y,z-2} ⨯ {0, 3/5, 4/5}|2 = [(3/5)(z-2)-(4/5)y]2 + ((4/5)x)2 + ((-3/5)x)2 = (25x2+16y2-24yz+48y+9z2-36z+36)/25
Let S be the sum of the squares of the three distances:
S = D12+D22+D32 = (50x2-50x+66y2-24yz-2y+34z2-36z+86)/25
To minimize S, take the partial derivative of S with respect to each coordinate and set to zero:
∂S/∂x = (100x-50)/25 = 0
∂S/∂y = (132y-24z-2)/25 = 0
∂S/∂z = (-24y+68z-36)/25 = 0
Which has the solution x=1/2, y=5/42, z=12/21
posted by DevilsAdvocate at 1:33 PM on October 14, 2016
A convenient way to define a line in 3-space is parametrically with a point on the line (Q) and a vector (v); then the line is defined by L=Q+vt. When you define the line this way, the distance from a point (P) to the line is given by |(P-Q) ⨯ v| / |v|. Since we can multiply our vector v by a constant and still have the same line, let's require that v be a unit vector, and the denominator falls out. Then the square of the distance of the point to the line is |(P-Q) ⨯ v|2. Calculate the sum of the squares of the distances of P to each of the three lines, and then find the point which minimizes that sum.
As a very simple example, let's consider these three lines:
L1: The x-axis. Q1=(0,0,0) v1={1,0,0}
L2: A line passing through (1,1,0) and parallel to the z-axis. Q2=(1,1,0) v2={0,0,1}
L3: A line in the yz plane, passing through (0,0,2) and with slope 4/3: Q3=(0,0,2) v3={0, 3/5, 4/5}
Let P=(x,y,z); D1 is the distance from P to L1, etc.
D12 = |(P-Q1) ⨯ v1|2 = |{x,y,z} ⨯ {1,0,0}|2 = y2+z2
D22 = |(P-Q2) ⨯ v2|2= |{x-1,y-1,z} ⨯ {0,0,1}|2 = (x-1)2 + (y-1)2 = x2-2x+y2-2y+2
D32 = |(P-Q3) ⨯ v3|2= |{x,y,z-2} ⨯ {0, 3/5, 4/5}|2 = [(3/5)(z-2)-(4/5)y]2 + ((4/5)x)2 + ((-3/5)x)2 = (25x2+16y2-24yz+48y+9z2-36z+36)/25
Let S be the sum of the squares of the three distances:
S = D12+D22+D32 = (50x2-50x+66y2-24yz-2y+34z2-36z+86)/25
To minimize S, take the partial derivative of S with respect to each coordinate and set to zero:
∂S/∂x = (100x-50)/25 = 0
∂S/∂y = (132y-24z-2)/25 = 0
∂S/∂z = (-24y+68z-36)/25 = 0
Which has the solution x=1/2, y=5/42, z=12/21
posted by DevilsAdvocate at 1:33 PM on October 14, 2016
Response by poster: Thanks, everyone - all of your answers helped me clarify my thinking a lot. I'd been hung up on thinking of my lines as arbitrary point clouds (for reasons that were previously sensible but are no longer relevant) and totally glossed over the fact that they were, well, vectors (despite having framed my question and tagged my post that way!) This has been tremendously helpful.
posted by btfreek at 6:30 PM on October 14, 2016
posted by btfreek at 6:30 PM on October 14, 2016
« Older A Hertz, an Iphone and Crackerjack GPS? | Can you help me find a mass-produced ring? Newer »
This thread is closed to new comments.
posted by eruonna at 11:20 AM on October 14, 2016 [1 favorite]