Line Segment/Circle collision detection?

James Stanley

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

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.

GullRaDriel

http://www.harveycartel.org/metanet/tutorials/tutorialA.html

SiegeLord

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.

James Stanley

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

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)
3float A = x - x1;//vector from one end point to the test point
4float B = y - y1;
5float C = x2 - x1;//vector from one end point to the other end point
6float D = y2 - y1;
7 
8float dot = A * C + B * D;//some interesting math coming from the geometry of the algorithm
9float len_sq = C * C + D * D;
10float param = dot / len_sq;
11 
12float 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
17if(param < 0)
18{
19    xx = x1;
20    yy = y1;
21}
22else if(param > 1)
23{
24    xx = x2;
25    yy = y2;
26}
27else
28{
29    xx = x1 + param * C;
30    yy = y1 + param * D;
31}
32 
33float dist = dist(x,y,xx,yy);//distance from the point to the segment

James Stanley

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

My thoughts, turned into code:

1#define NO_COLLISION -1
2 
3float test_line_against_circle(float *CircleCentre, float CircleRadius, float *LineStart, float *LineEnd)
4{
5   float LineVec[2] = {LineEnd[0] - LineStart[0], LineEnd[1] - LineStart[1]};
6   float VecToLine[2] = {LineStart[0] - CircleCentre[0], LineStart[1] - CircleCentre[1]};
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[0]*LineVec[0] + LineVec[1]*LineVec[1];
13   b = 2 * ( VecToLine[0]*LineVec[0] + VecToLine[1]*LineVec[1] );
14   c = ( VecToLine[0]*VecToLine[0] + VecToLine[1]*VecToLine[1]) - 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...
32float InterceptTime;
33InterceptTime = test_line_against_circle(CircleCentre, CircleRadius, LineStart, LineEnd);
34 
35if(InterceptTime >= 0 && InterceptTime <= 1)
36{
37   printf("interception!\n");
38   printf("at position: (%0.2f, %0.2f)\n", LineStart[0] + InterceptTime * (LineEnd[0] - LineStart[0]), LineStart[1] + InterceptTime * (LineEnd[1] - LineStart[1]));
39}
40...

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

James Stanley

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

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?

SiegeLord

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.

$<math>projection = \vec v_{pt} \cdot \vec v_{seg}</math>$

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 $<math>\vec v_{seg}</math>$ . 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 $<math>\vec v_{seg}</math>$ 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:

$<math>param = \frac {\vec v_{pt} \cdot \vec v_{seg}} {\left \Vert \vec v_{seg} \right \|^2}</math>$

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.

James Stanley

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.

Thread #595918. Printed from Allegro.cc

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

1	#define NO_COLLISION -1
2
3	float test_line_against_circle(float CircleCentre, float CircleRadius, float LineStart, float *LineEnd)
4	{
5	float LineVec[2] = {LineEnd[0] - LineStart[0], LineEnd[1] - LineStart[1]};
6	float VecToLine[2] = {LineStart[0] - CircleCentre[0], LineStart[1] - CircleCentre[1]};
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[0]LineVec[0] + LineVec[1]LineVec[1];
13	b = 2 * ( VecToLine[0]LineVec[0] + VecToLine[1]LineVec[1] );
14	c = ( VecToLine[0]VecToLine[0] + VecToLine[1]VecToLine[1]) - CircleRadius*CircleRadius;
15
16	/* solve for t */
17	sqrtterm = bb - 4a*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[0] + InterceptTime * (LineEnd[0] - LineStart[0]), LineStart[1] + InterceptTime * (LineEnd[1] - LineStart[1]));
39	}
40	...