 Allegro.cc Forums » Programming Questions » Line Segment/Circle collision detection?

Credits go to GullRaDriel, SiegeLord, and Thomas Harte for helping out!
 This thread is locked; no one can reply to it.  Line Segment/Circle collision detection?
 James Stanley Member #7,275 May 2006 Can anyone link me to a tutorial about detecting collisions (and calculating responses would also be helpful) between line segments and circles?Thanks.
 Thomas Harte Member #33 April 2000 I think there was recently a thread here somewhere, but I can't find it now. Personally, I usually work it out every time from first principles.The line segment is u + tv, where u and v are vectors and t is a scalar with a value between 0 and 1. The circle is the collection of all points p such that | p - c | = r, where c is a vector, || is the modulus/length operator and r is a scalar.So then just solve for | (u + tv) - c | = r. It turns into a quadratic, throw the quadratic formula at it and you can see how you end up with either no solutions for r (the line misses the circle), one solution (the line is a tangent) or two solutions (the line crosses the circle). Check those solutions to see if t is between 0 and 1 inclusive. [My site] [Tetrominoes]
 GullRaDriel Member #3,861 September 2003 "Code is like shit - it only smells if it is not yours"Allegro Wiki, full of examples and articles !!
 SiegeLord Member #7,827 October 2006 I made a post awhile ago detailing how to calculate the distance between a line segment and a point, which can be used for collision detection part... it does give you the point of contact sort of, so you could use it for the response as well.Here it is. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]
 James Stanley Member #7,275 May 2006 Thomas, while I believe what you say, I have no idea what that means.Gull, I've already seen that page and it meant as much to me as Thomas's post.SiegeLord, that post is in a language I understand better (code instead of maths ). I'll see about shoehorning that in to my project.Thanks everyone!EDIT:SiegeLord, what I've found so far is that it only finds the distance between the point and the top-left point on the line. This might be a problem in my code, though.Also, does your code work with negative co-ordinates involved?
SiegeLord
Member #7,827
October 2006 I just tested the code, and everything seems to work as it is supposed to. There's probably some issue in your code... perhaps stemming from my terrible documentation of the algorithm. And yes it is does work with negatives.

Here's a better commented version of it, in case it helps:

 1 //line segment goes from (x1,y1) to (x2,y2) 2 //the test point is at (x,y) 3 float A = x - x1;//vector from one end point to the test point 4 float B = y - y1; 5 float C = x2 - x1;//vector from one end point to the other end point 6 float D = y2 - y1; 7 8 float dot = A * C + B * D;//some interesting math coming from the geometry of the algorithm 9 float len_sq = C * C + D * D; 10 float param = dot / len_sq; 11 12 float xx,yy;//the coordinates of the point on the line segment closest to the test point 13 14 //the parameter tells us which point to pick 15 //if it is outside 0 to 1 range, we pick one of the endpoints 16 //otherwise we pick a point inside the line segment 17 if(param < 0) 18 { 19 xx = x1; 20 yy = y1; 21 } 22 else if(param > 1) 23 { 24 xx = x2; 25 yy = y2; 26 } 27 else 28 { 29 xx = x1 + param * C; 30 yy = y1 + param * D; 31 } 32 33 float dist = dist(x,y,xx,yy);//distance from the point to the segment

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

 James Stanley Member #7,275 May 2006 SiegeLord said: float dot = A * C + B * D;//some interesting math coming from the geometry of the algorithm float len_sq = C * C + D * D; float param = dot / len_sq;  Would that be Pythagoras' theorem?It seems to me that the parameter is the length of the dot product of the vectors (I know of dot products, but don't understand them - my wording may be unusual/inaccurate), divided by the length of the line segment. Can you explain why this works?Also, the dist() function. As far as I can tell, that needs Pythagoras' theorem to calculate the distance. I was using: xdiff = x - xx; ydiff = y - yy; hypot = sqrt((xdiff * xdiff) + (ydiff * ydiff));  That seem about right to you?
Thomas Harte
Member #33
April 2000 My thoughts, turned into code:

 1 #define NO_COLLISION -1 2 3 float test_line_against_circle(float *CircleCentre, float CircleRadius, float *LineStart, float *LineEnd) 4 { 5 float LineVec = {LineEnd - LineStart, LineEnd - LineStart}; 6 float VecToLine = {LineStart - CircleCentre, LineStart - CircleCentre}; 7 8 /* create a quadratic formula of the form ax^2 + bx + c = 0 */ 9 float a, b, c; 10 float sqrtterm, res1, res2; 11 12 a = LineVec*LineVec + LineVec*LineVec; 13 b = 2 * ( VecToLine*LineVec + VecToLine*LineVec ); 14 c = ( VecToLine*VecToLine + VecToLine*VecToLine) - CircleRadius*CircleRadius; 15 16 /* solve for t */ 17 sqrtterm = b*b - 4*a*c; 18 19 /* if the term we intend to square root is less than 0 then the answer won't be real, so it definitely won't be t in the range 0 to 1 */ 20 if(sqrtterm < 0) return NO_COLLISION; 21 22 /* if we can assume that the line segment starts outside the circle (e.g. for continuous time collision detection) then the following can be skipped and we can just return the equivalent of res1 */ 23 sqrtterm = sqrt(sqrtterm); 24 res1 = ( -b - sqrtterm ) / (2 * a); 25 res2 = ( -b + sqrtterm ) / (2 * a); 26 27 if(res1 >= 0 && res1 <= 1) return res1; 28 return res2; 29 } 30 31 ... 32 float InterceptTime; 33 InterceptTime = test_line_against_circle(CircleCentre, CircleRadius, LineStart, LineEnd); 34 35 if(InterceptTime >= 0 && InterceptTime <= 1) 36 { 37 printf("interception!\n"); 38 printf("at position: (%0.2f, %0.2f)\n", LineStart + InterceptTime * (LineEnd - LineStart), LineStart + InterceptTime * (LineEnd - LineStart)); 39 } 40 ...

You know, completely untested, just worked out on a piece of paper, etc.

 James Stanley Member #7,275 May 2006 I'm going to try implementing that now.Thanks!EDIT:That has the same problem as the other code - it only detects collisions with the line start point.I'm sure it's me doing something wrong, but I can't think what it is.EDIT2:These snippets don't depend on C++, do they?I'm running C, but I don't see how that would affect anything.
 Thomas Harte Member #33 April 2000 Quote: That has the same problem as the other code - it only detects collisions with the line start point. No it doesn't. What gives you that impression? Have you tested and discovered a mistake in my coding, or are you saying that just from reading it?EDIT: and SiegeLord's shouldn't either. Are you sure you aren't feeding incorrect numbers into your program somewhere? [My site] [Tetrominoes]
 SiegeLord Member #7,827 October 2006 Quote: Can you explain why this works? Here's a rough outline of how it works. First, we form the two vectors, one that is the line segment, and the other one that goes from one endpoint of the segment to the center of the circle. Note that they share the same starting vertex. Now, we take the dot product of the two vectors, which roughly represents the projection of one vector onto the other. Now, our goal is to get a normalized projection, i.e. such that if the point is directly above or below the segment vector we will get a parameter to be between 0 and 1. We accomplish this in two steps. First, we divide once by the length of . This gives us the magnitude of the projected point vector... basically as if it was casting a shadow onto the segment vector. Now, we divide that number again by the length of the to normalize the parameter. Why? Because clearly if the shadow of the vector is less than the length of the segment vector, we should get a number less than one. It does not take too much imagination to see that this relationship is linear. In any event, here's the net formula: Which nicely corresponds to the code. Note that we avoid taking the square root because we divide twice by the length, hence the variable being the length-squared. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]
 James Stanley Member #7,275 May 2006 Quote: No it doesn't. What gives you that impression? Read the line after the one you quoted .I'm sure your code probably works fine, it's just that my usage of it means that it only detects collisions with the start point. Quote: Are you sure you aren't feeding incorrect numbers into your program somewhere? I'm certain that I am. Problem is, I've checked them all and they all seem right.SiegeLord, that kinda makes sense. It seems to be a similar algorithm to Thomas Harte's, except you have the param thing and he has the quadratic formula.EDIT:Both functions work on the few test cases I just tried, I just can't make them work in the game.EDIT2:I just made it print out the exact numbers it was giving the functions, and they seemed right.
 Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads