# Line Collision

This topic is 4962 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello, I am writing a function that returns true if two lines are intersecting, the problem i have is that I don't know how to do it. I suck at math, and all the code I have found tells me where the intersection happens, I dont know what to look for. I just want to know if the two lines I give the function are intersecting. And these are lines I draw on the screen so they do have end points.

In 2D or 3D?

ace

2d

##### Share on other sites
I found this code in one of my old projects. It came from http://astronomy.swin.edu.au/~pbourke/geometry/lineline2d/

bool mat_DoSegmentsIntersect (mat_segment s1, mat_segment s2){   // http://astronomy.swin.edu.au/~pbourke/geometry/lineline2d/   // Given line (p1, p2) and line (p3, p4)   // They can be expressed parameticly as:   //    i = p1 + a (p2 - p1)   //    i = p3 + b (p4 - p3)   // where i is the intersection point and a and b are between 0 and 1   // Bringing the equations together...   //    p1 + a (p2 - p1) = p3 + b (p4 - p3)   // This forms two equations:   //    a = [(x4 - x3)(y1 - y3) - (y4 - y3)(x1 - x3)] /   //        [(y4 - y3)(x2 - x1) - (x4 - x3)(y2 - y1)]   //    b = [(x2 - x1)(y1 - y3) - (y2 - y1)(x1 - x3)] /   //        [(y4 - y3)(x2 - x1) - (x4 - x3)(y2 - y1)]   // As long as these are between 0 and 1, we have an intersection.   // Oh, and check the denomator isn't zero or else the lines are   // parallel. But if the numerator is zero also, they coincide.   // These are the points   float x1 = s1.p1.x, y1 = s1.p1.y;   float x2 = s1.p2.x, y2 = s1.p2.y;   float x3 = s2.p1.x, y3 = s2.p1.y;   float x4 = s2.p2.x, y4 = s2.p2.y;   // Calculate our interpolation values   float denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);   float numer_a = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3);   float numer_b = (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3);   if (denom == 0) // Parallel?      return false;   float a = numer_a / denom;   float b = numer_b / denom;   // Make sure they are between zero and one   if (a >= 0 && a <= 1 && b >= 0 && b <= 1)      return true;   else return false;}

thanks

##### Share on other sites
In 2D, any two lines with unequal slopes will intersect at one point. Any two lines with equal slopes will either be coincident (have the same cartesian equation in the form y = mx + b for slope m and y-intercept b), or have the same slope and a different y-intercept, resulting in no intersection.

If you have y1 = m1 X x1 + b1, y2 = m2 X x2 + b2:

Let y1 = y2
so m1 X x1 + b1 = m2 X x2 + b2

but x1 = x2 at intersection point:

m1 X x + b1 = m2 X x + b2

so: m1 X x - m2 X x = b2 - b1
x X (m1 - m2) = b2 - b1
x = (b2 - b1) / (m1 - m2), if m1 != m2

Then, sub x into either equation to find the common y-value at the intersection point.

If m1 = m2, it's a trivial case, and can be solved by simply checking y when x = 0: if y1 = y2 when x = 0, the lines are coincident and intersect at every point on each line, otherwise there is no intersection.

However, if you're working with line segments, the math is not as simple.

##### Share on other sites
skittleo: That piece of code looks a bit ugly. It probably won't crash but it will give bad results for some input.

##### Share on other sites
they coincide if the points move from one set of the line to another.

For eg. P1 (on line 1) is above the line, but P2 (other end) is below the line.
Therefore line 1 crosses the other line.

Same for the other way around. (ie P1 is below the line, then above).

....

.    . \ /   /  ..

So, the top right point is to the right of the top left point.
That is not so for the bowwom. (it is reversed), so they intersect.

From,
Nice coder

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 9
• 10
• 11
• 13
• 9
• ### Forum Statistics

• Total Topics
634094
• Total Posts
3015470
×