Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Robo

Line intersections with Circles

This topic is 6927 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 people, I was wondering if anyone knew of an efficient method of detecting collision with a line segment and a circle. I am doing something now that isn''t quite right, but it works a bit. Are there any parametric equations that can easily detect the points of collision? I am not a math genius unfortunately, and I have even looked in multiple math books for something relating but alas I can find nothing. Anyhelp out there? thanks! Rob

Share this post


Link to post
Share on other sites
Advertisement
Heh, i would just check to see if either of the end points of the line are within the radius of the circle, ie the distance from the endpoint of the line is <= the radius of the circle. Then you have special cases where niether points are in the circle, but the defined line still collides. I just thought of a method right now, and i dont even know if it will work. I would create a triangle from the two endpoints of the line and the center of the circle, and test to see if the distance of the line between the center of the circle and the midpoint of the original line is <= the radious of the circle, where there would be a collision. The segment in a triangle that extends from one point on the triangle to the midpoint of the opposite side has a name, but i cant think of it .

Hope this helps any.

Share this post


Link to post
Share on other sites
Maybe this will help (p1 & p2 are line end-points):

lineLengthSquared = (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y)
p1SepSquared = (c.x-p1.x)*(c.x-p1.x) + (c.y-p1.y)*(c.y-p1.y)
p2SepSquared = (c.x-p2.x)*(c.x-p2.x) + (c.y-p2.y)*(c.y-p2.y)

if(p1SepSquared < c.radiusSquared OR p2SepSquared < c.radiusSquared){
return TRUE;
}
else if(p1SepSquared < lineLengthSquared+c.radiusSquared && p2SepSquared < lineLengthSquared+c.radiusSquared){
/* The if statement above is intended to test if the circle is between the two endpoints. It's fairly quick but slightly inaccurate, so you might need to find a better test. */

/* get equation of line in the form a(x-p1.x) + b(y-p1.y) = 0 */

lineLength = sqrt(lineLengthSquared);
a = (p2.y-p1.y)/lineLength;
b = (p1.x-p2.x)/lineLength;

return ( fabs(a*(c.x-p1.x) + b*(c.y-p1.y)) < c.radius );
}
else{
return FALSE;
}

I'm way too lazy to test this, so sorry if it doesn't work.

Edited by - Eric on 4/29/00 4:42:47 AM

Share this post


Link to post
Share on other sites
that is basicly right, your solving to see if there is a answer for a set of multiple equations namely -

x^2 + y^2 = r^2 / Circle

y = m*x + b / Line

this works but is REALLY slow, so my question is this:
If you are useing this in a game wouldn''t it be faster to use a bounding box and "fudge" the answer? because the stuff above would work but if your not useing it in some type of near perfect result required process (pronounced atomic physics or fluid flow then the cpu cycles could be better spent in AI, graphics, etc..



I have always been lost!

Share this post


Link to post
Share on other sites
Actually, the method i mentioned earlier works, with a few revisions. That think i said with creating the triangles and everything, only do that once you determine that none of the endpoints lie in the circle. Then, do my method. If it doesn''t work the first time (there could be a collision even when the detection says there isn''t, try to figure out when ), do it again, only using the midpoint of the line instead of the end of the line as a vertex of the triangle. Reiterate this several times, and if it still doesn''t detect a collision, there probably isn''t. Of course, the more you reiterate this detection, the more likely you could find a collision.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!