Detecting Line-to-Line Intersection

These two methods are really useful for detecting line intersection in 2D.

• x1,y1,x2,y2 : The two points of the first line

• x3,y3,x4,y4 : The two points of the second line

 
/**
 
detecting-line-to-line-intersection taken from http://processinghacks.com/hacks:detecting-line-to-line-intersection
 
@author Ryan Alexander
 
*/
 
 
 
// Infinite Line Intersection
 
PVector lineIntersection(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4)
 
{
 
  float bx = x2 - x1;
 
  float by = y2 - y1;
 
  float dx = x4 - x3;
 
  float dy = y4 - y3;
 
 
 
  float b_dot_d_perp = bx*dy - by*dx;
 
 
 
  if(b_dot_d_perp == 0) return null;
 
 
 
  float cx = x3-x1;
 
  float cy = y3-y1;
 
 
 
  float t = (cx*dy - cy*dx) / b_dot_d_perp;
 
 
 
  return new PVector(x1+t*bx, y1+t*by);
 
}
 
 
 
// Line Segment Intersection
 
PVector segIntersection(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4)
 
{
 
  float bx = x2 - x1;
 
  float by = y2 - y1;
 
  float dx = x4 - x3;
 
  float dy = y4 - y3;
 
 
 
  float b_dot_d_perp = bx * dy - by * dx;
 
 
 
  if(b_dot_d_perp == 0) return null;
 
 
 
  float cx = x3 - x1;
 
  float cy = y3 - y1;
 
 
 
  float t = (cx * dy - cy * dx) / b_dot_d_perp;
 
  if(t < 0 || t > 1) return null;
 
 
 
  float u = (cx * by - cy * bx) / b_dot_d_perp;
 
  if(u < 0 || u > 1) return null;
 
 
 
  return new PVector(x1+t*bx, y1+t*by);
 
}

• Paul Bourke's tutorial / solution

• more related geometry links