CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 22
  1. #1
    Join Date
    Nov 2001
    Location
    In your dreams...
    Posts
    169

    Unhappy Distance between point and line segment

    I'm having one of those brain fart days. (Lack of sleep on a Friday and all that.)

    Could anyone please help by sending in a nice and simple algorithm for determining the shortest distance between a point (px,py) and a line segment(x1,y1)-(x2,y2)? Thanks.

  2. #2
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,721
    Here is a function that calculates both the distance to the line segment and the distance to the line (assuming infinite extent).
    I have a sample OpenGL graphics project I can attach which tests the function out if you want (as well as a couple of other small "mathematical" tasks such as this).

    Code:
    void DistanceFromLine(double cx, double cy, double ax, double ay ,
    					  double bx, double by, double &distanceSegment,
    					  double &distanceLine)
    {
    
    	//
    	// find the distance from the point (cx,cy) to the line
    	// determined by the points (ax,ay) and (bx,by)
    	//
    	// distanceSegment = distance from the point to the line segment
    	// distanceLine = distance from the point to the line (assuming
    	//					infinite extent in both directions
    	//
    
    /*
    
    Subject 1.02: How do I find the distance from a point to a line?
    
    
        Let the point be C (Cx,Cy) and the line be AB (Ax,Ay) to (Bx,By).
        Let P be the point of perpendicular projection of C on AB.  The parameter
        r, which indicates P's position along AB, is computed by the dot product 
        of AC and AB divided by the square of the length of AB:
        
        (1)     AC dot AB
            r = ---------  
                ||AB||^2
        
        r has the following meaning:
        
            r=0      P = A
            r=1      P = B
            r<0      P is on the backward extension of AB
            r>1      P is on the forward extension of AB
            0<r<1    P is interior to AB
        
        The length of a line segment in d dimensions, AB is computed by:
        
            L = sqrt( (Bx-Ax)^2 + (By-Ay)^2 + ... + (Bd-Ad)^2)
    
        so in 2D:   
        
            L = sqrt( (Bx-Ax)^2 + (By-Ay)^2 )
        
        and the dot product of two vectors in d dimensions, U dot V is computed:
        
            D = (Ux * Vx) + (Uy * Vy) + ... + (Ud * Vd)
        
        so in 2D:   
        
            D = (Ux * Vx) + (Uy * Vy) 
        
        So (1) expands to:
        
                (Cx-Ax)(Bx-Ax) + (Cy-Ay)(By-Ay)
            r = -------------------------------
                              L^2
    
        The point P can then be found:
    
            Px = Ax + r(Bx-Ax)
            Py = Ay + r(By-Ay)
    
        And the distance from A to P = r*L.
    
        Use another parameter s to indicate the location along PC, with the 
        following meaning:
               s<0      C is left of AB
               s>0      C is right of AB
               s=0      C is on AB
    
        Compute s as follows:
    
                (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
            s = -----------------------------
                            L^2
    
    
        Then the distance from C to P = |s|*L.
    
    */
    
    
    	double r_numerator = (cx-ax)*(bx-ax) + (cy-ay)*(by-ay);
    	double r_denomenator = (bx-ax)*(bx-ax) + (by-ay)*(by-ay);
    	double r = r_numerator / r_denomenator;
    //
        double px = ax + r*(bx-ax);
        double py = ay + r*(by-ay);
    //     
        double s =  ((ay-cy)*(bx-ax)-(ax-cx)*(by-ay) ) / r_denomenator;
    
    	distanceLine = fabs(s)*sqrt(r_denomenator);
    
    //
    // (xx,yy) is the point on the lineSegment closest to (cx,cy)
    //
    	double xx = px;
    	double yy = py;
    
    	if ( (r >= 0) && (r <= 1) )
    	{
    		distanceSegment = distanceLine;
    	}
    	else
    	{
    
    		double dist1 = (cx-ax)*(cx-ax) + (cy-ay)*(cy-ay);
    		double dist2 = (cx-bx)*(cx-bx) + (cy-by)*(cy-by);
    		if (dist1 < dist2)
    		{
    			xx = ax;
    			yy = ay;
    			distanceSegment = sqrt(dist1);
    		}
    		else
    		{
    			xx = bx;
    			yy = by;
    			distanceSegment = sqrt(dist2);
    		}
    
    
    	}
    
    	return;
    }
    Last edited by Philip Nicoletti; June 14th, 2002 at 05:52 PM.

  3. #3
    Join Date
    Jun 1999
    Location
    San Diego, CA
    Posts
    600
    Obviously Philip Nicoletti's code is a bad example, since it used "if" and "else", No boolean logic should be involved in a simple calculation like determing the distance from a point to a line segment.

    Suppose you have points A(xa, ya), B(xb, yb) and C(xc,yc). The distance between point C and line segment AB equals the area of parallelgram ABCC' divided by the length of AB.

    So it can be written as simple as:
    distance = |AB X AC| / sqrt(AB * AB)
    Here X mean cross product of vectors, and * mean dot product of vectors. This applied in both 2 dimentional and three dimentioanl space.

    In 2-D it becomes:
    sqrt(((yb-ya)*(xc-xa)+(xb-xa)*(yc-ya))^2/((xb-xa)^2 + (yb-ya)^2))

  4. #4
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,721
    Hi Anthony. Thanks (I think) for your comments on my code.
    I am not really interested in getting into a discussion
    about that, but I will mention something about that later.

    I am more interested in the solution algorithm. Maybe I am
    missing something, but I do not think your solution is correct.

    The distance between point C and line segment AB equals the
    area of parallelgram ABCC' divided by the length of AB.
    If I am missing something, please let me know as I am interested
    in these types of small mathematical problems. Or maybe I am
    mis-interpreting your algorithm.

    Some tests. Following is what my code calculates :

    A(0,0) , B(1,0) , C(0.707,0.707) : distanceToLine = distanceToSegment = 0.707

    A(0,0) , B(1,0) , C(-0.707,0.707) : distanceToLine = 0.707 , distanceToSegment = 1.0

    A(0,0) , B(100,100) , C(200,-106) : distanceToLine = distanceToSegment = 216.37

    ======

    As for my use of if statements in the solution.

    • notice in calculating the distance from the point to the
      line not line segment, I did not use boolean
      logic. I did code it in multiple lines instead of one. I did
      this on purpose, so that the code would follow the given theory
      more closely. It would be an easy exercise for someone interested
      in the code to change this if desired.
    • Maybe there is an simple equation for finding the distance from
      the point to the line segment, but I am not aware of it
      (as I mentioned, I do not think your solution is correct). The
      algorithm I used for the case of the line yields info on
      whether the closest point is within the line segment or not. If
      it is not within the line segment, then the closest point is one
      of the end points of the segment. My code was designed to make that
      clear.
    • the code does more than just calculated the two distances, it also
      calculates the closest point to the line segment (although I
      did forget to pass those as arguments).
    • This was one of the first functions I wrote when learning C++ (I
      had Fortran code which did the same calculations). Although you did
      not mention it, there are a couple of things I would do differently
      now :

      1) I would check the the end points of the line segment are not the same
      (that is, the user really supplied a point only instead of a line segment).
      In which case I would simply return the distance from C to A. I do not
      really want to have a code that divides by zero !

      2) the prototype and typical call for my function is :

      Code:
      void DistanceFromLine(double cx, double cy, double ax, double ay ,
      	double bx, double by, double &distanceSegment,
      	double &distanceLine);
      //
      //
      //
      DistanceFromLine(cx,cy,ax,ay,bx,by,distanceSegment,distanceLine);
      The problem : from the typical call, there is no way to know that
      distanceSegment and distanceLine are modified. So intead, maybe I
      would do this instead :

      Code:
      void DistanceFromLine(double cx, double cy, double ax, double ay ,
      	double bx, double by, double *distanceSegment,
      	double *distanceLine);
      //
      //
      //
      DistanceFromLine(cx,cy,ax,ay,bx,by,&distanceSegment,&distanceLine);
    Last edited by Philip Nicoletti; June 16th, 2002 at 07:55 AM.

  5. #5
    Join Date
    Nov 2001
    Location
    In your dreams...
    Posts
    169

    Smile Thanks.

    Thanks for the help! It proved three things.
    1) That I was remembering how to calculate this correctly. While not the prettiest of code, my original routines produced the same results.
    2) That my stuff wasn't working not because of the point to segment distance calculation, but because my line segment placement was thrown off-kilter by my not taking the window-space to OpenGL-space aspect ratios into consideration. (Stupid of me, I know. It was just a looooong day.)
    3) That this forum is still full of cool and helpful people.

    Again, thanks. Without your help I'd still be trying to figure out how to fix the wrong thing.

  6. #6
    Join Date
    Jun 2009
    Posts
    3

    Re: Distance between point and line segment

    Quote Originally Posted by Anthony Mai View Post
    Obviously Philip Nicoletti's code is a bad example, since it used "if" and "else", No boolean logic should be involved in a simple calculation like determing the distance from a point to a line segment.

    Suppose you have points A(xa, ya), B(xb, yb) and C(xc,yc). The distance between point C and line segment AB equals the area of parallelgram ABCC' divided by the length of AB.

    So it can be written as simple as:
    distance = |AB X AC| / sqrt(AB * AB)
    Here X mean cross product of vectors, and * mean dot product of vectors. This applied in both 2 dimentional and three dimentioanl space.

    In 2-D it becomes:
    sqrt(((yb-ya)*(xc-xa)+(xb-xa)*(yc-ya))^2/((xb-xa)^2 + (yb-ya)^2))

    I believe your answer is incorrect - the area of the parallelogram is the det of the 2x2 matrix formed by the points: it should therefore be:

    Code:
    (yb-ya)*(xc-xa)-(xb-xa)*(yc-ya)

  7. #7
    Join Date
    May 2009
    Posts
    2,413

    Re: Distance between point and line segment

    Quote Originally Posted by Anthony Mai View Post
    Obviously Philip Nicoletti's code is a bad example, since it used "if" and "else", No boolean logic should be involved in a simple calculation like determing the distance from a point to a line segment.
    Finding the shortest distance to a line segment requires you to consider three distances; One to the line and two to the endpoints. To select the shortest of these requires logical statements because selection always does.

  8. #8
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,727

    Re: Distance between point and line segment

    There is this equation,







    from this website.
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  9. #9
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,727

    Re: Distance between point and line segment

    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  10. #10
    Join Date
    May 2009
    Posts
    2,413

    Re: Distance between point and line segment

    Quote Originally Posted by JohnW@Wessex View Post
    This may help too.
    I hope you know the difference between a line and a line segment?

  11. #11
    Join Date
    May 2001
    Location
    Germany
    Posts
    1,158

    Re: Distance between point and line segment

    can anyone explain why you are digging out a seven year old thread?

  12. #12
    Join Date
    Jun 2009
    Posts
    3

    Re: Distance between point and line segment

    Quote Originally Posted by Richard.J View Post
    can anyone explain why you are digging out a seven year old thread?
    My bad - I was researching how to find the distance between a line segment and a point. I found this on google, implemented the ingenious suggestion of using areas and discovered it to be flawed so registered to post a correction in the spirit of making the web a better place...

  13. #13
    Join Date
    May 2009
    Posts
    2,413

    Re: Distance between point and line segment

    Quote Originally Posted by arctanb View Post
    My bad - I was researching how to find the distance between a line segment and a point. I found this on google, implemented the ingenious suggestion of using areas and discovered it to be flawed so registered to post a correction in the spirit of making the web a better place...
    It's a good initiative.

    Now if people only new the difference between a line and a line segment.

  14. #14
    Join Date
    Jun 2009
    Posts
    3

    Re: Distance between point and line segment

    Quote Originally Posted by nuzzle View Post
    Now if people only new the difference between a line and a line segment.
    ... and indeed a ray

    OK I think it's time for me to stop unwittingly bumping this topic

  15. #15
    Join Date
    May 2009
    Posts
    2,413

    Re: Distance between point and line segment

    Quote Originally Posted by arctanb View Post
    ... and indeed a ray

    OK I think it's time for me to stop unwittingly bumping this topic
    Well, the problem has an optimal algoritmic solution I think (see for example 3D Game Engine Design by Eberly).

    But who knows, maybe someone comes up with something better. This happens too often to risk anything so please keep bumping the thread.

Page 1 of 2 12 LastLast

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured