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?
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.
Assuming filled circle intersection (ie: One circle inside another is an intersection).
Where:
Code:
boolean intersects = Math.hypot(x0-x1, y0-y1) <= (r0 + r1);
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).
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.
I tried the formula given here that is a supposed answer and everyone voted way up although it's seriously flawed. I wrote a program in JavaFX to allow the user to test whether two circles intersect by changing each circles centerX, centerY, and Radius values and this formula absolutely does not work except one way...I can't figure out why but when I move circle 2 near circle 1 it works but when I move circle 1 to the other side near circle 2 it doesn't work.....????? that's a bit odd...figured the formula needed to be tested the opposite way as well so tried that and it doesn't work
if (Math.abs(circle1Radius - circle2Radius) <=
Math.sqrt(Math.pow((circle1X - circle2X), 2)
+ Math.pow((circle1Y - circle2Y), 2)) &&
Math.sqrt(Math.pow((circle1X - circle2X), 2)
+ Math.pow((circle1X - circle2Y), 2)) <=
(circle1Radius + circle2Radius)} {
return true;
} else {
return false;
}
This works:
// dx and dy are the vertical and horizontal distances
double dx = circle2X - circle1X;
double dy = circle2Y - circle1Y;
// Determine the straight-line distance between centers.
double d = Math.sqrt((dy * dy) + (dx * dx));
// Check Intersections
if (d > (circle1Radius + circle2Radius)) {
// No Solution. Circles do not intersect
return false;
} else if (d < Math.abs(circle1Radius - circle2Radius)) {
// No Solution. one circle is contained in the other
return false;
} else {
return true;
}
Go here for the formula Intersection of two circles
The formula used is not my formula all credit goes to Paul Bourke(April 1997)
First calculate the distance d between the center of the circles. d = ||P1 - P0||.
If d > r0 + r1 then there are no solutions, the circles are separate.
If d < |r0 - r1| then there are no solutions because one circle is contained within the other.
If d = 0 and r0 = r1 then the circles are coincident and there are an infinite number of solutions.
Considering the two triangles P0P2P3 and P1P2P3 we can write
a2 + h2 = r02 and b2 + h2 = r12
Using d = a + b we can solve for a,
a = (r02 - r12 + d2 ) / (2 d)
It can be readily shown that this reduces to r0 when the two circles touch at one point, ie: d = r0 + r1
Solve for h by substituting a into the first equation, h2 = r02 - a2
So
P2 = P0 + a ( P1 - P0 ) / d
And finally, P3 = (x3,y3) in terms of P0 = (x0,y0), P1 = (x1,y1) and P2 = (x2,y2), is
x3 = x2 +- h ( y1 - y0 ) / d
y3 = y2 -+ h ( x1 - x0 ) / d
Swift 4 solution:
struct Circle {
let radius: CGFloat
let position: CGPoint
}
func circlesIntersect(circleA: Circle, circleB: Circle) -> Bool {
let Δr² = pow(circleA.radius - circleB.radius, 2)
let Δx² = pow(circleA.position.x - circleB.position.x, 2)
let Δy² = pow(circleA.position.y - circleB.position.y, 2)
let ΣΔx²Δy² = Δx² + Δy²
let Σr² = pow(circleA.radius + circleB.radius, 2)
return Δr² <= ΣΔx²Δy² && ΣΔx²Δy² <= Σr²
}
This solution in Java used the mathematical expresion which was described above:
/**
*
* @param values
* { x0, y0, r0, x1, y1, r1 }
* @return true if circles is intersected
*
* Check if circle is intersect to another circle
*/
public static boolean isCircleIntersect(double... values) {
/*
* check using mathematical relation: ABS(R0-R1) <=
* SQRT((x0-x1)^2+(y0-y1)^2) <= (R0+R1)
*/
if (values.length == 6) {
/* get values from first circle */
double x0 = values[0];
double y0 = values[1];
double r0 = values[2];
/* get values from second circle */
double x1 = values[3];
double y1 = values[4];
double r1 = values[5];
/* returun result */
return (Math.abs(r0 - r1) <= Math.sqrt(Math.pow((x0 - x1), 2)
+ Math.pow((y0 - y1), 2)))
&& (Math.sqrt(Math.pow((x0 - x1), 2)
+ Math.pow((y0 - y1), 2)) <= (r0 + r1));
} else {
/* return default result */
return false;
}
}
