How do i find the closest point on a line?

Ok, i have a line, it starts at a point in space, and runs for x units in a specific direction, as well as the same distance in the opposite direction, It is of finite length

Given a random/arbitrary point in space, i need to find the closest point to it, which is on the aforementioned line.

I'm not exactly sure how to do this. It seems to me like it might be helpful to first convert my line into two vectors (the point at either end) but beyond that, i'm not sure where to go

 

3D space or 2D space? The mathematics is similar, but it helps to provide an example.

You can take advantage of the fact that the shortest distance from a straight line to a point will be perpendicular to the line. So the algorithm in 2D runs something like this.

1. Calculate the slope of a line perpendicular to your line.
2. Calculate a line that passes through your point with the slope determined above
3. Calculate the point that this new line intersects with the existing line

In 3D its pretty much the same, except you will be calculating a plane instead of a line in step 2. Higher dimensions all follow the same pattern.

You'll also want to deal with the special case that the point you find in 3 is past the ends of your line segment. In that case just clamp it to the nearest end of the line.

 

So lets take the scenario above. We have infinite line black, and point dark blue dot.

How we define an infinite line in vector math is as a point, and a unit vector to define the tangential of that line... the direction. In our image that point will be the red dot.

Now the shortest distance to this line is a straight shot to the line. This will result in a perpendicular line to that infinite line. This is the purple line in the picture.

If using this purple line, you draw a line from the red dot to its meeting point, and a line from the red dot to the blue dot. You get a right triangle (because that purple line is perpendicular).

We can calculate Red -> Blue, the hypotenuse. It's just the point we're working with subtracted by the red point that defines the infinite line.

We also know the angle between the blue line, and the red line... because the red line and black line are parallel. Lets call that angle theta.

With trig we know that:
blueline = B
redline = R
||B|| = magnitude of B, or length of B

cos(theta) * ||B|| = ||R||

We usually calculate the angle between to vectors as what?

theta = acos((a dot b) / (||a|| * ||b||))

Thing is, we're going to be cosining, a acos if we do that. And those magnitudes are going to cancel out in that balancing. Leaving that dot product behind.

There's a reason for this. Dot product does what we call "projects" one vector onto another.

If we project a vector onto a unit vector, it'll tell us how long in the dimension of that vector to go (this works because a unit vectors magnitude is 1, which is the identity value in that equation above... it effectively cancels it out). Our black line is defined as a point with a unit vector!

SO... if we dot product the blue line onto the vector in the direction of the black line. We'll get the length of... red. And we already know the direction of red.

So, lets assume our R is black line in this, a unit vector, and lets call that R'. If we replace accordingly where a = R' and b = B we get. But in our case R' is a unit vector for calculating the angle, because we're using the black line for that. SO, ||R'|| = 1.

acos((R' dot B) / (1 * ||B||))

insert into our previous equation:

cos(acos((R' dot B) / (1 * ||B||))) * ||B|| = ||R||

reduce:

||B|| * (R' dot B) / ||B|| = ||R||
R' dot B = ||R||

So if we take the dot product of the direction of blackline and the blueline, we get the length redline aught to be. And if we just multiply that by the direction of red/black line, add that to the start point, we get the end point.

Code (csharp):

1.  
2. //linePnt - point the line passes through
3. //lineDir - unit vector in direction of line, either direction works
4. //pnt - the point to find nearest on line for
5. public static Vector3 NearestPointOnLine(Vector3 linePnt, Vector3 lineDir, Vector3 pnt)
6. {
7.     lineDir.Normalize();//this needs to be a unit vector
8.     var v = pnt - linePnt;
9.     var d = Vector3.Dot(v, lineDir);
10.     return linePnt + lineDir * d;
11. }
12.  

Replace this with Vector2 if you wanted to do it in 2d. The operations are identical.

This technically even works in 4 dimensions... though the concept of a straight line in 4 dimensions gets really weird.

 

Apparently its been too long since I was in linear algebra class. @lordofduct's solution blows mine out of the water.

 

Indispensable:
http://wiki.unity3d.com/index.php/3d_Math_functions

 

These answers are very interesting and informative, though reading between the lines, it seems they're mostly overlong ways of telling me to use http://docs.unity3d.com/ScriptReference/Vector3.Project.html

I was already aware of that, however projection really only works if the line you're projecting onto is of infinite length, or at least long enough to have a perpendicular line to the target point. That often won't be the case in my situation

But BoredMormon does point out something that i missed, i suppose i could just clamp it to the nearest endpoint. I'll poke around with that

 

Now that i think about it, i'm not entirely clear on how i'd check if the resulting point falls on my little line. Or how i'd check if it's behind the origin (vector magnitude is always positive, no?)

Maybe define a bounding box and check if its within?

 

Nah, look at @lordofduct's diagram again. Simply check the distance between your start point and the point on the line is less then the distance between the start point and the end of the line.

 

Yeah, didn't notice that you said finite length. Thought you said infinite length.

So yeah, if it's finite, and the point that is found by projection (didn't know unity had a Project method, which is exactly all I did). But if the point you find by projection is off the line, just take the end point of the line in that direction.

Take the projection from a start point, and clamp the dot product to 0 -> length from start to end:

Code (csharp):

1.  
2. public static Vector3 NearestPointOnFiniteLine(Vector3 start, Vector3 end, Vector3 pnt)
3. {
4.     var line = (end - start);
5.     var len = line.magnitude;
6.     line.Normalize();
7.    
8.     var v = pnt - start;
9.     var d = Vector3.Dot(v, line);
10.     d = Mathf.Clamp(d, 0f, len);
11.     return start + line * d;
12. }
13.  

 

Old thread but I have a question about it.
The code provided gives the point on the line. To get the distance we substract both point and get magnitude like this :

Code (CSharp):

1.  
2.             lhs = v0 - start;
3.             dot = Vector2.Dot(lhs, dir);
4.             cut = start + dir * dot;
5.             distance = ((Vector2)v0 - cut).magnitude;
6.  

This add a magnitude call and a vector substraction.
Can't we just use the dot product without normalization to find the closest point to the line over many points THEN compute the distance if needed ? This would be faster.

Like this :

Code (CSharp):

1.  
2. dir = end - start; // NOT NORMALIZED
3.             lhs = vi - start;
4.             dot = Vector2.Dot(lhs, dir);
5.          
6. if(dot < previousDot)
7. {
8. closestPoint = vi;
9. previousDot = dot;
10. }
11.  

 

Where would you get the many points to iterate over? How do you know those points are on the line?

This would also mean having to iterate over many points which could also be slow.

 

I didn't say points where on the line but If we have many points on a plane which one is the closest to the line ?

 

Ok.

Well then that wasn't the question being answered.

The question was calculating the closest point on the line given a point in 3-space and a line in 3-space.

Basically given:


Where the blue dot is a point, the black line is a line. We want to find the point where red & purple meet.

...

In regards to the problem you're solving. If given many points on a plane, find the point closest to a line (my best understanding of the problem you're describing). Your answer won't actually solve the problem. Considering that the dot product doesn't actually give you a distance from the line (consider that if a given vi is behind the 'start' point, your dot product will be negative and therefore less than... even if it's hundreds of units behind the 'start'. Where behind means in the opposite direction of the vector from 'start' to 'end').

 

Interesting code, thanks.

I am really new to vectors, do you have solution for this scenario?
Having [AB] and [AC]

I would like to project the point C on [AB] (keeping the same distance from A)
And if [AC] is not long enough, C would just be added after B.

 

Just multiply the magnitude of AC onto the unit vector from AB.

Code (csharp):

1. var v = AC.magnitude * AB.normalized;

Not sure what you mean... do you mean if AB was not long enough? C would just end up after B? If so, then yeah, magnitude * unit vector will do that.

 

Thanks for answering fast,
It does not seem to work, can it be a problem if those segments are in the middle of my screens?

I mean the point A hasn't the position [0;0], it's a random position absolute to my screen

 

Well AC would have to be (C - A), and AB would have to be (B - A).

And I guess technically after that you might want to add v onto A to get that new position. But that's positioning... I was just going for the actual vector math portion of the math. So technically:

Code (csharp):

1. var pos = A + (C - A).normalized * (B - A).magnitude;

In the same respect, I may have misunderstood your question.

 

Thank you very much for this!

 

I saw that the code examples above compute the magnitude twice. Here is version with one Sqrt:

Code (CSharp):

1.  
2. /// <summary>
3. /// Closest point on a line segment from a given point in 3D.
4. /// </summary>
5. public static Vector3 ClosestPointOnLineSegment( float px, float py, float pz, float ax, float ay, float az, float bx, float by, float bz )
6. {
7.     float apx = px - ax;
8.     float apy = py - ay;
9.     float apz = pz - az;
10.     float abx = bx - ax;
11.     float aby = by - ay;
12.     float abz = bz - az;
13.     float abMag = abx * abx + aby * aby + abz * abz; // Sqr magnitude.
14.     if( abMag < Mathf.Epsilon ) return new Vector3( ax, ay, az );
15.     // Normalize.
16.     abMag = Mathf.Sqrt( abMag );
17.     abx /= abMag;
18.     aby /= abMag;
19.     abz /= abMag;
20.     float mu = abx * apx + aby * apy + abz * apz; // Dot.
21.     if( mu < 0 ) return new Vector3( ax, ay, az );
22.     if( mu > abMag ) return new Vector3( bx, by, bz );
23.     return new Vector3( ax + abx * mu, ay + aby * mu, az + abz * mu );
24. }
25. /// <summary>
26. /// Closest point on a line segment from a given point in 3D.
27. /// </summary>
28. public static Vector3 ClosestPointOnLineSegment( Vector3 p, Vector3 a, Vector3 b )
29. {
30.     return ClosestPointOnLineSegment( p.x, p.y, p.z, a.x, a.y, a.z, b.x, b.y, b.z );
31. }
32.