Sign in to follow this  
Alpha Nox

Checking collision: line X line, line X circle

Recommended Posts

Hi everyone, I'm working in a 2D game in a SDL and I need to check for collisions between a line segment and another. And also between a line segment and a circle. I've written a code that should do that and would like to know if it's correct, if there is a faster way to do it, what you think of it, etc. Any help/comments/suggestions appreciated. =) Thanks in advance, Victor Freire

struct pos2d
{
	double X;
	double Y;
};

// Two variable linear equation class

class lin_equation2
{
public:
	double A;
	double B;
	double C;
	lin_equation2();
};

lin_equation2::lin_equation2()
{
	A = 0;
	B = 0;
	C = 0;
}

class circle
{
	
public:
	// Creates a circle using the center coordinates and the radius
	circle(double Cx,double Cy,double Cradius);

	double X;
	double Y;
	double radius;
	
	// Get boundaries
	double GetLeftBound() { return (X - radius); };
	double GetRightBound(){ return (X + radius); };
	double GetUpperBound(){ return (Y + radius); };
	double GetLowerBound(){ return (Y - radius); };
	
	// Useful for debugging
	void DisplayEquation();

};

circle::circle(double Cx,double Cy,double Cradius)
{
	X = Cx;
	Y = Cy;
	radius = Cradius;
}

void circle::DisplayEquation()
{
	cout << "Center: " << X << " , "  << Y << endl;
	cout << "Radius: " << radius << endl;
	cout << "Xbound[0]: " << GetLeftBound() << endl;
	cout << "Xbound[1]: " << GetRightBound() << endl;
	cout << "Ybound[0]: " << GetLowerBound() << endl;
	cout << "Ybound[1]: " << GetUpperBound() << endl << endl;

}

class line_segment
{
	pos2d GetIntersectionPoint(const line_segment &ls1);
	lin_equation2 eq;
	double Xbound[2];
	double Ybound[2];
public:
	
	line_segment();
	// Creates a line segment using its extremity points
	line_segment(double X1,double Y1,double X2,double Y2);
	// Checks for collision with another line_segment
	bool CheckCollision(const line_segment &ls1);
	// Checks for collision with a circle
	bool CheckCollision( circle &cc1);
	// Useful for debugging
	void DisplayEquation();
		
};

line_segment::line_segment()
{
	Xbound[0] = 0;
	Xbound[1] = 0;
	Ybound[0] = 0;
	Ybound[1] = 0;

}

line_segment::line_segment(double X1,double Y1,double X2,double Y2)
{
	
	// Uses 0 for left/down and 1 for right/up
	if(X1 < X2)
	{
		Xbound[0] = X1;
		Xbound[1] = X2;
	}
	else
	{
		Xbound[0] = X2;
		Xbound[1] = X1;
	}
	
	if(Y1 < Y2)
	{
		Ybound[0] = Y1;
		Ybound[1] = Y2;
	}
	else
	{
		Ybound[0] = Y2;
		Ybound[1] = Y1;
	}

	eq.A = Y1 - Y2;
	eq.B = X2 - X1;
	eq.C = -X1*Y2 + X2*Y1;
	
	// make eq.A always positive to simplify calculations
	if(eq.A < 0)
	{
		eq.A = -eq.A;
		eq.B = -eq.B;
		eq.C = -eq.C;
	}


	
}

bool line_segment::CheckCollision(const line_segment &ls1)
{
	
	// check if the segment has points in common within the boxes created by their extremities
	if((Xbound[1] < ls1.Xbound[0]) || (Xbound[0] > ls1.Xbound[1]) 
|| (Ybound[1] < ls1.Ybound[0]) || (Ybound[0] > ls1.Ybound[1]) ) return false; 
	
	// calculate the intersection point if it existed and check if they belong to both line segments
	pos2d inp = GetIntersectionPoint(ls1);

	if( (eq.A * inp.X + eq.B * inp.Y == eq.C) 
&& (ls1.eq.A * inp.X + ls1.eq.B * inp.Y == ls1.eq.C) )
	{
		// displays intersection point on the screen if enabled
		if(DEBUG_OPTIONS) 
		{
			cout << "refpoint added\n";
			refpoints.push_back(inp);
		}
		return true;
	}
	
	return false;
	
}

bool line_segment::CheckCollision( circle &cc1)
{
	// first of all, check boundaries cause we're dealing with a line segment here not an infinite line
	if((Xbound[1] < cc1.GetLeftBound()) 
|| (Xbound[0] > cc1.GetRightBound()) || (Ybound[1] < cc1.GetLowerBound()) 
|| (Ybound[0] > cc1.GetUpperBound()) ) return false; 
	
	// uses distance from circle's center to the line segment(equation to calculate distance from line to point)
	// using -eq.C since we're passing it to the first member

	double e1 = ( abs(eq.A * cc1.X + eq.B * cc1.Y - eq.C) ) / sqrt(eq.A*eq.A + eq.B*eq.B);
	
	if(e1 > cc1.radius )
	{
		return false;
	}
		
	return true;
	
}

pos2d line_segment::GetIntersectionPoint(const line_segment &ls1)
{
	
	// Intersection points
	pos2d interpoint;
	interpoint.X = (eq.B * ls1.eq.C - eq.C * ls1.eq.B) / 
(eq.B * ls1.eq.A - eq.A * ls1.eq.B);
	interpoint.Y = (eq.A * ls1.eq.C - eq.C * ls1.eq.A) / 
(eq.A * ls1.eq.B - eq.B * ls1.eq.A);
	
	return interpoint;
	
}

void line_segment::DisplayEquation()
{
	if(eq.A != 0) cout << eq.A << "x" ;
	if(eq.B != 0) cout << eq.B << "y" ;
	cout << " = " << eq.C << "\n\n";
	
	cout << "Xbound left: " << Xbound[0] << endl;
	cout << "Xbound right: " << Xbound[1] << endl;
	cout << "Ybound down: " << Ybound[0] << endl;
	cout << "Ybound up: " << Ybound[1] << "\n\n";
}






[Edited by - Alpha Nox on July 5, 2008 8:07:46 PM]

Share this post


Link to post
Share on other sites
Could you edit your post and break some of the longer lines in your code? That will make it easier to read (as it is, some of us - well, I at least - have to scroll back and forth in order to access the vertical scroll bar).

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Could you edit your post and break some of the longer lines in your code? That will make it easier to read (as it is, some of us - well, I at least - have to scroll back and forth in order to access the vertical scroll bar).


Sorry about that. It's fixed now.

Share this post


Link to post
Share on other sites
You want to know if there's a faster way to do it:
If you aren't having problems, don't look for faster ways to do things. There's ALWAYS a faster way to do it until you break open your inline assembly, and even then, you might find a better way to implement your algorithm. If it runs as fast as you NEED, and it's simple enough for you to understand, it's good ENOUGH.

You're using the standard form for the equasion of a line. Good documentation would note that. Coming from a trig and pre-calc background, I was thinking of the quadratic formula when I saw A, B, and C. First, noting that you're using the standard equation is good, second, writing it (Ax + By = C) is good so someone who doesn't know can look it up (but, it is OK to assume people know what you're talking about).

Noting you're equation for the circle MIGHT be helpful, but it's less necessary because X, Y, and radius are self explanatory, whereas A, B, and C can seem a little abstract.

I also think it's a good practice to write the equation of what I'm doing where I use it. It's a good resource for when the C++ equation is confusing:
interpoint.X = (eq.B * ls1.eq.C - eq.C * ls1.eq.B) / (eq.B * ls1.eq.A - eq.A * ls1.eq.B).
I just don't like having to remember what eq and ls1 and crap like that means instead of having the actual equation right about it and say "Oh, right, B1 * C2."

Hope I've been helpful. Don't know if what you wrote will work; I should refreshen my math knowledge. But, if you try it out, and it LOOKS good, what more do you want?

Share this post


Link to post
Share on other sites
Quote:
Original post by Sirisian
Here it's C# but it has the basic intersection stuff.


It's similar so it will be useful, the collision code I wrote seem to be working after I fixed a minor mistake except for some situations. I think it's not this part of code that is wrong, I'll do some more tests and fix it soon.

Quote:
Original post by Splinter of Chaos
You want to know if there's a faster way to do it:
...


I often look for potential speed-ups and enhancements in my code because I want improve my coding skills. Your comment on the code was helpful, I keep wondering if I'm doing something correctly or if I could do a lot better so I wanted a review of the code to see how I'm doing so far. =)

Thanks for the help everyone,

Victor Freire

Share this post


Link to post
Share on other sites
My programming in such languages is very very rusty, so I didn't look through the code. That said, I could suggest the following strategy, which should be pretty good:

line-line:
1) Imagine the lines are infinite and find the intersection (2 equations 2 unknowns. Speed should be limited by a couple divisions).
2) Check if that intersection point is in both segments (just test 4 inequalities at most).

line-circle:
1) Create a line segment perpendicular to the initial line, such that the start of the line is the center of the circle, and the length is the radius of the circle. (this will take a couple divisions)(do you know linear algebra?)
2) Apply the line-line method to the initial line and the one you just created.


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