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

10 comments:

文剛文剛 said...

成熟,就是有能力適應生活中的模糊。....................................................................

張瑋劭 said...

nice to know you, and glad to find such a good artical!......................................................................

江婷 said...

知識可以傳授,智慧卻不行。每個人必須成為他自己。......................................................................

juliancu said...

成熟,就是有能力適應生活中的模糊。.................................................................

戴昀德 said...

安一估~你也安一估哦~............................................................

Stefan said...

what if the lines are parallel?

婉婷 said...

認清問題就等於已經解決了一半的問題。.................................................................

陳韋夏陳韋夏益東富益東富 said...

一個人的快樂,不是因為他擁有的多,而是他計較的少。..................................................

雅莊王edgd春2蕙婷余惠其 said...

認同您堅持和認真的態度,加油!支持你............................................................

Vargo said...

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