# Line Line Intersection Troubles

## Recommended Posts

I'm in the process of doing collision detection for a 2d game. One of the collisions is with two lines. (The first line being from an objects position and it's position + it's velocity and the second being a static line) I surfed the internet and found this website: Intersecting two line segments Which gives a way of finding when two lines intersect. Implemented in my code it looks like this:
bool
CLine::LineToLineCollision(CLine&  _rLineA, CLine& _rLineB)
{
//Pa = P1 + ua(P2 - P1) Where Pa and Pb are the points of collision between two lines
//Pb = P3 + ub(P4 - P3)

//Starting Points of one of the line segements
float P1x = _rLineA.GetQ().x;
float P1y = _rLineA.GetQ().y;

//Ending Points of that line segement
float P2x = _rLineA.GetV().x;
float P2y = _rLineA.GetV().y;

//Starting Points of the second line segement
float P3x = _rLineB.GetQ().x;
float P3y = _rLineB.GetQ().y;

//Ending points of the second line segement
float P4x = _rLineB.GetV().x;
float P4y = _rLineB.GetV().y;

float fDenominator = ((P4y - P3y)*(P2x - P1x) - (P4x - P3x)*(P2y - P1y));

if(fDenominator != 0)
{
float fUa = ((P4x - P3x)*(P1y - P3y)) - ((P4y  - P3y)*(P1x - P3x))
/ fDenominator;

float fUb = ((P2x - P1x)*(P1y - P3y)) - ((P2y  - P1y)*(P1x - P3x))
/ fDenominator;

if((fUa > 0 && fUa < 1) ||
(fUb > 0 && fUb < 1)) //We have intersection!
{
return (true);
}
}
return (false);
}


The object's starting position is not intersecting the line and when i set alot of velocity, there is no collision (when there should be), and when i set a small velocity, the instant after it is changed it reports that it is colliding (when it obviously isn't). Any suggestions or help would be greatly appreciated. Thanks Jonathan

##### Share on other sites
What do Q and V represent in the CLine class?

##### Share on other sites
Your last || should be an &&, since both ua AND ub have to be in the range 0..1

##### Share on other sites
Quote:
 Original post by jykWhat do Q and V represent in the CLine class?

Q and v are from the line formula t(r) = Q + r(V)
Q is the coordinates of one end of the line, V is the coordinates of the other.

@ jyk: I noticed that, but still have had no success.

##### Share on other sites
((P4x - P3x)*(P1y - P3y)) - ((P4y - P3y)*(P1x - P3x))

Need more parentheses.

Funny, when you look at code and find a bug, you think "that must be it!", and there's always something else.

(A) - (B) / C == A - (B/C), not (A-B)/C

##### Share on other sites
Quote:
 Original post by TrandafiraQ and v are from the line formula t(r) = Q + r(V)Q is the coordinates of one end of the line, V is the coordinates of the other.

Actually, using that parametric form Q is an endpoint, but V is only a direction. This is a good thing though, since the page you linked assumes you only have the endpoints and the (P2 - P1) and (P4 - P3) is merely a reduction to the parametric form.

##### Share on other sites
Quote:
Original post by Trandafira
Quote:
 Original post by jykWhat do Q and V represent in the CLine class?

Q and v are from the line formula t(r) = Q + r(V)
Q is the coordinates of one end of the line, V is the coordinates of the other.
As has been noted, V is not the second endpoint of the line but rather a vector representing its direction and length. If I'm not mistaken, you need to modify your code thusly:
//Starting Points of one of the line segements float P1x = _rLineA.GetQ().x; float P1y = _rLineA.GetQ().y; //Ending Points of that line segementfloat P2x = _rLineA.GetQ().x + _rLineA.GetV().x;float P2y = _rLineA.GetQ().y + _rLineA.GetV().y;//Starting Points of the second line segementfloat P3x = _rLineB.GetQ().x;float P3y = _rLineB.GetQ().y;//Ending points of the second line segementfloat P4x = _rLineB.GetQ().x + _rLineB.GetV().x;float P4y = _rLineB.GetQ().y + _rLineB.GetV().y;
This does introduce some redundancy into your code, but that can easily be cleaned up once you get the code working.

##### Share on other sites
Thanks for all the help guys. At the time of posting i didn't quite understand the parametric representation of a line. But after a bit of reading and your guys help I have a far better understanding. =D.

Thanks

Jonathan

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628333
• Total Posts
2982127

• 24
• 9
• 9
• 13
• 11