Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Results 1 to 5 of 5

Thread: Closest point on a Vector to a point

  1. #1
    Junior Member Newbie
    Join Date
    Jun 2004
    Posts
    2

    Closest point on a Vector to a point

    I have a vector and a point, p1. I want to find the closest point along the vector to p1. I've read about finding the closest point on a line to a point, but I think choosing arbitrary points on the vector is not the way to go.

  2. #2
    Junior Member Newbie
    Join Date
    Jun 2004
    Location
    Tsinghua Univ.,BeiJing,China
    Posts
    4

    Re: Closest point on a Vector to a point

    i cannot figure out what do u mean by "a point on a vector". A vector is sth. having length and direction,but no inherent location. So, to express a point, say P,you can do it as following:
    P = P0 + Vector

  3. #3
    Junior Member Regular Contributor
    Join Date
    Apr 2001
    Location
    U.S.
    Posts
    149

    Re: Closest point on a Vector to a point

    The closest point on a line to another point p1 is the intersection of the line with a perpendicular line formed from the point p1 to the line. If testing with line segment rather than a line constrain to extents of segment.

    Graphics GEMS has a lot of info for stuff like this. You might also look at Dave Eberley's code page at http://www.magic-software.com.

  4. #4
    Advanced Member Frequent Contributor plasmonster's Avatar
    Join Date
    Mar 2004
    Posts
    739

    Re: Closest point on a Vector to a point

    For a point P, and a normalized vector V, the point closest to P along V is

    P' = V * dot( P, V )

    In words, it's V scaled by the projection of P onto V.

  5. #5
    Senior Member OpenGL Pro
    Join Date
    May 2000
    Location
    Hannover, Germany
    Posts
    1,074

    Re: Closest point on a Vector to a point

    Alright, to make it more school-style i give an absolutely easy explanation, hehe.

    P2 is the point from which you want to have the closest point on the line.

    Pr is the closest point. (your result)

    P1 is a point on the line. v is the direction vector of the line L. So the parametric equation of the line is L(t) = (P1 + t*v).

    The closest point on the line L is the point where the line perpendicular to L and through your Pt intersects L. This means the points P1, Pr and P2 form a rightangled triangle.
    The two know edges of it are v and (P2-P1). The cosine of the angle they are enclosing is

    Code :
                 (Pt-P1)dot(v)
    cos(alpha) = -------------
                  |Pt-P1|*|v|
    as anyone should have learned in school, hehe. In the right angled triangle this cosine is the quotient

    Code :
                   near leg
    cos(alpha) =  -----------
                  hypothenuse
    Since we know the length of the hypothenuse (|P2-P1|) we can calculate the SIGNED length of the near leg:

    Code :
          (P2-P1)dot(v)
    len = ------------- * |P2-P1|
           |P2-P1|*|v|
     
      (P2-P1)dot(v)
    = -------------
           |v|
    This near leg is exactly the SIGNED distance on the line from P1 to Pr (which is the near leg in our rightangled triangle at P1 after all).
    So we have to scale t*|v| in our line equation to that length:

    Code :
    len        (P2-P1)dot(v)        (P2-P1)dot(v)
    --- * v =  ------------- * v =  ------------- * v
    |v|           |v|*|v|             (v)dot(v)
    |v| = sqrt(sum(vi * vi) thus |v|*|v| = sum(vi*vi) = (v)dot(v). If |v| is 1, then (v)dot(v) is 1.

    In our line equation that is finally:

    Code :
               (P2-P1)dot(v)
    Pr = P1 +  ------------- * v.
                 (v)dot(v)
    When v is prenormalized (v=v/|v|, set to length 1) you save the division by (v)dot(v). When P1 is additionaly the origin, then you end up at Sean's equation.
    - Michael Steinberg

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •