Point-Line Distances
A common problem in robotics and computer graphics is calculating the proximity between objects, and the closest points of collision. This page contains some useful equations for the closest points between points and line segments, building up to the closest points between two line segments.
For each step along the way there is a 3D demo, a mathematical derivation, and some C++ish example code.
Don't worry if the equations seem a bit full-on, you'll see from the code examples that it's mostly pretty simple!
Note that while the demos are in 3D, all of these equations work exactly the same for 2D and 3D.
Here's a preview of the closest points between two line segments:
Some inspiration taken from this page.
Background & Assumptions
Below are the building blocks (both mathematical and code) that will be used in the rest of the page.
Geometric definition of dot product
Vector Length
Vector classes
Assume you have vector/point classes such as Vector2
or Vector3
that have x
/y
/(z
) fields and handle your arithmetic.
Dot product
Assume you have a function for it, e.g. dot(a,b) = a.x*.x + a.y*b.y + a.z*b.z
. If you are using a library this will usually come with the vector/point classes.
Interpolation
Interpolation is the process of selecting a point between two other points, often used for selecting a more appropriate value for a data point between discrete samples. One of the simplest interpolation methods is linear interpolation where the mixture of the two sample points is directly proportional to how far we have moved between them.
We use a variable , where is the first point, is the second point, and anywhere in between represents the fraction moved between the points. The value can also extend beyond the bounds: will be before the first point and will be past the second (when we do this it's technically called linear extrapolation).
One simple way to implement linear interpolation is:
lerp(a,b,t) = a + t*(b-a)
Clamping
To clamp a value between two bounds e.g. 0 and 1:
clamp01(a) = min(max(a,0),1)
Division by 0
Whenever we are dividing, we need to make sure our denominator is not 0 (or very small). The easiest way is to check if the absolute value is smaller than some very small number that we call epsilon
.
nearzero(val) = abs(val) < epsilon
Choosing an appropriate value for epsilon
is a complex topic and will depend on the kind of problems you're solving - the examples below are using 0.000001
.
Projecting a vector onto a vector
The key tool we will use over and over in these equations is projecting one vector onto another:
Let's say we have two vectors, and . We want to project onto to make - it's like 's shadow.
To construct we first come up with an equation for its length using trigonometry, and then substitute the geometric equation for the dot product.
We know that lies in the same direction as , so we can recover the whole vector by multiplying its length by the unit vector . The full derivation becomes:
We can see that is simply a scaled version of , where the scaling factor is . For simplicity we'll refer to this as in the following sections, such that:
It's important to understand that when , lies inside the original . When , grows longer than , and when it begins to extend in the opposite direction to .
Remember to check your denominator is valid so you don't divide by 0 - this implies that has no length or direction! What you want to do in this case depends on the particular problem you are solving.
Example Code
Vector ProjectVectorOntoVector(Vector u, Vector v)
{
double denominator = v.dot(v);
if (nearzero(denominator))
{
return Vector(); // You need to handle this error appropriately for your problem!
}
double t = u.dot(v) / denominator; // Create an extra variable to make things clearer
return t*v;
}
Closest point on infinite line to point
While we often want the shortest distance betwen a point and a line segment, it is helpful to first derive the distance between a point and an infinite line, then adjust the equation.
Let our line be defined by two points, and . The line runs between these points and also extends infinitely in either direction. Given any point , we want to find the closest point on our line (from which we can get its distance to ).
This looks very similar to our vector projection! We start by calculating and as the vectors from to and respectively:
We can then calculate the coordinates of our closest point by adding the projected vector back on to :
Since was just the vector from to , our scaling factor is linearly interpolating between them. Values between and will be between the two original defining points, will be off one end, off the other.
Example Code
Vector CalcClosestPointToLine(Vector P, Vector A1, Vector A2)
{
Vector u = P - A1;
Vector v = A2 - A1;
double denominator = v.dot(v);
if (nearzero(denominator))
{
return A1; // You need to handle this error appropriately for your problem!
}
double t = u.dot(v) / denominator; // Create an extra variable to make things clearer
return A1 + t*v;
// Alternative return options that might make more sense for you:
// return lerp(A1, A2, t);
// return A1 + ProjectVectorOntoVector(u,v); // (Skipping the calculations)
}
- If you already have your line defined as a point and a direction, you start with already, no need to calculate it!
- If you also already know that is a unit vector, you can use the knowledge that to simplify things. The denominator disappears completely and the result is .
Closest point on line segment to point
What about a line that isn't infinite?
This is almost identical to the previous example, except we want to clamp the point between the endpoints of the segment - when the result would otherwise go outside the ends, the end becomes the closest point.
By seeing the previous result as an interpolation from to by , all we need to do to clamp our result point is to clamp between and .
Where, again, we have:
In this case, if we divide by 0 (see warning on previous) we usually want to return the point that is the line segment, as it is guaranteed to be the closest.
Example Code
Vector ClosestPointToLineSegment(Vector P, Vector A1, Vector A2)
{
Vector u = P - A1;
Vector v = A2 - A1;
double denominator = v.dot(v);
if (nearzero(denominator))
{
return A1; // In this case returning A1 (or A2) is likely what you want
}
double t = u.dot(v) / denominator;
return lerp(A1, A2, clamp01(t));
}
Projecting a point onto a plane
Before we move to the next problem with line segments, we need another tool - projecting a point onto a plane.
Let's say we have a plane defined by a point and a normal vector , and we want to find , the projection of a point onto the plane.
We start by creating a vector from to , and projecting it onto . Since is a unit vector, this simplifies down:
Then, to get we just need to subtract from :
If you need the plane normal to a line segment defined by two points and (as we will in the next step), pick the one you want as (e.g. ) and then calculate the normal vector with:
Code example
Vector ProjectPointOntoPlane(Vector P, Vector A, Vector N)
{
Vector u = P - A;
Vector t = u.dot(N);
return P - t*N;
}
Closest point on line segment to infinite line
Next we'll see how to find the closest point on a line segment to an infinite line. This probably has some practical use, but we are mostly using it as a stepping-stone to finding the closest points between two segments.
Let's say our infinite line is defined by two points and , and our line segment by and
This is a three-step process:
-
Project the two points of the line segment ( and ) onto the plane defined by one point on the infinite line (), and its normal () to create and
-
Find the closest point between and the new projected line segment ( and ).
-
If we use the same value to interpolate between the two original points ( and ), we get , the closest point on the original line segment.
You might notice that we don't actually need , just its value.
Example Code
Vector ClosestPointOnLineSegToLine(Vector L1, Vector L2, Vector S1, Vector S2)
{
// Project the line segment onto the plane defined by the line
Vector n = (L2 - L1).normalize();
Vector S1a = ProjectPointOntoPlane(S1, L1, n);
Vector S2a = ProjectPointOntoPlane(S2, L1, n);
// Find the t value for the closest point in the projected space
Vector u = L1 - S1a;
Vector v = S2a - S1a;
double denominator = v.dot(v);
if (nearzero(denominator))
{
return S1; // You decide what to do here!
}
double t = u.dot(v) / denominator;
// Use the t value to interpolate between the ORIGINAL points
return lerp(S1, S2, clamp01(t));
}
Closest points between two line segments
Tip: Move the left-most green dot across to the right of the view to really see the steps below in action.
We're on the home stretch! This is a three-step process:
- Find , the closest point to the infinite line of one segment () on the finite segment of the other ().
- Find , the closest point to on segment . This is one of the the two final points.
- Find , the closest point to on segment .
The points from steps 2 and 3 are your closest points!
If at the end of step 1 you find that , you can skip step 3, as will be the same as !
If you know this will happen a lot it's worth taking into account in your code.
Code Example
(Vector,Vector) ClosestPointsBetweenLineSegments(Vector A1, Vector A2, Vector B1, Vector B2)
{
// Closest point on B to infinite A
Vector Bx = ClosestPointOnLineSegToLine(A1, A2, B1, B2);
// Closest point on finite A to that
Vector Ax = ClosestPointToLineSegment(Bx, A1, A2);
// Closest point on finite B to that
Vector Bxx = ClosestPointToLineSegment(Ax, B1, B2);
return (Ax, Bxx);
}