How do I detect intersections between a circle and any other circle in the same plane?

Question

I'm looking for an algorithm to detect if a circle intersects with any other circle in the same plane (given that there can be more than one circle in a plane).

One method I have found is to do the separating axis test. It says:

Two objects don't intersect if you can find a line that separates the two objects, i.e. a line such that all objects or points of an object are on different sides of the line.

However, I don't know how to apply this method to my case.

Can anybody help me?

Solution 1

Two circles intersect if, and only if, the distance between their centers is between the sum and the difference of their radii. Given two circles (x0, y0, R0) and (x1, y1, R1), the formula is as follows:

ABS(R0 - R1) <= SQRT((x0 - x1)^2 + (y0 - y1)^2) <= (R0 + R1)

Squaring both sides lets you avoid the slow SQRT, and stay with ints if your inputs are integers:

(R0 - R1)^2 <= (x0 - x1)^2 + (y0 - y1)^2 <= (R0 + R1)^2

Since you need only a yes/no test, this check is faster than calculating the exact intersection points.

The above solution should work even for the "one circle inside the other" case.

Solution 2

Assuming filled circle intersection (ie: One circle inside another is an intersection).

Where:

• x0,y0,r0 = Center and radius of circle 0.
• x1,y1,r1 = Center and radius of circle 1.

Code:

boolean intersects = Math.hypot(x0-x1, y0-y1) <= (r0 + r1);

Solution 3

XNA / C# solution

    class Circle
    {
        public Vector2 Center;
        public float Radius;

        public bool Intersects(Circle circle)
        {
            float distanceX = Center.X - circle.Center.X;
            float distanceY = Center.Y - circle.Center.Y;
            float radiusSum = circle.Radius + Radius;
            return distanceX * distanceX + distanceY * distanceY <= radiusSum * radiusSum;
        }
        public bool Contains(Circle circle)
        {
            if (circle.Radius > Radius)
                return false;
            float distanceX = Center.X - circle.Center.X;
            float distanceY = Center.Y - circle.Center.Y;
            float radiusD = Radius - circle.Radius;
            return distanceX * distanceX + distanceY * distanceY <= radiusD * radiusD;
        }
    }

Note that method Circle.Intersects() returns true even if one circle is within another (treats them as "filled" circles).

Solution 4

If the distance between the centers of two circles is at most the sum of their radii, but at least the absolute value of the difference between the radii, then the circles themselves intersect at some point.

The "at least the difference" part applies if you care only about the circles themselves, and not their inner areas. If you care whether the circles or the areas they enclose share any points -- that is, if one circle totally inside the other counts as "intersecting" to you -- then you can drop the "at least the difference" check.

View more solutions

Comments

[parapura rajkumar]

@dashlinkenlight... I think the OP is looking for a 1 to many intersection

[Sergey Kalinichenko]

@parapurarajkumar A pair of nested loops and a check for i != j should easily deal with that, right?

[Tomas]

@parapurarajkumar - this is not true if you define circle as an area. That's only true if you think of a circle as a circumpherence only

[Tomas]

you should add that this algorithm must be O(N) and no faster algorithm is possible. So it is fairly easy.

[Bernhard Barker]

Rather than just providing a link, it would be preferable to include the essential parts of the answer here, and just provide the link for additional reference. If you're not up to this task, you should consider simply leaving a comment on the question instead of posting an answer. But since this is (presumably) really just an implementation of the accepted answer, and the question makes no mention of Java, I don't find this all that useful.

[Jeroen Vannevel]

I fixed your post, what you did was not according to the standards we impose upon ourselves. I strongly encourage you to add some form of code markup to your website (I'm assuming it's yours) so it's actually readable. Not only that but also make sure nothing fancy is going on with the font: I had to replace all the minus signs and the triple dots because they simply weren't valid characters in Eclipse. Read through the links provided by Dukeling to avoid this in future posts.

[John Conner]

Also I want to thank lorenzo-s for providing me with the link to this page.

[Michael]

That is perfectly fine for 2 given circles, but applying this to all pairs of circles in straightforward manner would lead to O(n^2) algorithm. One should first filter out pair that cannot possibly intersect. IMO the preferred way is to consider bounding boxes of the circles, build a quadtree, and then check for intersections only the circles that have possibly intersecting bounding boxes. That would lead to an algorithm with O(n*log(n)) average case complexity.

[Nick Zalutskiy]

Neat Math.hypot

[Stéphane]

Should this be < or <= ? As in ... y0-y1) <= (r0 + r1) ?

[Cornul11]

@parapurarajkumar, there's no need for that condition, you simply make two nested loops with the first one starting from 0, up to the length of the whole array minus one, and the second one starting from the actual index of the first loop plus one until the length of the array.

[xaphod]

Does this work when CGPoint contains negative values, or, when the radius is so large that a circle's "left" side is in the negative value of its axis? I don't think it does.

[nbro]

Would it be possible to elaborate the complete solution to the actual problem, i.e. include the loops, etc.?

[Craigo]

@Stéphane Technically, < if you don't care about the edge intersection, <= if you do. However, practically, it's unlikely to make a difference, as Math.hypot is unlikely to be able to give you an exact value.