Line intersections with Circles
Author
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
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.
.Hope this helps any.
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
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
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!
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!
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.
), 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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
