Checking collision: line X line, line X circle

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

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;

// 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;
}

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 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 on other sites
Quote:
 Original post by jykCould 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 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 on other sites
Quote:
 Original post by SirisianHere 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 ChaosYou 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 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 on other sites
try also looking at the site geometric tools --- i think there are codes in there for most shapes

• What is your GameDev Story?

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

(You must login to your GameDev.net account.)

• 11
• 15
• 11
• 11
• 9
• Forum Statistics

• Total Topics
634151
• Total Posts
3015825
×