Line Intersection

I am having troubles with my line segment intersection algorithm.

Someone can share some knowledge on a good algorithm that helps you know if two segments intersect? I really need it for custom collision detection.

Thanks
Simone

 

In 2D, you can use simultaneous equations to find the point where two lines cross, if there is one. Once you have found the point, you can just check its coordinates against the start and end points of your two line segments to see if the crossing point is within the length of the segments.

In 3D, it is rare for two lines to cross exactly. However, you can make the 2D method work for 3D by simply leaving out one of the coordinates (ie, check if the lines in XY cross, then the lines in XZ and finally YZ). Once you have established that the lines cross somewhere, you can just measure the distance between the crossing points or use the skew line formula to see if the lines are close together.

 

Hi Andeeee,
I need to find the intersection point (if any) of two line segments not simple lines.

Anyway thanks for the links, they didnt solve my problem but the skew line thing is interesting

 

Sorry if I didn't explain that very clearly. What I meant was that you could use simultaneous equations to find the point where the two lines cross. Once you have that point, it is quite easy to check if it lies within the short segments of the lines that you are interested in. You basically just check each of the coordinates separately - if the crossing point is in the segment, its X coord will lie between the X coords of the two end points of the segment (and the same goes for the Y and Z coords). Do the check for both line segments and you will know if they intersect.

 

My fault! it was obvious... thank you very much for clearing my mind yes it is a viable solution.
I was looking for an algorithm that involves 2 vectors, but this solution is correct.

Thanks a lot

 

Well, you can use two vectors, but it is still a simultaneous equation...

You can represent your line segments using a start point and a vector offset to the end point. Then, any point along the line can be represented by

pt.x = start.x + t * offset.x
pt.y = start.y + t * offset.y

If your two lines are called A and B, the points are equal at the crossover, so you have:-

startA.x + t * offsetA.x = startB.x + u * offsetB.x
startA.y + t * offsetA.y = startB.y + u * offsetB.y

You basically just use the simultaneous equation method to eliminate one of the unknowns, t or u and rearrange the resulting equation to get a result in terms of the remaining unknown. The crossing point will be within both segments if both t and u are in the range 0..1

 

I too need a 2D line segment intersection algorithm and I found this post:
http://antihax.net/2D_Line_Intersection

It is based on the "Faster Line Segment Intersection" by Franklin Antonio (1992).
http://books.google.com/books?id=xm...Faster Line Segment Intersection&pg=RA1-PA199

It works great for pixels, but the intersection point goes way off when line component values are smaller than 1.0. I want to check intersections in UV co-ordinates so I am really stuck.

Can anyone help me spot the problem? Why is the precision terrible in 0.0–1.0 space?

~ce

Code (csharp):

1. public static bool LineIntersection( Vector2 p1,Vector2 p2, Vector2 p3, Vector2 p4, ref Vector2 intersection )
2. {
3.     float Ax,Bx,Cx,Ay,By,Cy,d,e,f,num,offset;
4.     float x1lo,x1hi,y1lo,y1hi;
5.    
6.     Ax = p2.x-p1.x;
7.     Bx = p3.x-p4.x;
8.    
9.     // X bound box test/
10.     if(Ax<0) {
11.         x1lo=p2.x; x1hi=p1.x;
12.     } else {
13.         x1hi=p2.x; x1lo=p1.x;
14.     }
15.    
16.     if(Bx>0) {
17.         if(x1hi < p4.x || p3.x < x1lo) return false;
18.     } else {
19.         if(x1hi < p3.x || p4.x < x1lo) return false;
20.     }
21.    
22.     Ay = p2.y-p1.y;
23.     By = p3.y-p4.y;
24.    
25.     // Y bound box test//
26.     if(Ay<0) {                 
27.         y1lo=p2.y; y1hi=p1.y;
28.     } else {
29.         y1hi=p2.y; y1lo=p1.y;
30.     }
31.    
32.     if(By>0) {
33.         if(y1hi < p4.y || p3.y < y1lo) return false;
34.     } else {
35.         if(y1hi < p3.y || p4.y < y1lo) return false;
36.     }
37.    
38.     Cx = p1.x-p3.x;
39.     Cy = p1.y-p3.y;
40.     d = By*Cx - Bx*Cy;  // alpha numerator//
41.     f = Ay*Bx - Ax*By;  // both denominator//
42.    
43.     // alpha tests//
44.     if(f>0) {
45.         if(d<0 || d>f) return false;
46.     } else {
47.         if(d>0 || d<f) return false;
48.     }
49.    
50.     e = Ax*Cy - Ay*Cx;  // beta numerator//
51.    
52.     // beta tests //
53.     if(f>0) {                          
54.       if(e<0 || e>f) return false;
55.       } else {
56.       if(e>0 || e<f) return false;
57.       }
58.    
59.     // check if they are parallel
60.     if(f==0) return false;
61.    
62.     // compute intersection coordinates //
63.     num = d*Ax; // numerator //
64.     offset = same_sign(num,f) ? f*0.5f : -f*0.5f;   // round direction //
65.     intersection.x = p1.x + (num+offset) / f;
66.    
67.     num = d*Ay;
68.     offset = same_sign(num,f) ? f*0.5f : -f*0.5f;
69.     intersection.y = p1.y + (num+offset) / f;
70.    
71.     return true;
72. }
73.  
74. private static bool same_sign( float a, float b ){
75.     return ( ( a * b ) >= 0f );
76. }
77.  

 

Hey Carl.
Sorry about the revival, but I was looking for a line intersection algorithm and found yours.
I removed the offset and started working for me.
Code would be something like this.
Hope it helps.

Code (csharp):

1. public static bool LineIntersection( Vector2 p1,Vector2 p2, Vector2 p3, Vector2 p4, ref Vector2 intersection )
2. {
3.  
4.     float Ax,Bx,Cx,Ay,By,Cy,d,e,f,num/*,offset*/;
5.  
6.     float x1lo,x1hi,y1lo,y1hi;
7.  
8.    
9.  
10.     Ax = p2.x-p1.x;
11.  
12.     Bx = p3.x-p4.x;
13.  
14.    
15.  
16.     // X bound box test/
17.  
18.     if(Ax<0) {
19.  
20.         x1lo=p2.x; x1hi=p1.x;
21.  
22.     } else {
23.  
24.         x1hi=p2.x; x1lo=p1.x;
25.  
26.     }
27.  
28.    
29.  
30.     if(Bx>0) {
31.  
32.         if(x1hi < p4.x || p3.x < x1lo) return false;
33.  
34.     } else {
35.  
36.         if(x1hi < p3.x || p4.x < x1lo) return false;
37.  
38.     }
39.  
40.    
41.  
42.     Ay = p2.y-p1.y;
43.  
44.     By = p3.y-p4.y;
45.  
46.    
47.  
48.     // Y bound box test//
49.  
50.     if(Ay<0) {                  
51.  
52.         y1lo=p2.y; y1hi=p1.y;
53.  
54.     } else {
55.  
56.         y1hi=p2.y; y1lo=p1.y;
57.  
58.     }
59.  
60.    
61.  
62.     if(By>0) {
63.  
64.         if(y1hi < p4.y || p3.y < y1lo) return false;
65.  
66.     } else {
67.  
68.         if(y1hi < p3.y || p4.y < y1lo) return false;
69.  
70.     }
71.  
72.    
73.  
74.     Cx = p1.x-p3.x;
75.  
76.     Cy = p1.y-p3.y;
77.  
78.     d = By*Cx - Bx*Cy;  // alpha numerator//
79.  
80.     f = Ay*Bx - Ax*By;  // both denominator//
81.  
82.    
83.  
84.     // alpha tests//
85.  
86.     if(f>0) {
87.  
88.         if(d<0 || d>f) return false;
89.  
90.     } else {
91.  
92.         if(d>0 || d<f) return false;
93.  
94.     }
95.  
96.    
97.  
98.     e = Ax*Cy - Ay*Cx;  // beta numerator//
99.  
100.    
101.  
102.     // beta tests //
103.  
104.     if(f>0) {                          
105.  
106.       if(e<0 || e>f) return false;
107.  
108.       } else {
109.  
110.       if(e>0 || e<f) return false;
111.  
112.       }
113.  
114.    
115.  
116.     // check if they are parallel
117.  
118.     if(f==0) return false;
119.        
120.     // compute intersection coordinates //
121.  
122.     num = d*Ax; // numerator //
123.  
124. //    offset = same_sign(num,f) ? f*0.5f : -f*0.5f;   // round direction //
125.  
126. //    intersection.x = p1.x + (num+offset) / f;
127.   intersection.x = p1.x + num / f;
128.  
129.    
130.  
131.     num = d*Ay;
132.  
133. //    offset = same_sign(num,f) ? f*0.5f : -f*0.5f;
134.  
135. //    intersection.y = p1.y + (num+offset) / f;
136. intersection.y = p1.y + num / f;
137.  
138.    
139.  
140.     return true;
141.  
142. }

 

The following code is almost a duplicate from the code above, but slightly thinner because I was not interested in the intersection point itself. The implementation is (as above) based on Faster Line Segment Intersection by Franklin Antonio, Graphics Gems III, 1992, pp. 199-202, see also http://www.stefanbader.ch/?p=49.

Code (csharp):

1.  
2. static bool FasterLineSegmentIntersection(Vector2 p1, Vector2 p2, Vector2 p3, Vector2 p4) {
3.    
4.     Vector2 a = p2 - p1;
5.     Vector2 b = p3 - p4;
6.     Vector2 c = p1 - p3;
7.    
8.     float alphaNumerator = b.y*c.x - b.x*c.y;
9.     float alphaDenominator = a.y*b.x - a.x*b.y;
10.     float betaNumerator  = a.x*c.y - a.y*c.x;
11.     float betaDenominator  = a.y*b.x - a.x*b.y;
12.    
13.     bool doIntersect = true;
14.    
15.     if (alphaDenominator == 0 || betaDenominator == 0) {
16.         doIntersect = false;
17.     } else {
18.        
19.         if (alphaDenominator > 0) {
20.             if (alphaNumerator < 0 || alphaNumerator > alphaDenominator) {
21.                 doIntersect = false;
22.                
23.             }
24.         } else if (alphaNumerator > 0 || alphaNumerator < alphaDenominator) {
25.             doIntersect = false;
26.         }
27.        
28.         if (doIntersect  betaDenominator > 0) {
29.             if (betaNumerator < 0 || betaNumerator > betaDenominator) {
30.                 doIntersect = false;
31.             }
32.         } else if (betaNumerator > 0 || betaNumerator < betaDenominator) {
33.             doIntersect = false;
34.         }
35.     }
36.  
37.     return doIntersect;
38. }
39.  

 

Thanks a lot guys. This works perfect as per my consideration.

 

Hey Guys,

I have a similar issue but Its slightly different. Could anybody tell me how to check if a Vector3 point has crossed a line.

I'm can't use the colliders for this. Is there a way to change the above algorithm to achieve this ?

 

There's a problem above in Line 28 - what's the correct line?

 

Ln 28 should be:

Code (CSharp):

1. if (doIntersect && betaDenominator > 0) {

Cheers,
Ben

 

there is also a whole mass of stuff regarding intersecting points/lines/plane/whatever on

http://wiki.unity3d.com/index.php/3d_Math_functions

 

But not line segments.

 

Hi guys,
I have changed the code above(Minassian version) to meet my requirements. I add some float precision control with the parameter fSelfDefinedEpsilon. Hope this is helpful for you.

Code (CSharp):

1.    /// <summary>
2.     /// Calculate the intersection point of two line segments
3.     /// </summary>
4.     /// <param name="p1"></param>
5.     /// <param name="p2"></param>
6.     /// <param name="p3"></param>
7.     /// <param name="p4"></param>
8.     /// <param name="intersection"></param>
9.     /// <param name="fSelfDefinedEpsilon">Epsilon in pixels</param>
10.     /// <returns></returns>
11.     public static bool LineSegmentsIntersectionWithPrecisonControl (Vector2 p1, Vector2 p2, Vector2 p3, Vector2 p4, ref Vector2 intersection, float fSelfDefinedEpsilon = 1.0f) {
12.         //Debug.Log (string.Format("LineSegmentsIntersection2 p1 {0} p2 {1} p3 {2} p4{3}", p1, p2, p3, p4)); // the float value precision in the log is just 0.0f
13.         UnityEngine.Assertions.Assert.IsTrue (fSelfDefinedEpsilon > 0);
14.  
15.         float Ax, Bx, Cx, Ay, By, Cy, d, e, f, num/*,offset*/;
16.         float x1lo, x1hi, y1lo, y1hi;
17.         Ax = p2.x - p1.x;
18.         Bx = p3.x - p4.x;
19.  
20.         // X bound box test/
21.         if (Ax < 0) {
22.             x1lo = p2.x; x1hi = p1.x;
23.         }
24.         else {
25.             x1hi = p2.x; x1lo = p1.x;
26.         }
27.  
28.         if (Bx > 0) {
29.             if ((x1hi < p4.x && Mathf.Abs(x1hi - p4.x) > fSelfDefinedEpsilon)
30.                 || (p3.x < x1lo && Mathf.Abs(p3.x - x1lo) > fSelfDefinedEpsilon))
31.                 return false;
32.         }
33.         else {
34.             if ((x1hi < p3.x && Mathf.Abs(x1hi - p3.x) > fSelfDefinedEpsilon)
35.                 || (p4.x < x1lo && Mathf.Abs(p4.x - x1lo) > fSelfDefinedEpsilon))
36.                 return false;
37.         }
38.  
39.         Ay = p2.y - p1.y;
40.         By = p3.y - p4.y;
41.  
42.         // Y bound box test//
43.         if (Ay < 0) {
44.             y1lo = p2.y; y1hi = p1.y;
45.         }
46.         else {
47.             y1hi = p2.y; y1lo = p1.y;
48.         }
49.  
50.         if (By > 0) {
51.             if ((y1hi < p4.y && Mathf.Abs(y1hi - p4.y) > fSelfDefinedEpsilon)
52.                 || (p3.y < y1lo && Mathf.Abs(p3.y - y1lo) > fSelfDefinedEpsilon))
53.                 return false;
54.         }
55.         else {
56.             if ((y1hi < p3.y && Mathf.Abs(y1hi - p3.y) > fSelfDefinedEpsilon)
57.                 || (p4.y < y1lo && Mathf.Abs(p4.y - y1lo) > fSelfDefinedEpsilon))
58.                 return false;
59.         }
60.  
61.         Cx = p1.x - p3.x;
62.         Cy = p1.y - p3.y;
63.         d = By * Cx - Bx * Cy;  // alpha numerator//
64.         f = Ay * Bx - Ax * By;  // both denominator//
65.        
66.         // alpha tests//
67.  
68.         if (f > 0) {
69.             if ((d < 0 && Mathf.Abs(d) > fSelfDefinedEpsilon)
70.                 || (d > f && Mathf.Abs(d - f) > fSelfDefinedEpsilon))
71.                 return false;
72.         }
73.         else {
74.             if ((d > 0 && Mathf.Abs(d) > fSelfDefinedEpsilon)
75.                 || (d < f && Mathf.Abs(d - f) > fSelfDefinedEpsilon))
76.                 return false;
77.         }
78.         e = Ax * Cy - Ay * Cx;  // beta numerator//
79.  
80.         // beta tests //
81.  
82.         if (f > 0) {
83.             if ((e < 0 && Mathf.Abs(e) > fSelfDefinedEpsilon)
84.                 || (e > f) && Mathf.Abs(e - f) > fSelfDefinedEpsilon)
85.                 return false;
86.         }
87.         else {
88.             if ((e > 0 && Mathf.Abs(e) > fSelfDefinedEpsilon)
89.                 || (e < f && Mathf.Abs(e - f) > fSelfDefinedEpsilon))
90.                 return false;
91.         }
92.  
93.         // check if they are parallel
94.         if (f == 0 && Mathf.Abs(f) > fSelfDefinedEpsilon)
95.             return false;
96.  
97.         // compute intersection coordinates //
98.         num = d * Ax; // numerator //
99.  
100.         //    offset = same_sign(num,f) ? f*0.5f : -f*0.5f;   // round direction //
101.  
102.         //    intersection.x = p1.x + (num+offset) / f;
103.         intersection.x = p1.x + num / f;
104.         num = d * Ay;
105.  
106.         //    offset = same_sign(num,f) ? f*0.5f : -f*0.5f;
107.  
108.         //    intersection.y = p1.y + (num+offset) / f;
109.         intersection.y = p1.y + num / f;
110.         return true;
111.     }

 

I turned out to use this one instead. https://www.habrador.com/tutorials/math/5-line-line-intersection/

You can control the margin of error by modifying the IsBetween function very easily.

 

And leaner still (and could be faster but messier by saving C and numerator calculations until needed)...

Code (CSharp):

1. bool FasterLineSegmentIntersection (Vector2 line1point1, Vector2 line1point2, Vector2 line2point1, Vector2 line2point2) {
2.  
3.     Vector2 a = line1point2 - line1point1;
4.     Vector2 b = line2point1 - line2point2;
5.     Vector2 c = line1point1 - line2point1;
6.  
7.     float alphaNumerator = b.y * c.x - b.x * c.y;
8.     float betaNumerator  = a.x * c.y - a.y * c.x;
9.     float denominator    = a.y * b.x - a.x * b.y;
10.  
11.     if (denominator == 0) {
12.         return false;
13.     } else if (denominator > 0) {
14.         if (alphaNumerator < 0 || alphaNumerator > denominator || betaNumerator < 0 || betaNumerator > denominator) {
15.             return false;
16.         }
17.     } else if (alphaNumerator > 0 || alphaNumerator < denominator || betaNumerator > 0 || betaNumerator < denominator) {
18.         return false;
19.     }
20.     return true;
21. }
22.  

 

@CgPanda just noticed a bug in your code

Code (CSharp):

1. // check if they are parallel
2. if (f == 0 && Mathf.Abs(f) > fSelfDefinedEpsilon)
3.     return false;

f needs to be 0 -> abs(f) needs to be 0,
fSelfDefinedEpsilon should be greater 0,
Mathf.Abs(f) > fSelfDefinedEpsilon is always false

I think what you meant to do is

Code (CSharp):

1. // check if they are parallel
2. if (Mathf.Abs(f) < fSelfDefinedEpsilon)
3.    return false;

 

Sorry for revival, how to return the exact point of intersection?

 

Perhaps too late to the party:

Code (CSharp):

1.     /// <summary>
2.     /// Calculates the intersection of two given lines
3.     /// </summary>
4.     /// <param name="intersection">returned intersection</param>
5.     /// <param name="linePoint1">start location of the line 1</param>
6.     /// <param name="lineDirection1">direction of line 1</param>
7.     /// <param name="linePoint2">start location of the line 2</param>
8.     /// <param name="lineDirection2">direction of line2</param>
9.     /// <returns>true: lines intersect, false: lines do not intersect</returns>
10.     public static bool LineLineIntersection(out Vector3 intersection,
11.         Vector3 linePoint1, Vector3 lineDirection1,
12.         Vector3 linePoint2, Vector3 lineDirection2)
13.     {
14.  
15.         Vector3 lineVec3 = linePoint2 - linePoint1;
16.         Vector3 crossVec1and2 = Vector3.Cross(lineDirection1, lineDirection2);
17.         Vector3 crossVec3and2 = Vector3.Cross(lineVec3, lineDirection2);
18.         float planarFactor = Vector3.Dot(lineVec3, crossVec1and2);
19.  
20.         //is coplanar, and not parallel
21.         if (Mathf.Abs(planarFactor) < 0.0001f
22.                 && crossVec1and2.sqrMagnitude > 0.0001f)
23.         {
24.             float s = Vector3.Dot(crossVec3and2, crossVec1and2) / crossVec1and2.sqrMagnitude;
25.             intersection = linePoint1 + (lineDirection1 * s);
26.             return true;
27.         }
28.         else
29.         {
30.             intersection = Vector3.zero;
31.             return false;
32.         }
33.     }

 

That blatantly doesn't work. I hate when people post random intersection algorithms they don't understand and/or didn't test!

 

Blatantly works perfectly for me!

 

From memory ... it was a copy/paste of a wrong implementation of someone else's algorithm. You can find other copies floating around the web - they don't work, since the original copy had a bug in it.

They will half work - some cases will seem to give the right answer.

But sooner or later they will fail and give the wrong result.

(I'm now sorry I didn't specify what exactly the bug is - I can't remember. But I dropped it into my unit tests and it immediately failed)

 

I managed to reproduce the solution from school textbook.
(Given 4 points, calculate the intersection point of line P1P2 and P3P4)

Code (CSharp):

1.  
2.     Vector2 GetIntersectionPoint(Vector2 p1, Vector2 p2, Vector2 p3, Vector2 p4)
3.     {
4.         float d1 = Vector3.Cross(p1 - p3, p4 - p3).z;
5.         float d2 = Vector3.Cross(p2 - p3, p4 - p3).z;
6.         if (d1 - d2 == 0) return Vector2.negativeInfinity; // P1P2 and P3P4 is parallel in this case
7.         return (d1 * p2 - d2 * p1) / (d1 - d2);
8.     }
9.  

 

Homogeneous coordinates line intersection in 2D.
Lowered to eliminate all calls; mathematically stable and robust solution.

Code (csharp):

1. bool lineLine(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 p) {
2.   const float EPSILON = 1E-6f;
3.   p = new Vector2(float.NaN, float.NaN);
4.  
5.   var cc = (a1.y - a2.y) * (b2.x - b1.x) - (a2.x - a1.x) * (b1.y - b2.y);
6.   if(System.Math.Abs(cc) < EPSILON) return false; // lines are parallel or congruent
7.  
8.   p = (1f / cc) * new Vector2(
9.     (a2.x - a1.x) * (b1.x * b2.y - b1.y * b2.x) - (a1.x * a2.y - a1.y * a2.x) * (b2.x - b1.x),
10.     (a1.x * a2.y - a1.y * a2.x) * (b1.y - b2.y) - (a1.y - a2.y) * (b1.x * b2.y - b1.y * b2.x)
11.   );
12.  
13.   return true;
14. }

Full explanation and more utilities can be found here.