Algorithm 2
[Home] [Overview] [History] [Algorithms] [Books] [Web Sites] [Gift Shop]

About Lines and
Distance of a Point to a Line (2D & 3D)

by Dan Sunday

Distance computations are fundamental in computer graphics and computational geometry, and there are well-known formulas for them.  Nevertheless, due to differences in object representations, there are alternative solutions to choose from.  We will give some of these and indicate the situations they apply to.

Throughout, we need to have a metric for calculating the distance between two points.   We assume this is the standard Euclidean metric L₂ norm based on the Pythagorean theorem.  That is, for an n-dimensional vector v=(v₁,v₂,...,v_n), its length |v| is given by:

and for two points P=(p₁,p₂,...,p_n) and Q=(q₁,q₂,...,q_n), the distance between them is:

About Lines

A point is that which has no part. [Book I, Definition 1]
A line is breadthless length. [Book I, Definition 2]
The extremities of a line are points. [Book I, Definition 3]
A straight line is a line which lies evenly with the points on itself. [Book I, Definition 4]

To draw a straight line from any point to any point. [Book I, Postulate 1]
To produce a finite straight line continuously in a straight line. [Book I, Postulate 2]
[Euclid, 300 BC]

The primal way to specify a line L is by giving two distinct points, P₀ and P₁, on it.  In fact, this defines a finite line segment going from P₀ to P₁ which are the endpoints of L.  This is how the Greeks understood straight lines, and it coincides with our natural intuition for the most direct  and shortest path between the two endpoints.  This line can then be extended indefinitely beyond either endpoint producing infinite rays in both directions.  When extended simultaneously beyond both ends, one gets the concept of an infinite line which is how we often think of it today.  However, for the Greeks, the line was the finite segment which could be extended indefinitely using a straight edge.  One nice thing about defining lines this way is that it works for all dimensions: 2D, 3D, or any n-dimensional space.  Further, it is common in applications to have lines specified as segments given by their endpoints since finite segments often occur as an edge of a polygon, polyhedron, or an embedded graph.

A line L can also be defined by a point and a direction.  Let P₀ be a point on L and v_L be a nonzero vector giving the direction of the line.  This is equivalent to the two point definition, since we could just put v_L=(P₁-P₀).  Or, given P₀ and v_L, we could select P₁=P₀+v_L as a second point on the line.  If v_L is normalized to be the unit direction vector, u_L=v_L/|v_L|, then its components are the direction cosines of L.  That is, in n-dimensions, let q_i (i=1,n) be the angle that L makes with the i-th axis a_i (for example, in 2D, a₁ is the x-axis and a₂ is the y-axis).  Then, the vector v_L = (v_i), with v_i = cos(q_i) for each i, is a direction vector for L.  In 2D, as shown in the diagram, if q is the angle L makes with the x-axis, then cos(q₂) = sin(q), and v_L = (cos(q₁), cos(q₂)) = (cos(q), sin(q)) is a unit direction vector for L.  It is a unit vector since: cos²(q) + sin²(q) = 1.  Similarly in any dimension, the squares of the direction cosines sum to 1, that is: S_i=1,n cos²(q_i) = 1.

Line Equations

Lines can also be defined by equations using the coordinates of points on the line as unknowns.  The usual types of equations that one encounters in practice are the following:

The 2D explicit equation is the one most people are first taught in school, but it is not the most flexible one to use in computational software.  The implicit equation is a bit more useful, and the conversion of an explicit to an implicit equation is easy to do.  Note that the first two implicit coefficients always define a vector n_L=(a,b) which is perpendicular to the line L.  This is because for any two points P₀=(x₀,y₀) and P₁=(x₁,y₁) on L, we have n_L·v_L = (a,b)·(P₁-P₀) = a(x₁-x₀) + b(y₁-y₀) =  f(P₁) - f(P₀) = 0.  Hence, given a normal vector n_L=(a,b) to the line L and a point P₀ on it, the normal form of the implicit equation is:

This equation is said to be normalized if  a² + b² = 1 and thus |n| is a unit normal vector.  [I know this overuse of the word "normal" may be confusing, but that's the terminology in current use.]

However, a single implicit (or explicit) equation only defines a line in 2D, whereas in 3D a single linear equation defines a plane and in n-dimensions it defines an (n-1)-dimensional hyperplane [Hanson, 1994].  This, of course, is useful in its own right, but it is not our interest here.  For further information about 3D planes, see the Algorithm 4 discussion about  Planes and the Distance of a Point to a Plane.

On the other hand, in any n-dimensional space, the parametric equation for the line is valid and is the most versatile one to use.  For a line defined by two points P₀ and P₁ with a direction vector v_L, the equation can be written several ways; namely:

where t is a real number.  For this representation P(0)=P₀ , P(1)=P₁ , and P(t) with 0<t<1 is a point on the finite segment between P₀ and P₁ where t is the fraction of P(t)'s distance along the whole P₀P₁ line segment.  That is, t = d(P₀,P(t)) / d(P₀,P₁).  So, P(1/2)=(P₀+P₁)/2 is the midpoint of the segment.  Further, if t<0 then P(t) is outside the segment on the P₀ side, and if t>1 then P(t) is outside the segment on the P₁ side.

One can convert from any of these representations to another when convenient.  For example, given two points P₀=(x₀,y₀) and P₁=(x₁,y₁) on a 2D line, one can derive an implicit equation for it as follows.  With v_L=(x_v,y_v)=P₁-P₀=(x₁-x₀, y₁-y₀) for the line direction vector, we have n_L=(-y_v,x_v)=(y₀-y₁,x₁-x₀) is a normal vector perpendicular to L (since n_L·v_L= 0).  Then, an implicit equation for L is:

where the coefficients of x and y are the components of n_L. 

For example, in 2D, if a line L makes an angle q with the x-axis, recall that v_L = (cos(q), sin(q)) is a unit direction vector, and thus n_L = (-sin(q), cos(q)) is a unit normal vector.  If P₀=(x₀,y₀) is a point on L, then a normalized implicit equation for L is:

since: sin²(q) + cos²(q) = 1.  Further, the parametric line equation is:

Distance of a Point to an Infinite Line

Given a line L and any point P, let d(P,L) denote the distance from P to L.  This is the shortest distance separating P and L.  If L is an infinite line, then this is the length of a perpendicular dropped from P to L.  However if L is a finite segment, then the base of the perpendicular may be outside the segment, and a different determination of the shortest distance needs to be made.  We first consider perpendicular distance to an infinite line.

A 2-Point Line

In 2D and 3D, when L is given by two points P₀ and P₁, one can use the cross-product to directly compute the distance from any point P to L.  The 2D case is handled by embedding it in 3D with a third z-component = 0.  The key observation to make is that the magnitude of the cross-product of two 3D vectors is equal to the area of the parallelogram spanned by them, since |v×w| = |v| |w| |sin q| where q  is the angle between the two vectors v and w.  However, this area is also equal to the magnitude of the base times the height of the parallelogram, and we can arrange the geometry so that the height is the distance d(P,L).  Let v_L=P₀P₁=(P₁-P₀) and w=P₀P=(P-P₀) as in the diagram:

Then, |v_L× w| = Area( parallelogram(v_L,w) ) = |v_L| d(P,L) which results in the easy formula:

where u_L = v_L / |v_L| is the unit direction vector of L.  If one is computing the distances of many points to a fixed line, then it is most efficient to first calculate u_L.

For the embedded 2D case with P=(x,y,0), the cross-product becomes:

and the distance formula is:

We did not take the absolute value of the numerator here making this is a signed distance with positive values on one side of L and negative distances on the other.  This can sometimes be useful.  Other times one may want to take the absolute value.  Also note the similarity of the numerator and the implicit line equation previously given.

A 2D Implicit Line

In 2D, there are many situations where a line L is most easily defined by an implicit equation f(x,y) = ax+by+c = 0.  For any 2D point P=(x,y), the distance d(P,L) can be computed directly from this equation. 

Recall that the vector n_L=(a,b) is a "normal" (perpendicular) vector to the line L.  Using n_L, we can compute the distance of an arbitrary point P to L by first selecting any specific point P₀ on L and then projecting the vector P₀P onto n_L. as shown in the diagram:

Writing out the details, we have:
    (1) since not both a and b are zero, assume a!=0 and select P₀=(-c/a,0) which is on the line  [Otherwise, if a=0 then b!=0, and select P₀=(0,-c/b) instead, which yields the same final result]
    (2) for any P₀ on L we have:  n_L · P₀P = |n_L| |P₀P| cos q = |n_L| d(P,L)
    (3) also for our specific P₀:  n_L · P₀P = (a,b) · (x+c/a, y) = ax+c+by = f(x,y) = f(P)
and equating (2) and (3) yields the formula:

Further, one can divide the coefficients of f(x,y) by |n_L| to prenormalize the implicit equation so that |n_L|=1.  This results in the very efficient formula:

which has only 2 multiplications and 2 additions for each distance calculation.  So, if in 2D one needs to compute the distances of many points to the same infinite line L, then one should derive the unit normalized implicit equation and use this formula.  Also note that if one is just comparing distances (say, to find the closest or farthest point to the line), then normalizing is not needed since it just changes all computed distances by a constant factor.

Recall that when L makes an angle q with the x-axis and P₀=(x₀,y₀) is a point on L, then the normalized implicit equation has: a = -sin(q), b = cos(q), and c = sin(q)x₀ - cos(q)y₀.

A Parametric Line

To compute the distance d(P,L) (in any n-dimensional space) from an arbitrary point P to a line L given by a parametric equation, suppose that P(b) is the base of the perpendicular dropped from P to L.  Let the parametric line equation be given as: P(t)=P₀ + t (P₁-P₀).  Then, the vector P₀P(b) is the projection of the vector P₀P onto the segment P₀P₁, as shown in the diagram:

So, with v_L=(P₁-P₀) and w=(P-P₀), we get that:

and thus:

where u_L is our friend the unit direction vector of L.

This computation has the advantage of working for any dimension n and of also computing the base point P(b) which is sometimes useful.  In 3D, it is just as efficient as the cross product formula.  But in 2D, when P(b) is not needed, the implicit method is better, especially if one is computing the distances of many points to the same line.

Distance of a Point to a Ray or Segment

A ray is a half line originating at a point P₀ and extending indefinitely in some direction.  It can be expressed parametrically as P(t) for all t>=0 with P(0)=P₀ as the starting point.  A finite segment consists of the points of a line that are between two endpoints P₀ and P₁.  Again, it can be represented by a parametric equation with P(0)=P₀ and P(1)=P₁ as the endpoints and the points P(t) for 0<=t<=1 as the segment points.

The thing that is different about computing distances of a point P to a ray or a segment is that the base P(b) of the perpendicular from P to the extended line L may be outside the range of the ray or segment.  In this case, the actual shortest distance is from the point P to the start point of the ray or one of the endpoints of a finite segment.

For a ray there is only one choice, but for a segment one must determine which end of the segment is closest to P.  One could just compute both distances and use the shortest, but this is not very efficient.  Also, one must first determine that P's perpendicular base is actually outside the segment's range.  An easy way to do this is to consider the angles between the segment P₀P₁ and the vectors P₀P and P₁P from the segment endpoints to P.  If either of these angles is 90º , then the corresponding endpoint is the perpendicular base P(b).  If the angle is not a right angle, then the base lies to one side or the other of the endpoint according to whether the angle is acute or obtuse.  These conditions are easily tested by computing the dot product of the vectors involved and testing whether it is positive, negative, or zero.  The result determines if the distance should be computed to one of the points P₀ or P₁, or as the perpendicular distance to the line L itself.  This technique, which works in any n-dimensional space, is illustrated in the diagram:

Further note that the two tests can be done just using the two dot products w₀·v and v·v which are also the numerator and denominator of the formula to find the parametric base of the perpendicular from P to the extended line L of the segment S.  This lets us streamline the algorithm as shown in the pseudocode:

However, in the 2D case, if we need to compute distances from many points to the same ray or segment, it can still be more efficient to use a normalized implicit equation to do an initial test for whether a point P has a new minimum distance from L.  In practice, the details of a specific application will decide which is the most efficient method to use.

Implementations

Here are a few sample "C++" applications using these algorithms.  We assume that the low level classes and functions are already given.

// Copyright 2001, softSurfer (www.softsurfer.com)
// This code may be freely used and modified for any purpose
// providing that this copyright notice is included with it.
// SoftSurfer makes no warranty for this code, and cannot be held
// liable for any real or imagined damage resulting from its use.
// Users of this code must verify correctness for their application.

// Assume that classes are already given for the objects:
//    Point and Vector with
//        coordinates {float x, y, z;} (z=0 for 2D)
//        appropriate operators for:
//            Point  = Point ± Vector
//            Vector = Point - Point
//            Vector = Scalar * Vector
//    Line with defining endpoints {Point P0, P1;}
//    Segment with defining endpoints {Point P0, P1;}
//===================================================================

// dot product (3D) which allows vector operations in arguments
#define dot(u,v)   ((u).x * (v).x + (u).y * (v).y + (u).z * (v).z)
#define norm(v)    sqrt(dot(v,v))  // norm = length of vector
#define d(u,v)     norm(u-v)       // distance = norm of difference

// closest2D_Point_to_Line(): finds the closest 2D Point to a Line
//    Input:  an array P[] of n points, and a Line L
//    Return: the index i of the Point P[i] closest to L
int
closest2D_Point_to_Line( Point P[], int n, Line L)
{
    // Get coefficients of the implicit line equation.
    // Do NOT normalize since scaling by a constant
    // is irrelevant for just comparing distances.
    float a = L.P0.y - L.P1.y;
    float b = L.P1.x - L.P0.x;
    float c = L.P0.x * L.P1.y - L.P1.x * L.P0.y;

    // initialize min index and distance to P[0]
    int mi = 0;
    float min = a * P[0].x + b * P[0].y + c;
    if (min < 0) min = -min;    // absolute value

    // loop through Point array testing for min distance to L
    for (i=1; i<n; i++) {
        // just use dist squared (sqrt not needed for comparison)
        float dist = a * P[i].x + b * P[i].y + c;
        if (dist < 0) dist = -dist;   // absolute value
        if (dist < min) {    // this point is closer
            mi = i;          // so have a new minimum
            min = dist;
        }
    }
    return mi;    // the index of the closest Point P[mi]
}
//===================================================================

// dist_Point_to_Line(): get the distance of a point to a line.
//    Input:  a Point P and a Line L (in any dimension)
//    Return: the shortest distance from P to L
float
dist_Point_to_Line( Point P, Line L)
{
    Vector v = L.P1 - L.P0;
    Vector w = P - L.P0;

    double c1 = dot(w,v);
    double c2 = dot(v,v);
    double b = c1 / c2;

    Point Pb = L.P0 + b * v;
    return d(P, Pb);
}
//===================================================================

// dist_Point_to_Segment(): get the distance of a point to a segment.
//    Input:  a Point P and a Segment S (in any dimension)
//    Return: the shortest distance from P to S
float
dist_Point_to_Segment( Point P, Segment S)
{
    Vector v = S.P1 - S.P0;
    Vector w = P - S.P0;

    double c1 = dot(w,v);
    if ( c1 <= 0 )
        return d(P, S.P0);

    double c2 = dot(v,v);
    if ( c2 <= c1 )
        return d(P, S.P1);

    double b = c1 / c2;
    Point Pb = S.P0 + b * v;
    return d(P, Pb);
}
//===================================================================

References

David Eberly, "Distance Between Point and Line, Ray, or Line Segment", Magic Software

Euclid, The Elements, Alexandria (300 BC)

Andrew Hanson, "Geometry for N-Dimensional Graphics"  in Graphics Gems IV (1994)

Thomas Heath, The Thirteen Books of Euclid's Elements, Vol 1 (Books I and II) (1956)

Jack Morrison, "The Distance from a Point to a Line", in Graphics Gems II (1994)

Copyright © 2001-2006 softSurfer.  All rights reserved.
Email comments and suggestions to feedback@softsurfer.com