-1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ The formula you chose from Wikipedia computes the distance from.the point to an infinite line that passes through both points and continues out each side without limit. What you want is the distance to a line segment that ends at those points. \$\endgroup\$ – DMGregory May 16 at 13:36
  • \$\begingroup\$ Thank you. Do you know if there's a way to get the distance to the edges of objects in Unity (not just say the point where you position an empty game object -- because this object will need to be invisible but placed where the players pass over the path segments I have in my game)? Maybe I could solve it that way, if there is. \$\endgroup\$ – Pete Bloom May 16 at 13:50
  • \$\begingroup\$ Presumably you looked at Collider.ClosestPoint? \$\endgroup\$ – DMGregory May 16 at 14:29
  • \$\begingroup\$ @DMGregory I'd seen that but thought it was just another way of detecting the distance between a point and the player. Or did I not read that closely enough? \$\endgroup\$ – Pete Bloom May 16 at 14:37
  • \$\begingroup\$ What did you try and how did the results differ from what you want? \$\endgroup\$ – DMGregory May 16 at 14:43
0
\$\begingroup\$

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]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.