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.
1 Like
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).
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
public static bool LineIntersection( Vector2 p1,Vector2 p2, Vector2 p3, Vector2 p4, ref Vector2 intersection )
{
float Ax,Bx,Cx,Ay,By,Cy,d,e,f,num,offset;
float x1lo,x1hi,y1lo,y1hi;
Ax = p2.x-p1.x;
Bx = p3.x-p4.x;
// X bound box test/
if(Ax<0) {
x1lo=p2.x; x1hi=p1.x;
} else {
x1hi=p2.x; x1lo=p1.x;
}
if(Bx>0) {
if(x1hi < p4.x || p3.x < x1lo) return false;
} else {
if(x1hi < p3.x || p4.x < x1lo) return false;
}
Ay = p2.y-p1.y;
By = p3.y-p4.y;
// Y bound box test//
if(Ay<0) {
y1lo=p2.y; y1hi=p1.y;
} else {
y1hi=p2.y; y1lo=p1.y;
}
if(By>0) {
if(y1hi < p4.y || p3.y < y1lo) return false;
} else {
if(y1hi < p3.y || p4.y < y1lo) return false;
}
Cx = p1.x-p3.x;
Cy = p1.y-p3.y;
d = By*Cx - Bx*Cy; // alpha numerator//
f = Ay*Bx - Ax*By; // both denominator//
// alpha tests//
if(f>0) {
if(d<0 || d>f) return false;
} else {
if(d>0 || d<f) return false;
}
e = Ax*Cy - Ay*Cx; // beta numerator//
// beta tests //
if(f>0) {
if(e<0 || e>f) return false;
} else {
if(e>0 || e<f) return false;
}
// check if they are parallel
if(f==0) return false;
// compute intersection coordinates //
num = d*Ax; // numerator //
offset = same_sign(num,f) ? f*0.5f : -f*0.5f; // round direction //
intersection.x = p1.x + (num+offset) / f;
num = d*Ay;
offset = same_sign(num,f) ? f*0.5f : -f*0.5f;
intersection.y = p1.y + (num+offset) / f;
return true;
}
private static bool same_sign( float a, float b ){
return ( ( a * b ) >= 0f );
}
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.
public static bool LineIntersection( Vector2 p1,Vector2 p2, Vector2 p3, Vector2 p4, ref Vector2 intersection )
{
float Ax,Bx,Cx,Ay,By,Cy,d,e,f,num/*,offset*/;
float x1lo,x1hi,y1lo,y1hi;
Ax = p2.x-p1.x;
Bx = p3.x-p4.x;
// X bound box test/
if(Ax<0) {
x1lo=p2.x; x1hi=p1.x;
} else {
x1hi=p2.x; x1lo=p1.x;
}
if(Bx>0) {
if(x1hi < p4.x || p3.x < x1lo) return false;
} else {
if(x1hi < p3.x || p4.x < x1lo) return false;
}
Ay = p2.y-p1.y;
By = p3.y-p4.y;
// Y bound box test//
if(Ay<0) {
y1lo=p2.y; y1hi=p1.y;
} else {
y1hi=p2.y; y1lo=p1.y;
}
if(By>0) {
if(y1hi < p4.y || p3.y < y1lo) return false;
} else {
if(y1hi < p3.y || p4.y < y1lo) return false;
}
Cx = p1.x-p3.x;
Cy = p1.y-p3.y;
d = By*Cx - Bx*Cy; // alpha numerator//
f = Ay*Bx - Ax*By; // both denominator//
// alpha tests//
if(f>0) {
if(d<0 || d>f) return false;
} else {
if(d>0 || d<f) return false;
}
e = Ax*Cy - Ay*Cx; // beta numerator//
// beta tests //
if(f>0) {
if(e<0 || e>f) return false;
} else {
if(e>0 || e<f) return false;
}
// check if they are parallel
if(f==0) return false;
// compute intersection coordinates //
num = d*Ax; // numerator //
// offset = same_sign(num,f) ? f*0.5f : -f*0.5f; // round direction //
// intersection.x = p1.x + (num+offset) / f;
intersection.x = p1.x + num / f;
num = d*Ay;
// offset = same_sign(num,f) ? f*0.5f : -f*0.5f;
// intersection.y = p1.y + (num+offset) / f;
intersection.y = p1.y + num / f;
return true;
}
2 Likes
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.
static bool FasterLineSegmentIntersection(Vector2 p1, Vector2 p2, Vector2 p3, Vector2 p4) {
Vector2 a = p2 - p1;
Vector2 b = p3 - p4;
Vector2 c = p1 - p3;
float alphaNumerator = b.y*c.x - b.x*c.y;
float alphaDenominator = a.y*b.x - a.x*b.y;
float betaNumerator = a.x*c.y - a.y*c.x;
float betaDenominator = a.y*b.x - a.x*b.y;
bool doIntersect = true;
if (alphaDenominator == 0 || betaDenominator == 0) {
doIntersect = false;
} else {
if (alphaDenominator > 0) {
if (alphaNumerator < 0 || alphaNumerator > alphaDenominator) {
doIntersect = false;
}
} else if (alphaNumerator > 0 || alphaNumerator < alphaDenominator) {
doIntersect = false;
}
if (doIntersect betaDenominator > 0) {
if (betaNumerator < 0 || betaNumerator > betaDenominator) {
doIntersect = false;
}
} else if (betaNumerator > 0 || betaNumerator < betaDenominator) {
doIntersect = false;
}
}
return doIntersect;
}
5 Likes
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:
if (doIntersect && betaDenominator > 0) {
Cheers,
Ben
2 Likes
there is also a whole mass of stuff regarding intersecting points/lines/plane/whatever on
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.
```csharp
-
///
/// Calculate the intersection point of two line segments
///
///
///
///
///
///
/// Epsilon in pixels
///
public static bool LineSegmentsIntersectionWithPrecisonControl (Vector2 p1, Vector2 p2, Vector2 p3, Vector2 p4, ref Vector2 intersection, float fSelfDefinedEpsilon = 1.0f) {
//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
UnityEngine.Assertions.Assert.IsTrue (fSelfDefinedEpsilon > 0);float Ax, Bx, Cx, Ay, By, Cy, d, e, f, num/*,offset*/; float x1lo, x1hi, y1lo, y1hi; Ax = p2.x - p1.x; Bx = p3.x - p4.x; // X bound box test/ if (Ax < 0) { x1lo = p2.x; x1hi = p1.x; } else { x1hi = p2.x; x1lo = p1.x; } if (Bx > 0) { if ((x1hi < p4.x && Mathf.Abs(x1hi - p4.x) > fSelfDefinedEpsilon) || (p3.x < x1lo && Mathf.Abs(p3.x - x1lo) > fSelfDefinedEpsilon)) return false; } else { if ((x1hi < p3.x && Mathf.Abs(x1hi - p3.x) > fSelfDefinedEpsilon) || (p4.x < x1lo && Mathf.Abs(p4.x - x1lo) > fSelfDefinedEpsilon)) return false; } Ay = p2.y - p1.y; By = p3.y - p4.y; // Y bound box test// if (Ay < 0) { y1lo = p2.y; y1hi = p1.y; } else { y1hi = p2.y; y1lo = p1.y; } if (By > 0) { if ((y1hi < p4.y && Mathf.Abs(y1hi - p4.y) > fSelfDefinedEpsilon) || (p3.y < y1lo && Mathf.Abs(p3.y - y1lo) > fSelfDefinedEpsilon)) return false; } else { if ((y1hi < p3.y && Mathf.Abs(y1hi - p3.y) > fSelfDefinedEpsilon) || (p4.y < y1lo && Mathf.Abs(p4.y - y1lo) > fSelfDefinedEpsilon)) return false; } Cx = p1.x - p3.x; Cy = p1.y - p3.y; d = By * Cx - Bx * Cy; // alpha numerator// f = Ay * Bx - Ax * By; // both denominator// // alpha tests// if (f > 0) { if ((d < 0 && Mathf.Abs(d) > fSelfDefinedEpsilon) || (d > f && Mathf.Abs(d - f) > fSelfDefinedEpsilon)) return false; } else { if ((d > 0 && Mathf.Abs(d) > fSelfDefinedEpsilon) || (d < f && Mathf.Abs(d - f) > fSelfDefinedEpsilon)) return false; } e = Ax * Cy - Ay * Cx; // beta numerator// // beta tests // if (f > 0) { if ((e < 0 && Mathf.Abs(e) > fSelfDefinedEpsilon) || (e > f) && Mathf.Abs(e - f) > fSelfDefinedEpsilon) return false; } else { if ((e > 0 && Mathf.Abs(e) > fSelfDefinedEpsilon) || (e < f && Mathf.Abs(e - f) > fSelfDefinedEpsilon)) return false; } // check if they are parallel if (f == 0 && Mathf.Abs(f) > fSelfDefinedEpsilon) return false; // compute intersection coordinates // num = d * Ax; // numerator // // offset = same_sign(num,f) ? f*0.5f : -f*0.5f; // round direction // // intersection.x = p1.x + (num+offset) / f; intersection.x = p1.x + num / f; num = d * Ay; // offset = same_sign(num,f) ? f*0.5f : -f*0.5f; // intersection.y = p1.y + (num+offset) / f; intersection.y = p1.y + num / f; return true;}*
```
1 Like
I turned out to use this one instead. Use math to solve problems in Unity with C# - Line segment intersection | Habrador
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)…
bool FasterLineSegmentIntersection (Vector2 line1point1, Vector2 line1point2, Vector2 line2point1, Vector2 line2point2) {
Vector2 a = line1point2 - line1point1;
Vector2 b = line2point1 - line2point2;
Vector2 c = line1point1 - line2point1;
float alphaNumerator = b.y * c.x - b.x * c.y;
float betaNumerator = a.x * c.y - a.y * c.x;
float denominator = a.y * b.x - a.x * b.y;
if (denominator == 0) {
return false;
} else if (denominator > 0) {
if (alphaNumerator < 0 || alphaNumerator > denominator || betaNumerator < 0 || betaNumerator > denominator) {
return false;
}
} else if (alphaNumerator > 0 || alphaNumerator < denominator || betaNumerator > 0 || betaNumerator < denominator) {
return false;
}
return true;
}
2 Likes
@CgPanda just noticed a bug in your code
// check if they are parallel
if (f == 0 && Mathf.Abs(f) > fSelfDefinedEpsilon)
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
// check if they are parallel
if (Mathf.Abs(f) < fSelfDefinedEpsilon)
return false;
Sorry for revival, how to return the exact point of intersection?