I have a line from A to B and a circle positioned at C with the radius R.
What is a good algorithm to use to check whether the line intersects the circle? And at what coordinate along the circles edge it occurred?
I have a line from A to B and a circle positioned at C with the radius R.
What is a good algorithm to use to check whether the line intersects the circle? And at what coordinate along the circles edge it occurred?
I would use the algorithm to compute the distance between a point (circle center) and a line (line AB). This can then be used to determine the intersection points of the line with the circle.
Let say we have the points A, B, C. Ax and Ay are the x and y components of the A points. Same for B and C. The scalar R is the circle radius.
This algorithm requires that A, B and C are distinct points and that R is not 0.
Here is the algorithm
Here's an implementation in Javascript. My approach is to first convert the line segment into an infinite line then find the intersection point(s). From there I check if the point(s) found are on the line segment. The code is well documented, you should be able to follow along.
You can try out the code here on this live demo. The code was taken from my algorithms repo.
If the line's coordinates are A.x, A.y and B.x, B.y and the circles center is C.x, C.y then the lines formulae are:
x = A.x * t + B.x * (1 - t)
y = A.y * t + B.y * (1 - t)
where 0<=t<=1
and the circle is
(C.x - x)^2 + (C.y - y)^2 = R^2
if you substitute x and y formulae of the line into the circles formula you get a second order equation of t and its solutions are the intersection points (if there are any). If you get a t which is smaller than 0 or greater than 1 then its not a solution but it shows that the line is 'pointing' to the direction of the circle.
Here is a solution written in golang. The method is similar to some other answers posted here, but not quite the same. It is easy to implement, and has been tested. Here are the steps:
The values for A, B, and C for the quadratic are derived here, where (n-et) and (m-dt) are the equations for the line's x and y coordinates, respectively. r is the radius of the circle.
Therefore A = ee+dd, B = - 2(en + dm), and C = nn + mm - rr.
Here is the golang code for the function:
I tested it with this function, which confirms that solution points are within the line segment and on the circle. It makes a test segment and sweeps it around the given circle:
Here is the output of the test:
Finally, the method is easily extendable to the case of a ray starting at one point, going through the other and extending to infinity, by only testing if t > 0 or t < 1 but not both.
I just needed that, so I came up with this solution. The language is maxscript, but it should be easily translated to any other language. sideA, sideB and CircleRadius are scalars, the rest of the variables are points as [x,y,z]. I'm assuming z=0 to solve on the plane XY
Circle is really a bad guy :) So a good way is to avoid true circle, if you can. If you are doing collision check for games you can go with some simplifications and have just 3 dot products, and a few comparisons.
I call this "fat point" or "thin circle". its kind of a ellipse with zero radius in a direction parallel to a segment. but full radius in a direction perpendicular to a segment
First, i would consider renaming and switching coordinate system to avoid excessive data:
Second, index h in hvec2f means than vector must favor horisontal operations, like dot()/det(). Which means its components are to be placed in a separate xmm registers, to avoid shuffling/hadd'ing/hsub'ing. And here we go, with most performant version of simpliest collision detection for 2D game:
I doubt you can optimize it any further. I am using it for neural-network driven car racing collision detection, to process millions of millions iteration steps.