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#

- // Returns true if the lines intersect, otherwise false. If the lines
- // intersect, intersectionPoint holds the intersection point.
- public bool Intersects2D(LineSegment3 otherLineSegment, out Vector3 intersectionPoint)
- {
- float firstLineSlopeX, firstLineSlopeY, secondLineSlopeX, secondLineSlopeY;
- firstLineSlopeX = this.Point2.X - this.Point1.X;
- firstLineSlopeY = this.Point2.Y - this.Point1.Y;
- secondLineSlopeX = otherLineSegment.Point2.X - otherLineSegment.Point1.X;
- secondLineSlopeY = otherLineSegment.Point2.Y - otherLineSegment.Point1.Y;
- float s, t;
- s = (-firstLineSlopeY * (this.Point1.X - otherLineSegment.Point1.X) + firstLineSlopeX * (this.Point1.Y - otherLineSegment.Point1.Y)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
- t = (secondLineSlopeX * (this.Point1.Y - otherLineSegment.Point1.Y) - secondLineSlopeY * (this.Point1.X - otherLineSegment.Point1.X)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
- if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
- {
- float intersectionPointX = this.Point1.X + (t * firstLineSlopeX);
- float intersectionPointY = this.Point1.Y + (t * firstLineSlopeY);
- // Collision detected
- intersectionPoint = new Vector3(intersectionPointX, intersectionPointY, 0);
- return true;
- }
- intersectionPoint = Vector3.Zero;
- return false; // No collision
- }

## 4 comments:

what if the lines are parallel?

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

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

Post a Comment