Wednesday, November 9, 2011

Using Vector Mathematic, Finding closest point on a line

In this post we will be looking at determining the closest point on a line from another point. This technique by itself isn't worth much, but it's required as part of other techniques, such as an intersection test between a line and a sphere, which I may post about later.

Describing how this works using only words is going to be tough. Lets start with a picture to help:



Of the points in this picture, only point B lies along the line segment. Technically you could say that the closest point on the segment to point A is P1, and to C is P2, but in most cases where you want the closest point on a line segment you want to exclude points that aren't going to lie in that segment, so we will exclude them for our purposes.

First we need to get some information setup that we'll be able to test with.
  1. We need a vector from P1 to P2, which is achieved by doing P2 - P1.
    Line difference vector is (5 - 0, 0 - 0, 0 - 0) = (5, 0, 0)
  2. We need the squared length of the vector we just got in step 1.
    I'm not even doing the math for this part, only one component is non-zero, which is the 5, so the   length in this case is 5, leaving squared length at 25.
  3. We need a vector from P1 to our test point (point B), which is B - P1.
    Point difference from P1 is (3 - 0, 0 - 0, -2 - 0) = (3, 0, -2)
Now we do the dot product between our line difference vector and our line to point vector
line diff ( dot ) line to point = ( 3*5 + 0*0 + -2*0 ) = 15

Notice that unlike previous posts, we don't unitize our difference vectors before doing a dot product. In this case we take that dot product and now divide it by the squared length.

Percentage from start to end point = 15 / 25 = 0.6 (0.6 is the same as saying 60%)

Note: We didn't test points A or C because we could see from the picture they weren't on the line segment, but normally you won't be able to just pick which point you want to test, you test every point, and if your value above (which for point B is 0.4) is less than 0.0 or greater than 1.0, then you know it's outside of the line segment.

Now, the closest point is calculated as such:
P1 + ( U * ( P2 - P1 ) )

Which for our example becomes this:
(0, 0, 0) + ( 0.6 * ( 0, 0, 5 ) ), which simplifies to ( 3, 0, 0 )

Here's the code for this:
Vector3 GetClosestPointOnLineSegment(const Vector3& LinePointStart, const Vector3& LinePointEnd,
                                     const Vector3& testPoint)
{
    const Vector3 LineDiffVect = LinePointEnd - LinePointStart;
    const float lineSegSqrLength = LineDiffVect.LengthSqr();

    const Vector3 LineToPointVect = testPoint - LinePointStart;
    const float dotProduct = LineDiffVect.dot(LineToPointVect);

    const float percAlongLine = dotProduct / lineSegSqrLength;

    if (  percAlongLine  < 0.0f ||  percAlongLine  > 1.0f )
    {
        // Point isn't within the line segment
        return Vector3::ZERO;
    }

    return ( LinePointStart + ( percAlongLine * ( LinePointEnd - LinePointStart ));
}

1 comment:

  1. This might be a daft question - you're returning a zeroed vector if the closest point is outwith the line, but what if the closest point happens to be at (0,0,0)? In the above example, if point B was (0, -2) then the closest point would be (0,0) but you'd think it was outwith since success/failure depends on the actual values of the returned vector (i.e all values at zero means failure, but in this case it should be success). How'd you get around that?

    ReplyDelete