1. We're looking for feedback on Unity Starter Kits! Let us know what you’d like.
    Dismiss Notice
  2. Unity 2017.2 beta is now available for download.
    Dismiss Notice
  3. Unity 2017.1 is now released.
    Dismiss Notice
  4. Introducing the Unity Essentials Packs! Find out more.
    Dismiss Notice
  5. Check out all the fixes for 5.6 on the patch releases page.
    Dismiss Notice
  6. Help us improve the editor usability and artist workflows. Join our discussion to provide your feedback.
    Dismiss Notice

How do i find the closest point on a line?

Discussion in 'Scripting' started by Nanako, Jul 11, 2015.

  1. Nanako

    Nanako

    Joined:
    Sep 24, 2014
    Posts:
    1,047
    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
     
  2. Kiwasi

    Kiwasi

    Joined:
    Dec 5, 2013
    Posts:
    13,876
    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.
     
  3. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    4,582
    line_dot.png

    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.
     
    Last edited: Jul 11, 2015
    Graph and Kiwasi like this.
  4. Kiwasi

    Kiwasi

    Joined:
    Dec 5, 2013
    Posts:
    13,876
    Apparently its been too long since I was in linear algebra class. @lordofduct's solution blows mine out of the water.
     
    lordofduct likes this.
  5. hpjohn

    hpjohn

    Joined:
    Aug 14, 2012
    Posts:
    1,914
  6. Nanako

    Nanako

    Joined:
    Sep 24, 2014
    Posts:
    1,047
    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
     
  7. Nanako

    Nanako

    Joined:
    Sep 24, 2014
    Posts:
    1,047
    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?
     
  8. Kiwasi

    Kiwasi

    Joined:
    Dec 5, 2013
    Posts:
    13,876
    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.
     
  9. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    4,582
    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.  
     
    Aily, Graph and Nanako like this.