# Line Segment Intersection

### From Progteam

// 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; }