Come posso rilevare le intersezioni tra un cerchio e qualsiasi altro cerchio nello stesso piano?

Sto cercando un algoritmo per rilevare se un cerchio si interseca con qualsiasi altro cerchio nello stesso piano (dato che ci può essere più di un cerchio in un piano).

Un metodo che ho trovato è quello di fare il test dell’asse di separazione. Dice:

Due oggetti non si intersecano se è ansible trovare una linea che separa i due oggetti, cioè una linea in modo tale che tutti gli oggetti oi punti di un object si trovino su lati diversi della linea.

Tuttavia, non so come applicare questo metodo al mio caso.

Qualcuno può aiutarmi?

Due cerchi si intersecano se, e solo se, la distanza tra i loro centri è compresa tra la sum e la differenza dei loro raggi. Dati due cerchi (x0, y0, R0) e (x1, y1, R1) , la formula è la seguente:

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

La quadratura di entrambi i lati ti consente di evitare il SQRT lento e di rimanere con i valori integer se i tuoi input sono interi:

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

Poiché è necessario solo un test sì / no, questo controllo è più veloce del calcolo dei punti di intersezione esatti.

La soluzione di cui sopra dovrebbe funzionare anche per il caso "un cerchio dentro l'altro".

Supponendo l’intersezione del cerchio pieno (cioè: un cerchio all’interno di un altro è un’intersezione).

Dove:

  • x0, y0, r0 = centro e raggio del cerchio 0.
  • x1, y1, r1 = centro e raggio del cerchio 1.

Codice:

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

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

Se la distanza tra i centri di due cerchi è al massimo la sum dei loro raggi, ma almeno il valore assoluto della differenza tra i raggi, allora i cerchi stessi si intersecano in qualche punto.

La parte “almeno la differenza” si applica se ci si preoccupa solo dei cerchi stessi, e non delle loro aree interne. Se ti interessa se i cerchi o le aree che racchiudono condividono tutti i punti – cioè, se un cerchio totalmente dentro l’altro conta come “intersecanti” per te – allora puoi lasciare il controllo “almeno la differenza”.

Ho provato la formula qui fornita che è una risposta presunta e tutti hanno votato fino a quando è seriamente imperfetto. Ho scritto un programma in JavaFX per consentire all’utente di verificare se due cerchi si intersecano modificando i valori di ogni centroX di cerchi, centroY e Radius e questa formula assolutamente non funziona tranne un modo … Non riesco a capire perché, ma quando I muovi il cerchio 2 vicino al cerchio 1 funziona, ma quando sposto il cerchio 1 sull’altro lato vicino al cerchio 2 non funziona ….. ????? è un po ‘strano … figurava che la formula doveva essere testata anche in modo opposto, quindi l’ho provata e non funziona

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

Questo funziona:

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

Vai qui per la formula Intersezione di due cerchi

La formula usata non è la mia formula, tutto il merito va a Paul Bourke (aprile 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 

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

Questa soluzione in Java ha usato l’espressione matematica che è stata descritta sopra:

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