Finding The Shortest Distance Between Two 3D Line Segments

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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: https://www.geometrictools.com/Documentation/DistanceLine3Line3.pdf

There is even an implementation linked inside the PDF: https://www.geometrictools.com/GTE/Mathematics/DistSegmentSegment.h