Line-Line Intersection Method With C Code Sample

Line-Line Intersection Method With C Code Sample
©2006 Darel Rex Finley. This complete article, unmodified, may be freely distributed for educational purposes.

Suppose we have two line segments, each defined by two points. We want to know where the two lines intersect — even if the line segments do not, as in this illustration. (Note: It doesn't matter which end of each segment you choose to be point A or B, or point C or D, just as long as points A and B represent one line, and points C and D represent the other.)

line-line intersection

Step 1. Translate the coordinate system so that point A is now the origin:

line-line intersection

Step 2. Rotate the coordinate system so that point B is on the positive X-axis:

line-line intersection

Step 3. Thanks to linearity, the proportion of the large, vertical bracket to the smaller one must be exactly the same as the proportion of the large, horizontal bracket to the smaller one. This makes it easy to discover the point ABpos,0 (which is the intersection point, in this coordinate system).

line-line intersection

Step 4. Apply the value ABpos along the line A-B in the original coordinate system. This gives you the intersection point you wanted:

line-line intersection

C Code Sample

//  public domain function by Darel Rex Finley,
2006





//  Determines the intersection point of the line defined by points A and B with the

//  line defined by points C and D.

//

//  Returns YES if the intersection point was found, and stores that point in X,Y.

//  Returns NO if there is no determinable intersection point, in which case X,Y will

//  be unmodified.



bool lineIntersection(

double Ax, double Ay,

double Bx, double By,

double Cx, double Cy,

double Dx, double Dy,

double *X, double *Y) {



  double  distAB, theCos, theSin, newX, ABpos ;



  //  Fail if either line is undefined.

  if (Ax==Bx && Ay==By || Cx==Dx && Cy==Dy) return NO;



  //  (1) Translate the system so that point A is on the origin.


  Bx-=Ax; By-=Ay;

  Cx-=Ax; Cy-=Ay;

  Dx-=Ax; Dy-=Ay;



  //  Discover the length of segment A-B.

  distAB=sqrt(Bx*Bx+By*By);



  //  (2) Rotate the system so that point B is on the positive X axis.

  theCos=Bx/distAB;

  theSin=By/distAB;

  newX=Cx*theCos+Cy*theSin;

  Cy  =Cy*theCos-Cx*theSin; Cx=newX;


  newX=Dx*theCos+Dy*theSin;

  Dy  =Dy*theCos-Dx*theSin; Dx=newX;



  //  Fail if the lines are parallel.

  if (Cy==Dy) return NO;



  //  (3) Discover the position of the intersection point along line A-B.

  ABpos=Dx+(Cx-Dx)*Dy/(Dy-Cy);



  //  (4) Apply the discovered position to line A-B in the original coordinate
system.

  *X=Ax+ABpos*theCos;

  *Y=Ay+ABpos*theSin;



  //  Success.

  return YES; }

If you need to find out only when (and where) the line segments intersect, you can modify the function as follows:

//  public domain function by Darel Rex Finley,
2006





//  Determines the intersection point of the line segment defined by points A and B

//  with the line segment defined by points C and D.

//

//  Returns YES if the intersection point was found, and stores that point in X,Y.

//  Returns NO if there is no determinable intersection point, in which case X,Y will

//  be unmodified.



bool lineSegmentIntersection(

double Ax, double Ay,

double Bx, double By,

double Cx, double Cy,

double Dx, double Dy,

double *X, double *Y) {



  double  distAB, theCos, theSin, newX, ABpos ;



  //  Fail if either line segment is zero-length.

  if (Ax==Bx && Ay==By || Cx==Dx && Cy==Dy) return NO;



  //  Fail if the segments share an end-point.

  if (Ax==Cx && Ay==Cy || Bx==Cx && By==Cy

  ||  Ax==Dx && Ay==Dy || Bx==Dx && By==Dy) {

    return NO; }



  //  (1) Translate the system so that point A is on the origin.


  Bx-=Ax; By-=Ay;

  Cx-=Ax; Cy-=Ay;

  Dx-=Ax; Dy-=Ay;



  //  Discover the length of segment A-B.

  distAB=sqrt(Bx*Bx+By*By);



  //  (2) Rotate the system so that point B is on the positive X axis.

  theCos=Bx/distAB;

  theSin=By/distAB;

  newX=Cx*theCos+Cy*theSin;

  Cy  =Cy*theCos-Cx*theSin; Cx=newX;

  newX=Dx*theCos+Dy*theSin;

  Dy  =Dy*theCos-Dx*theSin; Dx=newX;



  //  Fail if segment C-D doesn't cross line A-B.

  if (Cy<0. && Dy<0. || Cy>=0. && Dy>=0.) return NO;



  //  (3) Discover the position of the intersection point along line A-B.

  ABpos=Dx+(Cx-Dx)*Dy/(Dy-Cy);



  //  Fail if segment C-D crosses line A-B outside of segment A-B.

  if (ABpos<0. || ABpos>distAB) return NO;



  //  (4) Apply the discovered position to line A-B in the original coordinate
system.

  *X=Ax+ABpos*theCos;

  *Y=Ay+ABpos*theSin;



  //  Success.

  return YES; }

Important: Both of the above functions return NO if the segments are colinear, even if they overlap.

Send me an e-mail!