closest point to 2 skew lines in 3D
Steve
lines in 3D space given the directions v1 and v2 for the lines, as
well as a point in each line, p1 and p2.
L1: r=p1+t*v1
L2: r=p2+s*v2
I basically find t and s such that the distance between the lines is
minimized (which is equivalent to finding a line segment that is
simultaneously perpendicular to both L1 and L2). To find the point
cloest to both lines, I then find the midpoint of this
minimum_distance connecting line segment.
However, I recently came across the following code in an older post
(by Tom Davis, from 2002) on here, and I don't understand why it is
getting good results (I'm not even sure that he was looking for the
midpoint of the min_dist line segment or just pure intersections, but
this appears to work for me). Can anyone explain why setting the
problem up like this allows us to use the \ operator to get a
solution, or where this approach might be referenced? I've just
never seen this set up as a least squares problem before, and am
getting a bit hung up... Any help in understanding this would be
appreciated.
Thanks.
-Steve
a = [v1,-v2];
b = p2-p1;
x = a\b; % least squares solution
p3 = p1+x(1)*v1;
Roger Stafford
<srjm...@gmail.com> wrote:
---------------------
Yes it can be set up as a problem in least squares, though it is not the
way I personally would have approached it. As you say, points on L1 and
L2 can be expressed as:
r1 = p1+t*v1
r2 = p2+s*v2,
where t and s are scalars. What we want to do is find t and s which
minimizes the square of the distance between r2 and r1 - in other words,
which minimizes
((p2x+s*v2x)-(p1x+t*v1x))^2 +
((p2y+s*v2y)-(p1y+t*v1y))^2 +
((p2z+s*v2z)-(p1z+t*v1z))^2 =
((v1x*t-v2x*s) - (p2x-p1x))^2 +
((v1y*t-v2y*s) - (p2y-p1y))^2 +
((v1z*t-v2z*s) - (p2z-p1z))^2
Thus, this is a problem in linear least squares in which we wish to so
adjust linear coefficients t and s as to minimize the sum of the squares
of the three differences in the vector
[v1,-v2]*[t;s] - [p2-p1] = a*[t;s] - b.
Hence, t and s are obtained from the solution to a\b.
By the way, p3 is not the midpoint you seek. The midpoint would be at
(p1+x(1)*v1+p2+x(2)*v2)/2.
Roger Stafford
Steve
Sincerely,
Steve
Steve
I had gotten my original solution from the Schneider and Eberly text
(Geometric Tools for Computer Graphics, 2003).
They do it according to the following (in their own notation):
Lo(s)=P0+s*do
L1(t)=P1+t*d1
Let Q0=P0+sc*d0, Q1=P1+tc*d1, where the Q's are points on P0 and P1
where the distance is a minimum...
define v = Q0 - Q1
now, we note that dot(d0,v) = 0 and dot(d1,v) = 0 must both be
satisfied; Expanding definition of v and substitute yields:
dot(d0,d0)*sc-dot(d0,d1)*tc = -dot(d0,(P0-P1))
dot(d1,d0)*sc-dot(d1,d1)*tc = -dot(d1,(P0-P1))
let a=dot(d0,d0)
b=dot(d0,d1)
c=dot(d1,d1)
d=dot(d0,(P0-P1))
e=dot(d1,(P0-P1))
f=dot((P0-P1),(P0-P1))
Thus we have 2 eqns in 2 unknowns, solution is
sc = (b*e-c*d)/(a*c-b^2)
tc = (a*e-b*d)/(a*c-b^2)
We can now set tc=0, and solve for sc = -d/a...
Steve
> We can now set tc=0, and solve for sc = -d/a...
Roger Stafford
<srjm...@gmail.com> wrote:
> Actually, while I'm here, I should ask how you would approach it?
> ........
--------------------
The approach you described earlier, Steve, finds a least mean square
solution to three equations and two unknowns. I would have tended to get
only two equations and two unknowns that could be solved exactly, using
these equations:
dot((p2+s*v2)-(p1+t*v1)),v1) = 0
dot((p2+s*v2)-(p1+t*v1)),v2) = 0
These constitute two linear equations in the two unknowns, t and s, which
can then be solved for s and t.
However, I prefer the solution I just sent out on another thread,
"Distance between 2 lines in 3d space". Instead of solving for parameters
s and t, and then substituting these back into the original line
expressions, it gives a single, rather esthetically pleasing formula in
terms of vector cross and dot products. It assumes you start with four
points, but you can easily convert it to your point/vector form of the
problem.
Roger Stafford
nuk...@op.pl
Stafford) wrote:
> In article <1180374468.997186.142...@p77g2000hsh.googlegroups.com>, Steve
I don't know what happened but when I try to search for "Distance
between 2 lines in 3d space" thread there's none - it's gone. However
it's still avaiable under that link...