¿Cómo puedo detectar intersecciones entre un círculo y cualquier otro círculo en el mismo plano?

Estoy buscando un algoritmo para detectar si un círculo se cruza con cualquier otro círculo en el mismo plano (dado que puede haber más de un círculo en un avión).

Un método que he encontrado es hacer la prueba del eje de separación. Dice:

Dos objetos no se cruzan si puede encontrar una línea que separe los dos objetos, es decir, una línea tal que todos los objetos o puntos de un objeto estén en lados diferentes de la línea.

Sin embargo, no sé cómo aplicar este método a mi caso.

Alguien puede ayudarme?

Dos círculos se cruzan si, y solo si, la distancia entre sus centros está entre la sum y la diferencia de sus radios. Dado dos círculos (x0, y0, R0) y (x1, y1, R1) , la fórmula es la siguiente:

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

Al cuadrar ambos lados te permite evitar el SQRT lento y quedarte con los enteros si tus entradas son enteros:

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

Como solo necesita una prueba de sí / no, esta comprobación es más rápida que calcular los puntos de intersección exactos.

La solución anterior debería funcionar incluso para el caso "un círculo dentro del otro".

Suponiendo intersección de círculo lleno (es decir: un círculo dentro de otro es una intersección).

Dónde:

  • x0, y0, r0 = Centro y radio del círculo 0.
  • x1, y1, r1 = Centro y radio del círculo 1.

Código:

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

Solución XNA / C #

  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; } } 

Si la distancia entre los centros de dos círculos es como máximo la sum de sus radios, pero al menos el valor absoluto de la diferencia entre los radios, entonces los propios círculos se cruzan en algún punto.

La parte “al menos la diferencia” se aplica si solo se preocupan por los círculos mismos y no por sus áreas internas. Si te importa si los círculos o las áreas que encierran comparten algún punto, es decir, si un círculo totalmente dentro del otro cuenta como “intersecante” contigo, entonces puedes descartar la marca “al menos la diferencia”.

Intenté con la fórmula que se da aquí, que es una supuesta respuesta y todos votaron a la alza, aunque tiene serias fallas. Escribí un progtwig en JavaFX para permitir al usuario probar si se cruzan dos círculos cambiando los valores de cada centro de círculosX, centerY y Radio, y esta fórmula no funciona, excepto en una dirección … No puedo entender por qué, pero cuando mover el círculo 2 cerca del círculo 1 funciona, pero cuando muevo el círculo 1 al otro lado cerca del círculo 2, no funciona ….. ????? eso es un poco extraño … pensé que la fórmula necesitaba ser probada de la manera opuesta, así que lo intenté y no funciona

 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; } 

Esto funciona:

  // 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; } 

Vaya aquí para la fórmula Intersección de dos círculos

La fórmula utilizada no es mi fórmula, todo el mérito recae en Paul Bourke (abril de 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 

Solución Swift 4 :

 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² } 

Esta solución en Java utilizó la expresión matemática que se describió anteriormente:

 /** * * @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; } }