Wednesday, June 9, 2010

2D Line segment intersection detection in C#

For a previous game project, I needed a nice line segment intersection detection algorithm.  It was surprisingly difficult to find a good one in C#, but I found one in C++ that I converted. 

As it turns out, my upcoming game makes heavy use of this algorithm as well.  So here it is in case anyone else needs it.  This version is a little sloppy in that it uses 3D constructs despite checking 2D intersections, but it would be simple to convert this to its 2D counterpart.

Line segment intersection C#
  1. // Returns true if the lines intersect, otherwise false. If the lines
  2.         // intersect, intersectionPoint holds the intersection point.
  3.         public bool Intersects2D(LineSegment3 otherLineSegment, out Vector3 intersectionPoint)
  4.         {
  5.             float firstLineSlopeX, firstLineSlopeY, secondLineSlopeX, secondLineSlopeY;
  6.  
  7.             firstLineSlopeX = this.Point2.X - this.Point1.X;
  8.             firstLineSlopeY = this.Point2.Y - this.Point1.Y;
  9.  
  10.             secondLineSlopeX = otherLineSegment.Point2.X - otherLineSegment.Point1.X;
  11.             secondLineSlopeY = otherLineSegment.Point2.Y - otherLineSegment.Point1.Y;
  12.  
  13.             float s, t;
  14.             s = (-firstLineSlopeY * (this.Point1.X - otherLineSegment.Point1.X) + firstLineSlopeX * (this.Point1.Y - otherLineSegment.Point1.Y)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
  15.             t = (secondLineSlopeX * (this.Point1.Y - otherLineSegment.Point1.Y) - secondLineSlopeY * (this.Point1.X - otherLineSegment.Point1.X)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
  16.  
  17.             if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
  18.             {
  19.                 float intersectionPointX = this.Point1.X + (t * firstLineSlopeX);
  20.                 float intersectionPointY = this.Point1.Y + (t * firstLineSlopeY);
  21.  
  22.                 // Collision detected
  23.                 intersectionPoint = new Vector3(intersectionPointX, intersectionPointY, 0);
  24.  
  25.                 return true;
  26.             }
  27.  
  28.             intersectionPoint = Vector3.Zero;
  29.             return false; // No collision
  30.         }