Which is the more efficient method for calculating the intersections of two circles?

Question

I'm trying to find the fastest and easiest way in a C# program to calculate the intersections of two circles. From what I can tell there are two possible methods, and you'll have to forgive me for not knowing the official names for them.

We're assuming you know the center points for both circles and their exact radii, from which you can calculate the distance between them, so all that is missing are the point(s) of intersection. This is taking place on a standard x-y plot.

The first is a kind of substitution method like the one described here where you combine the two circle formulas and isolate either x or y, then sub it back in to an original formula to end up with a quadratic equation that can be solved for two (or possibly one or none) coordinates for an axis, which then lets you find the corresponding coordinates on the other axis.

The second I have seen a reference to is using a Law of Cosines method to determine the angles, which would then let you plot a line for each side on the grid, and put in your radius to find the actual intersection point.

I have written out the steps for the first method, and it seems rather lengthy. The second one is going to take some research/learning to write out but sounds simpler. What I've never done is translate processes like this into code, so I don't know ultimately which one will be the easiest for that application. Does anyone have advice on that? Or am I perhaps going about the the complete wrong way? Is there a library already out there that I can use for it instead of reinventing the wheel?

Some context: I'm worried mainly about the cost to the CPU to do these calculations. I plan on the application doing a heck of a lot of them at once, repeatedly, hence why I want the simplest way to accomplish it.

Answer 1

Computational geometry is almost always a pain to implement. It's also almost always quite CPU-intensive. That said, this problem is just algebra if you set it up right.

Compute d = hypot(x2-x1, y2-y1), the distance between the two centres. If r1 + r2 < d, there is no intersection. If r1+r2 == d, the intersection is at (x1, y1) + r1/(r1+r2) * (x2-x1,y2-y1). If d < abs(r1-r2), one circle is contained in the other and there is no intersection. You can work out the case where the two circles are tangent and one is contained in the other. I will only deal with the remaining case.

You want to find distances h orthogonal to (x2-x1,y2-y1) and p parallel to (x2-x1,y2-y1) so that p^2 + h^2 = r1^2 and (d-p)^2 + h^2 = r2^2. Subtract the two equations to get a linear equation in p: d^2-2dp = r2^2-r1^2. Solve this linear equation for p. Then h = sqrt(r1^2 - p^2).

The coordinates of the two points are (x1,y1) + p (x2-x1,y2-y1) / d +/- h (y2-y1, x1-x2) / d. If you work through the derivation above and solve for p/d and h/d instead, you may get something that does fewer operations.