CodeGuru Forums - Distance between point and line segment

CodeGuru Forums (http://www.codeguru.com/forum/index.php)

- C++ (Non Visual C++ Issues) (http://www.codeguru.com/forum/forumdisplay.php?f=9)

- - Distance between point and line segment (http://www.codeguru.com/forum/showthread.php?t=194400)

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. :)

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;

}

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))

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.

Quote:

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);

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.