Jump to content
  • Advertisement
Sign in to follow this  
cptrnet

Line Collision

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

If you intended to correct an error in the post then please contact us.

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.

Share this post


Link to post
Share on other sites
Advertisement
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;
}

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!