Sign in to follow this  
Trandafira

Line Line Intersection Troubles

Recommended Posts

Trandafira    133
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 this post


Link to post
Share on other sites
Trandafira    133
Quote:
Original post by jyk
What 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 this post


Link to post
Share on other sites
Cowboy Coder    365
((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 this post


Link to post
Share on other sites
Zipster    2365
Quote:
Original post by Trandafira
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.

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


Link to post
Share on other sites
jyk    2094
Quote:
Original post by Trandafira
Quote:
Original post by jyk
What 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 segement
float P2x = _rLineA.GetQ().x + _rLineA.GetV().x;
float P2y = _rLineA.GetQ().y + _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.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 this post


Link to post
Share on other sites
Trandafira    133
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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this