Jump to content
  • Advertisement
Sign in to follow this  
Saber Rules

Intersection of a line and a circle

This topic is 4860 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

I'm trying to locate a function written in C or C++ that will give me the intersection points of a line and a circle. I've downloaded several math libraries and have been googling most of the day. The closest I've gotten to my goal is this: http://intervision.hjem.wanadoo.dk/tech1002.htm The problem is that this code is written in Lisp and I'm having a hard time translating it into C. It appears to do exactly what I want but I'm not confident that I will translate it correctly and will end up spending more hours debugging it only to never get it working at all. Does anyone know where I can find some 2D line/circle intersection code in C/C++ that will give me the point(s) of intersection? Preferably platform-independent and library independent.

Share this post


Link to post
Share on other sites
Advertisement
I don't have code, but it's pretty simple in 2D. The formula (in cartesian coordinatse) for distance of a line from a point is:

d =

Like this find distance of the center of the circle from the line. Now, for an intersection, d < r (where r is the radius of the circle).

Read up here, by the way.

/edit: The formula above assumes the equation of your line is ax + by + c = 0, and (x0, y0) are the coordinates of the center of the circle in your case.

/edit2: Reading your post again, I overlooked first that you wanted the points of contact. For that you will have to solve the equations of the line and the circle. Substitute one of the variables from the line eqn to the circle eqn (on paper), it should be pretty easy to get the coordinates of the points of contact. If you have trouble with this, post back. I would do it myself for you but I'm in a lot of hurry.

Share this post


Link to post
Share on other sites
The standard way to derive this is to plug the line equation O+tD into the circle equation |X-C|2 = r2 and solve the resulting quadratic for t. The following is not the best or most robust possible code, but it does illustrate the algorithm:


bool IntersectLineCircle(
const Vector2& O, // Line origin
const Vector2& D, // Line direction
const Vector2& C, // Circle center
float radius, // Circle radius
float t[2], // Parametric values at intersection points
Vector2 point[2] // Intersection points
Vector2 normal[2]) // Normals at intersection points
{
Vector2 d = O - C;
float a = D.Dot(D);
float b = d.Dot(D);
float c = d.Dot(d) - radius * radius;

float disc = b * b - a * c;
if (disc < 0.0f) {
return false;
}

float sqrtDisc = Math::Sqrt(disc);
float invA = 1.0f / a;
t[0] = (-b - sqrtDisc) * invA;
t[1] = (-b + sqrtDisc) * invA;

float invRadius = 1.0f / radius;
for (int i = 0; i < 2; ++i) {
point = O + t * D;
normal = (point - C) * invRadius;
}

return true;
}





Note that the function for line-sphere intersection is exactly the same, except in R3 instead of R2.

[Edited by - jyk on December 2, 2005 10:57:16 PM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!