## Wednesday, June 9, 2010

### 2D Line segment intersection detection in C# / XNA

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