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.         }

4 comments:

Stefan said...

what if the lines are parallel?

Vargo said...

@Stefan: it will return false if the lines are parallel.

gilschneider said...

What is the mathematical formula in which this algorithm is based?

gilschneider said...
This comment has been removed by the author.