# Circle - Line Collsion 2D

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

## Recommended Posts

This problem is wrecking my head. I have a moving circle, with a movement vector (mvx,mvy), about to hit an abritary line (x1,y1)-(x2,y2). How do I correctly find the exact point of intersection, correctly, even if the movement vector would move the circle over the boudary line? I've tried serval different methods from the net and written loads of paper diagram, I know I'm neraly there. But I still don;t think it's working right. I can't give out the code I'm afraid.

##### Share on other sites
treat the problem as a moving point vs line collision.

if the distance peripendicular to the line goes below the radius of the sphere, you have a collision. only if this happens within the areathat lies between the endpoints though. do a point-sphere check for the endpoints/vertices.

moving point vs line is quite easy.

px(t) = p.pos.x + p.vel.x * t;
py(t) = p.pos.y + p.vel.y * t;

dist(t) = (px(t) - line.end.x) * line.normal.x + (px(t) - line.end.y) * line.normal.y = p.radius;

a simple linear equation you can solve for t.

sphere vs point is just a special case of sphere-sphere, and extremely googleable.

##### Share on other sites
bool CircleSegmentIntersection(	Vector2D lp1, //first point of segment	Vector2D lp2, //second point of segment	Vector2D C, //centre of circle	float r, //radius of circle	Vector2D& I, //intersection point	float& t //time of intersection){	lp2 -= lp1;	float length = lp2.Length();	lp2.Normalize();	Vector2D L = C - lp1;	float d = L.Dot( lp2 );	float lsquared = L.Dot( L );	float rsquared = r * r;	if (d < 0 && lsquared > rsquared)		return false;	float dsquared = d*d;	float msquared = lsquared - dsquared;	if (msquared > rsquared)		return false;	float q = (float) sqrt( rsquared – msquared );	if ( lsquared > rsquared )		t = d - q;	else		t = 0.0f;	if( t > length ) return false;	else 	{		I = lp1 + lp2 * t;		t /= length;	}	return true;}bool PointConfined( Vector2D lp1, Vector2D lp2, Vector2D p ){	if( p == lp1 || p == lp2 )		return true;	if( sign( ( p - lp1 ).Dot( lp2 - lp1 ) ) != sign( ( p - lp2 ).Dot( lp2 - lp1 ) ) )		return true;	return false;}Vector2D RayPlaneIntersection( Vector2D po, Vector2D pn, Vector2D ro, Vector2D rv ){   float d = -pn.Dot( po );   float numer = pn.Dot( ro ) + d;   float denom = pn.Dot( rv );   return ro + rv * -( numer / denom );}bool CirclePlaneSweep(	float r, //circle radius	Vector2D c0, //previous position of circle	Vector2D c1, //current position of circle	Vector2D lp0, //the plane	Vector2D lp1,	float& t, //time of collision	Vector2D &cpn //collision plane normal){	//Cancel out if our velocity is 0 or plane is facing away from us	if( ( ( c1 - c0 ).x == 0 && ( c1 - c0 ).y == 0 ) || ( c1 - c0 ).Cross( lp1 - lp0 ) > 0 )		return 0;	//Intersection point	Vector2D ci;	//Determine the plane normal	Vector2D pn = Vector2D( lp1.y - lp0.y, lp0.x - lp1.x ).Normalized();	//Determine velocity	Vector2D v = ( c1 - c0 ).Normalized();	//Determine the inverted plane normal sized to the ball's radius	Vector2D ipn = pn.Inverted() * r;	//Add this to the balls origin:	Vector2D ip = c0 + ipn;	//Now find the intersection point with the plane by casting the velocity	//from IP and checking for intersection with the plane	ip = RayPlaneIntersection( lp0, pn, ip, v );	ci = ip + pn * r;	//Determine if the intersection point is actually on the plane	if( !PointConfined( lp0, lp1, ip ) )	{		//No? Then check for collision against endpoints		//Find the closest endpoint by comparing the squared distances		Vector2D ep = ( lp0 - c0 ).LengthSqr() < ( lp1 - c0 ).LengthSqr() ? lp0 : lp1;		//Check for point segment/circle intersection		if( !CircleSegmentIntersection( c0, c1, ep, r, ci, t ) )			return 0;		//CircleSegmentIntersection determined the time of collision for us		//Collision Plane Normal is the vector from the end point to the circle centre at		//time of collsion		cpn = ( ci - ep ).Normalized();		return 1;	}	//Determine if the sphere's new position is actually on the path it followed	if( !PointConfined( c0, c1, ci ) )	{		return 0;	}	//Determine time of collision	t = ( ci - c0 ).Length() / ( c1 - c0 ).Length();	//Collision Plane Normal is that of the plane	cpn = pn;	return 1;}

That is the code I use. The CirclePlaneSweep() function only detects against one side of the segment (my game world consists of enclosed polygons) but I imagine this can be altered.
I based this code on prior knowledge an the concepts outlined in this article. It is a good read that simplifies the procedure considerably. The CircleSegmentIntersection() function is Oliii’s (thanks for that one).

Note: this code could well be optimized. It seems fast enough for my needs (fast-action game, levels consisting of several hundred segments). I’ve not encountered any bugs and I have been using it for some time but I wouldn’t go so far as to ensure that none exist.

Hope this helps,
Jackson Allan

##### Share on other sites
Thanks for the help.

• 36
• 12
• 10
• 10
• 9
• ### Forum Statistics

• Total Topics
631359
• Total Posts
2999538
×

## Important Information

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!