Shortest distance to chain of line segments

Question

I'm trying to calculate the distance of the player to a few lines that intersect two points, and return the smallest distance (i.e. tell me which of the lines the player is closest to/how far the player is from it at any given point in time). The lines are finite, my game is in 3D.

I'm looking for a solution that doesn't involve just picking the midpoint of the line segments and detecting the shortest distance from the player. I can do that but ideally, I'd like something more precise.

I have tried to find a suitable formula but keep coming across ones that are for infinite lines rather than finite segments.

Answer 1

To find the distance of our point \$\vec P\$ to the line segment between points \$\vec A\$ and \$\vec B\$, we need the closest point on the line segment. We can represent such a point \$\vec Q\$ on the segment by:

$$\vec Q = \vec A + t (\vec B - \vec A)$$

for some scalar value \$ 0 \le t \le 1 \$, which ensures our point doesn't shoot off the ends of the segment.

To make our math simpler, let's define the "span" of the segment \$\vec S = \vec B - \vec A\$ and the "wander" of our point from the start of the segment, \$\vec W = \vec P - \vec A\$. This is effectively shifting the start of the segment to the origin, without changing any of the distances involved, so we eliminate one extra variable from the problem.

The squared distance of our point \$P\$ from the point \$t\$ of the way along the segment is then:

$$\begin{align} D^2 &= \left(\vec W - t\vec S \right)^2 \\ &= W^2 - 2t\left(\vec W \cdot \vec S\right) + t^2 S^2 \\ \frac {d D^2} {d t} &= -2 \left(\vec W \cdot \vec S\right) + 2 t S^2 \end{align}$$

We differentiate with respect to \$t\$, and set the result to zero to find the local minimum of this function at the closest point along the segment, \$t = t^*\$

$$\begin{align} -2 \left(\vec W \cdot \vec S\right) + 2 t^* S^2 &= 0 \\ 2 t^* S^2 &= 2 \left(\vec W \cdot \vec S\right)\\ t^* &= \frac{\vec W \cdot \vec S} {S^2} \end{align}$$

Now we can use this to find our closest point, like so:

Vector3 ClosestPointOnLineSegment(Vector3 segmentStart, Vector3 segmentEnd, Vector3 point) {
    // Shift the problem to the origin to simplify the math.    
    var wander = point - segmentStart;
    var span = segmentEnd - segmentStart;

    // Compute how far along the line is the closest approach to our point.
    float t = Vector3.Dot(wander, span) / span.sqrMagnitude;

    // Restrict this point to within the line segment from start to end.
    t = Mathf.Clamp01(t);

    // Return this point.
    return segmentStart + t * span;
}

Now you can find the closest point to the player by...

int closestIndex = -1;
float closestSquaredRange = Mathf.infinity;

for (int i = 1; i < points.Length; i++) {
    var closestPoint = ClosestPointOnLineSegment(
                            points[i-1],
                            points[i],
                            player.position
                       );

    var squaredRange = (player.position - closestPoint).sqrMagnitude;

    if(squaredRange < closestSquaredRange) {
        closestSquaredRange = squaredRange;
        closestIndex = i - 1;
    }
}

// Closest segment is the span from points[closestIndex] to points[closestIndex+1]