Pontos de interseção círculo-círculo

Como faço para calcular os pontos de intersecção de dois círculos. Eu esperaria que houvesse dois, um ou nenhum ponto de intersecção em todos os casos.

Eu tenho as coordenadas xey do ponto central e o raio de cada círculo.

Uma resposta em python seria preferida, mas qualquer algoritmo de trabalho seria aceitável.

Intersecção de dois círculos

Escrito por Paul Bourke

A nota a seguir descreve como localizar o (s) ponto (s) de interseção entre dois círculos em um plano, a seguinte notação é usada. O objective é encontrar os dois pontos P 3 = (x 3 , y 3 ), se existirem.

Intersecção de 2 círculos

Primeiro calcule a distância d entre o centro dos círculos. d = || P 1 – P 0 ||.

  • Se d> r 0 + r 1 então não há soluções, os círculos são separados.
  • Se d <| r 0 – r 1 | então não há soluções porque um círculo está contido no outro.
  • Se d = 0 e r 0 = r 1, então os círculos são coincidentes e há um número infinito de soluções.

Considerando os dois triângulos P 0 P 2 P 3 e P 1 P 2 P 3 podemos escrever

a 2 + h 2 = r 0 2 e b 2 + h 2 = r 1 2

Usando d = a + b podemos resolver por um,

a = (r 0 2 – r 1 2 + d 2 ) / (2 d)

Pode ser prontamente mostrado que isto reduz para r 0 quando os dois círculos tocam em um ponto, ie: d = r 0 + r 1

Resolva para h substituindo a na primeira equação, h 2 = r 0 2 – a 2

assim

P 2 = P 0 + a (P 1 – P 0 ) / d

E finalmente, P 3 = (x 3 , y 3 ) em termos de P 0 = (x 0 , y 0 ), P 1 = (x 1 , y 1 ) e P 2 = (x 2 , y 2 ), é

x 3 = x 2 + – h (y 1 – y 0 ) / d

y 3 = y 2 – + h (x 1 – x 0 ) / d

Fonte: http://paulbourke.net/geometry/circlesphere/

Aqui está minha implementação de C ++ baseada no artigo de Paul Bourke . Ele só funciona se houver duas interseções, caso contrário, provavelmente retornará NaN NAN NAN NAN.

 class Point{ public: float x, y; Point(float px, float py) { x = px; y = py; } Point sub(Point p2) { return Point(x - p2.x, y - p2.y); } Point add(Point p2) { return Point(x + p2.x, y + p2.y); } float distance(Point p2) { return sqrt((x - p2.x)*(x - p2.x) + (y - p2.y)*(y - p2.y)); } Point normal() { float length = sqrt(x*x + y*y); return Point(x/length, y/length); } Point scale(float s) { return Point(x*s, y*s); } }; class Circle { public: float x, y, r, left; Circle(float cx, float cy, float cr) { x = cx; y = cy; r = cr; left = x - r; } pair intersections(Circle c) { Point P0(x, y); Point P1(cx, cy); float d, a, h; d = P0.distance(P1); a = (r*r - cr*cr + d*d)/(2*d); h = sqrt(r*r - a*a); Point P2 = P1.sub(P0).scale(a/d).add(P0); float x3, y3, x4, y4; x3 = P2.x + h*(P1.y - P0.y)/d; y3 = P2.y - h*(P1.x - P0.x)/d; x4 = P2.x - h*(P1.y - P0.y)/d; y4 = P2.y + h*(P1.x - P0.x)/d; return pair(Point(x3, y3), Point(x4, y4)); } }; 

Aqui está uma implementação em Javascript usando vetores. O código está bem documentado, você deve ser capaz de segui-lo. Aqui está a fonte original

Veja a demonstração ao vivo aqui : insira a descrição da imagem aqui

 // Let EPS (epsilon) be a small value var EPS = 0.0000001; // Let a point be a pair: (x, y) function Point(x, y) { this.x = x; this.y = y; } // Define a circle centered at (x,y) with radius r function Circle(x,y,r) { this.x = x; this.y = y; this.r = r; } // Due to double rounding precision the value passed into the Math.acos // function may be outside its domain of [-1, +1] which would return // the value NaN which we do not want. function acossafe(x) { if (x >= +1.0) return 0; if (x <= -1.0) return Math.PI; return Math.acos(x); } // Rotates a point about a fixed point at some angle 'a' function rotatePoint(fp, pt, a) { var x = pt.x - fp.x; var y = pt.y - fp.y; var xRot = x * Math.cos(a) + y * Math.sin(a); var yRot = y * Math.cos(a) - x * Math.sin(a); return new Point(fp.x+xRot,fp.y+yRot); } // Given two circles this method finds the intersection // point(s) of the two circles (if any exists) function circleCircleIntersectionPoints(c1, c2) { var r, R, d, dx, dy, cx, cy, Cx, Cy; if (c1.r < c2.r) { r = c1.r; R = c2.r; cx = c1.x; cy = c1.y; Cx = c2.x; Cy = c2.y; } else { r = c2.r; R = c1.r; Cx = c1.x; Cy = c1.y; cx = c2.x; cy = c2.y; } // Compute the vector  dx = cx - Cx; dy = cy - Cy; // Find the distance between two points. d = Math.sqrt( dx*dx + dy*dy ); // There are an infinite number of solutions // Seems appropriate to also return null if (d < EPS && Math.abs(Rr) < EPS) return []; // No intersection (circles centered at the // same place with different size) else if (d < EPS) return []; var x = (dx / d) * R + Cx; var y = (dy / d) * R + Cy; var P = new Point(x, y); // Single intersection (kissing circles) if (Math.abs((R+r)-d) < EPS || Math.abs(R-(r+d)) < EPS) return [P]; // No intersection. Either the small circle contained within // big circle or circles are simply disjoint. if ( (d+r) < R || (R+r < d) ) return []; var C = new Point(Cx, Cy); var angle = acossafe((r*rd*dR*R)/(-2.0*d*R)); var pt1 = rotatePoint(C, P, +angle); var pt2 = rotatePoint(C, P, -angle); return [pt1, pt2]; } 

Por que não usar apenas 7 linhas da sua linguagem procedural favorita (ou calculadora programável!) Como abaixo.

Assumindo que você receba P0 coords (x0, y0), P1 coords (x1, y1), r0 e r1 e você deseja encontrar as coordenadas P3 (x3, y3):

 d=sqr((x1-x0)^2 + (y1-y0)^2) a=(r0^2-r1^2+d^2)/(2*d) h=sqr(r0^2-a^2) x2=x0+a*(x1-x0)/d y2=y0+a*(y1-y0)/d x3=x2+h*(y1-y0)/d // also x3=x2-h*(y1-y0)/d y3=y2-h*(x1-x0)/d // also y3=y2+h*(x1-x0)/d 

Tente isso;

  def ri(cr1,cr2,cp1,cp2): int1=[] int2=[] ori=0 if cp1[0]cp2[1]: ori+=2 elif cp1[0]>cp2[0] and cp1[1]!=cp2[1]: p1=cp2 p2=cp1 r1=cr2 r2=cr1 if p1[1]p2[1]: ori+=2 elif cp1[0]==cp2[0]: ori+=4 if cp1[1]>cp2[1]: p1=cp1 p2=cp2 r1=cr1 r2=cr2 elif cp1[1]cp2[0]: p1=cp2 p2=cp1 r1=cr2 r2=cr1 elif cp1[0]