[Math] Finding The Shortest Distance Between Two 3D Line Segments

3danalytic geometryvector-spaces

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

Best Answer

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

Related Question