I have two Line Segments, represented by a 3D point at their beginning/end points.
Line:
class Line
{ public string Name { get; set; } public Point3D Start { get; set; } = new Point3D(); public Point3D End { get; set; } = new Point3D();
}The 3D points are just 3 doubles for coordinates X,Y and Z.
3DPoint:
class Point3D
{ public double X { get; set; } public double Y { get; set; } public double Z { get; set; }
}The Question:
Can I find the distance between two 'Lines' and the endpoints of that distance 'Line'. Here is an Image to Better Illustrate What I am trying to Achieve I know that this question seems programmatically oriented. But the true issue is a math question at heart. Thank you in advance for your understanding.
What I have:
Currently, I can successfully get the distance between the two lines with this code (Adapted From Here Using the Segment To Segment Section):
public double lineNearLine(Line l1, Line l2) { Vector3D uS = new Vector3D { X = l1.Start.X, Y = l1.Start.Y, Z = l1.Start.Z }; Vector3D uE = new Vector3D { X = l1.End.X, Y = l1.End.Y, Z = l1.End.Z }; Vector3D vS = new Vector3D { X = l2.Start.X, Y = l2.Start.Y, Z = l2.Start.Z }; Vector3D vE = new Vector3D { X = l2.End.X, Y = l2.End.Y, Z = l2.End.Z }; Vector3D w1 = new Vector3D { X = l1.Start.X, Y = l1.Start.Y, Z = l1.Start.Z }; Vector3D w2 = new Vector3D { X = l2.Start.X, Y = l2.Start.Y, Z = l2.Start.Z }; Vector3D u = uE - uS; Vector3D v = vE - vS; Vector3D w = w1 - w2; double a = Vector3D.DotProduct(u, u); double b = Vector3D.DotProduct(u, v); double c = Vector3D.DotProduct(v, v); double d = Vector3D.DotProduct(u, w); double e = Vector3D.DotProduct(v, w); double D = a * c - b * b; double sc, sN, sD = D; double tc, tN, tD = D; if (D < 0.01) { sN = 0; sD = 1; tN = e; tD = c; } else { sN = (b * e - c * d); tN = (a * e - b * d); if (sN < 0) { sN = 0; tN = e; tD = c; } else if (sN > sD) { sN = sD; tN = e + b; tD = c; } } if (tN < 0) { tN = 0; if (-d < 0) { sN = 0; } else if (-d > a) { sN = sD; } else { sN = -d; sD = a; } } else if (tN > tD) { tN = tD; if ((-d + b) < 0) { sN = 0; } else if ((-d + b) > a) { sN = sD; } else { sN = (-d + b); sD = a; } } if (Math.Abs(sN) < 0.01) { sc = 0; } else { sc = sN / sD; } if (Math.Abs(tN) < 0.01) { tc = 0; } else { tc = tN / tD; } Vector3D dP = w + (sc * u) - (tc * v); double distance1 = Math.Sqrt(Vector3D.DotProduct(dP, dP)); return distance1; }What I Need:
Is there any way to determine the endpoints of the displacement vector 'dP' from the code above? If not, can anyone suggest a better method for finding minimum distance and the endpoints of that distance?
Thank you for Reading, and Thanks in advance for any suggestions!
For those interested in the solution, I have posted a code complete version on my question HERE
$\endgroup$ 35 Answers
$\begingroup$I'm not sure about the correctness of the webpage linked by @amd (I don't have enough points to add a comment below it).
The author claims: 'However, in these cases, the minimum always occurs on the boundary of G, ...'.
Imagine the line segments defined by $ P_1=(-1,1,0)$, $ P_2=(1,-1,0) $ and $ Q_1=(-1,-1,1) $ and $ Q_2=(1,1,1) $. The shortest distance is not at the boundary of G. It is at s=t=0.5.
I think the correct theory is provided by this PDF:
There is even an implementation linked inside the PDF:
$\endgroup$ 0 $\begingroup$Take a look at the end of the “Distance between Lines” section of the web page from which you lifted your code:
Having solved for $s_C$ and $t_C$, we have the points $P_C$ and $Q_C$ on the two lines $\mathbf L_1$ and $\mathbf L_2$ where they are closest to each other.
These are exactly the points that you’re asking for. Reading a bit earlier in that section, you might discover that $P_C=P(s_C)$ and $Q_C=Q(t_C)$, and you can find the definitions for these functions at the top of the section. Now, the code for dist3d_Segment_to_Segment() doesn’t compute these two points explicitly, but it does compute $s_C\mathbf u$ and $t_C\mathbf v$, so you’re only two vector additions away from having $P_C$ and $Q_C$.
If we write the red line as $$\underline{r}=\underline{a}+\lambda\underline{b}$$ and the green line as $$\underline{r}=\underline{c}+\mu\underline{d}$$
Then the shortest distance between these lines is given by $$(\underline{c}-\underline{a})\cdot\frac{\underline{b}\times\underline{d}}{|\underline{b}\times\underline{d}|}.$$
this may well be what your code is doing.
To find the actual coordinates, you need to set up and solve simultaneous equations to find the values of $\lambda$ and $\mu$ Which are determined by the fact that the blue line is perpendicular to both red and green lines. In other words, $$((\underline{a}+\lambda\underline{b})-(\underline{c}+\mu\underline{d}))\cdot\underline{b}=0$$
And
$$((\underline{a}+\lambda\underline{b})-(\underline{c}+\mu\underline{d}))\cdot\underline{d}=0$$
$\endgroup$ 2 $\begingroup$HINT.-Let $A=(x_1,y_1,z_1);\space B=(x_2,y_2,z_2);\space C=(x_3,y_3,z_3);\space D=(x_4,y_4,z_4)$ One has $$(x,y,z)\in \overline{AB}\iff(x,y,z)=(x_1+tx_2,y_1+ty_2,z_1+tz_2)\space\text {where }0\le t\le 1$$ Similarly $$(w,u,v)\in \overline{CD}\iff(w,u,v)=(x_3+sx_4,y_3+sy_4,z_3+sz_4)\space\text {where }0\le s\le 1$$ Now find the minimun of the distance $D$ between the two points $(x,y,z)$ and $(w,u,v)$ (You could apply the method of Lagrange multipliers, for instance).
$\endgroup$ $\begingroup$Assuming that the first segment has endpoints $A,B$ and the second one has endpoints $C,D$,
we just have to minimize the quadratic form
$$ f(\lambda,\mu)=\left\|\lambda A+(1-\lambda)B-\mu C-(1-\mu)D\right\|^2 $$
over the square $(\lambda,\mu)\in[0,1]^2$, that is a common problem in optimization. If you do not care about the argmin being given by a segment with a vertex on $AB$ and a vertex on $CD$, you may just remove the last constraint and the problem boils down to finding a line that is orthogonal both to $AB$ and $CD$, an easy linear algebra problem.
