# Finding The Shortest Distance Between Two 3D Line Segments

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?

For those interested in the solution, I have posted a code complete version on my question HERE

• As I commented to you when you asked about this yesterday, the code for dist_3D_Segment_to_Segment() on that web page already does most of what you want and the derivation of the algorithm used in the code shows you how to find these points. Your code is basically identical to that on the web page. I suggest that you read it and its derivation more carefully and try to understand what sc * u and tc * v that are computed near the end of this cribbed code really are. – amd Jul 28 '16 at 18:29
• Using a single case with two known line segments and a known distance, I couldn't make any logical connection between scu and tcv to the correct endpoints. So, I reformulated my question to be more verbose and hopefully get a more helpful answer. – Kikootwo Jul 28 '16 at 19:44
• Ah, so the underlying problem here is that you don’t understand the code, the documentation, or both. Have you even read the derivation on that web page? It describes how to find the points you’re looking for explicitly, using essentially the same method as David Quinn describes in his answer. – amd Jul 29 '16 at 4:17

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$$

• Awesome, I would love to try out this solution. How can I create the equations of the lines that you're specifying from the endpoints of the segments? Also, will the shortest distance line always be perpendicular for line segments? – Kikootwo Jul 28 '16 at 14:37
• @Kikootwo This is exactly what the web page you cite in your question tells you to do. The code you cribbed already computes $\lambda$ and $\mu$, just by different names. – amd Jul 28 '16 at 18:35

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).

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.