Testing for line segment intersection in 2D - a pedestrian approach

For the collision engine in a 2D game I've been working on, I often find myself needing to know whether or not two line segments intersect. A quick google search showed plenty of fancy approaches, but since I just want something quick, understandable and reliable, I went the high school math route.

First, the problem: given two line segments L1 and L2, (a) do they intersect? (b) if so, where?

Before the algorithm we have to choose how we represent our lines. I prefer defining a line segment by two points:
$p_1=\left(x_1,y_1\right)$ $p_2=\left(x_2,y_2\right)$
This is a totally fine way of representing a line or a line segment. Another way of writing a line is:
$y = mx+b$
where the slope m and intercept b are related to our points as in the diagram below.

A disadvantage of writing the line as a function of y is that a vertical line (with equation x=const) can not be represented in this manner. If we're working with this form we have to consider vertical lines separately, which is a bit of a bummer, but amounts to a mere if statement or two.

Simple example: infinite lines

It helps to first consider the case of two lines. As drawn below, if the slopes of the two lines are equal, they always intersect at a unique point. If the slopes are equal, the lines do not intersect unless they are the same line, in which case (almost by definition), they intersect everywhere.

The algorithm for finding the intersection is then as follows:

// Simplest case:
double m1 = (L1.x2-L1.x1)/(L1.y2-L1.y1)
double m2 = (L2.x2-L2.x1)/(L2.y2-L2.y1)
double b1 = (y1-m1*x1)
double b2 = (y2-m2*x2)
// If the slopes are equal, they only intersect if the lines are equal
if(m1==m2)
{
   if(b1==b2) return L1;
   else return false;
}
else
// otherwise the lines intersect at a point 
{
   double xI = (b1-b2)/(m2-m1);
   double yI = m1*xI+b1; // or m2*xI+b2 … same thing.
   return return new Point(xI,yI);
}

Modifying for segments

Modifying for line segments is a straightforward extension: first, we check for the collision coordinates as above, then see whether or not the the point is on one of these lines. This amounts to asking if the x-point of collision xI is within the region of x points of either line segment:

// Modify for segments
if(lineCollision) // as before
{
   if ((xI >= lx1 && xI <= rx1) && (xI >= lx2 && xI <= rx2))
   {
      collision == true;
   }
}

Crossing the t's and dotting the ... lower case j's

If we're dealing with floating point numbers, I find it best not to use strict equality because successive mathematical operations can lead to slight round-off error and you wind up with things like (49.99999999999999999999 == 50) = false, which in our program, should be true. This can be easily accounted for by checking if values are within some small threshold delta. To do this replace:

if(L1.x1 == L1.x2) 

… with:

if(Math.abs(L1.x1 - L1.x2)<delta) 

The code above will fail either of the line segments are vertical. This is easy to fix, but takes a few extra lines of code before the previous case:

// First check for vertical lines
if(L1.isVert()&&L2.isVert())
{
   if(Math.abs(L1.x-L2.x)<delta) // they're the same line
   {
      if(L1.y2 > L1.y2 && L1.y1 < L2.y2) // they intersect
      {
         collision = true;
         // xI,yI are on L1,L2
      }
   }
}

else if (L1.isVert())
{
   xI = L1.x1;
   yI = m2*xI + b2;
}
else if (L2.isVert())
{
   xI = L2.x1;
   yI = m1*xI + b2;
}

where,

public boolean isVert(Line L1)
{
   return(L1.x1-L2.x2 < delta)
}

Finally, int the case of collinear segments, the intersection occurs not at a point, but over a smaller line segment itself. For my purposes I only care that the segments overlap at least at a point, but we can easily extend the code to give the segment of overlap:

public boolean isVert(Line L1)
{ // This assumes that x1<x2, y1<y2. 
// If not, define x1s = Math.min(x1,x2);x2s = Math.max(x1,x2); etc…
// if colliding and collinear as before
double xL = Math.max(L1.x1,L2.x1);
double xR = Math.min(L1.x2,L2.x2);
double yL = m1*XL+b1;
double yR = m1*XR+b1;
return new LineSegment(xL,yL,xR,yR);
} // and similarly for horizontal and vertical lines

The Code in Action

I wrote a quick demo program for this code which can be found here. An executable jar file for the code is here if you want to play around with it. A video of the demo program is displayed below.