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
- }
10 comments:
成熟,就是有能力適應生活中的模糊。....................................................................
nice to know you, and glad to find such a good artical!......................................................................
知識可以傳授,智慧卻不行。每個人必須成為他自己。......................................................................
成熟,就是有能力適應生活中的模糊。.................................................................
安一估~你也安一估哦~............................................................
what if the lines are parallel?
認清問題就等於已經解決了一半的問題。.................................................................
一個人的快樂,不是因為他擁有的多,而是他計較的少。..................................................
認同您堅持和認真的態度,加油!支持你............................................................
@Stefan: it will return false if the lines are parallel.
Post a Comment