Sunday, February 1, 2009

Distance from a line to a point

We often have a line and a point somewhere that we need to compare to our line. Distance between the line and the point is one way to measure this line and the point. In computer games, one of the most common interview questions is "how do I find the distance from a line to a point?" They usually mean what is the shortest distance and how do you calculate it. This has many applications such as the following:

1) Given a football player who is running toward the goal, what is the shortest distance another player needs to run to stop him.
2) If I fire my gun, does it strike that statue (treating the statue as a point, and bullet as a line)

It turns out that the shortest distance between a point in space and a line is a line connecting the point to the line at a perpendicular. There are many geometric and algebraic proofs for this and most are based on the Pythagorean Theorem.


There are a lot of ways to solve this problem: I can think of three at least (the one following, one with cross product, and another using a 'normal'). We're going to show the easiest here. Essentially, we are given a line and a point off of that line somewhere.







Now what we'd like to do is find the shortest distance from our line to the point. Given that we only have three points, we need some special knowledge which happens to come from precalculus. First we create a line between our point and one of the endpoints of our line. We're going to use a special property of two lines called the projection.






Once we have the projection, we know how far away from v1 a new point directly under pt would be. It is shown in red here and I have labeled it the shadow.









We're almost done. Now we ignore the extra line and we create a new point that is the shadow distance away from v1.








Lastly, we measure the distance from the new point to our original point and we're done.





If we are writing code, it looks just like this.

float DistanceFromPointToLine (const Vector& v1, // origin point
const Vector& v2,
const Vector& pt) //tested point
{
Vector connect1 = v2 - v1;
Vector connect2 = pt - v1;

// projection equation
float shadowDist = connect1.Dot (connect2) /
connect1.MagnitudeSquared ();// by using the squared value, we save some calculations later
// Clamp
if (
shadowDist < 0.0F) shadowDist = 0.0F;
if (shadowDist > 1.0F) shadowDist = 1.0F;

// shadowed point
Vector ClosestPoint = v1 +
shadowDist * connect1;// origin + n*v
// subtract the points
float dist = (pt-ClosestPoint).Magnitude ();
return dist;

}

No comments: