Interseção círculo & linha

Dadas as coordenadas do centro de um círculo, seu raio e a equação de uma linha, você deve encontrar os pontos de interseção.

Solução

Em vez de resolver o sistema de duas equações, abordaremos o problema geometricamente. Dessa forma, obtemos uma solução mais precisa do ponto de vista da estabilidade numérica.

Assumimos sem perda de generalidade que o círculo está centrado na origem. Caso contrário, o translocaremos para lá e corrigimos a constante $C$ na equação da linha. Portanto, temos um círculo centrado em $(0,0)$ de raio $r$ e uma linha com equação $Ax+By+C=0$.

Vamos começar por encontrar o ponto na linha mais próximo da origem $(x_0, y_0)$. Primeiro, tem que estar a uma distância

$$ d_0 = \frac{|C|}{\sqrt{A^2+B^2}} $$

Segundo, como o vetor $(A, B)$ é perpendicular à linha, as coordenadas do ponto devem ser proporcionais às coordenadas desse vetor. Como sabemos a distância do ponto até a origem, só precisamos "escalar"(escalar um vetor geométrico significa manter sua orientação igual, mas alterar seu comprimento por um fator de escala. É como mudar a escala de uma imagem; os objetos se expandem ou encolhem, mas as direções permanecem as mesmas) o vetor $(A, B)$ para esse comprimento, e então obteremos:

$$ x_0 = - \frac{AC}{A^2 + B^2} $$ $$ y_0 = - \frac{BC}{A^2 + B^2} $$

Os sinais de menos não são óbvios, mas podem ser facilmente verificados substituindo $x_0$ e $y_0$ na equação da linha.

Nesse estágio, podemos determinar o número de pontos de interseção e até encontrar a solução quando houver um ou zero pontos. De fato, se a distância de $(x_0, y_0)$ à origem $d_0$ for maior que o raio $r$, a resposta será zero pontos de interseção. Se $d_0=r$, a resposta será um ponto $(x_0, y_0)$. Se $d_0<r$, existem dois pontos de interseção, e agora temos que encontrar suas coordenadas.

Portanto, sabemos que o ponto $(x_0, y_0)$ está dentro do círculo. Os dois pontos de interseção, $(a_x, a_y)$ e $(b_x, b_y)$, devem pertencer à linha $Ax+By+C=0$ e devem estar à mesma distância $d$ de $(x_0, y_0)$, e é possível encontrar essa distância:

$$ d = \sqrt{r^2 - \frac{C^2}{A^2 + B^2}} $$

Observe que o vetor $(-B, A)$ é colinear à linha e, portanto, podemos encontrar os pontos em questão adicionando e subtraindo o vetor $(-B,A)$, dimensionado/escalado para o comprimento $d$, para o ponto $(x_0, y_0)$.

Finalmente, as equações dos dois pontos de interseção são:

$$ m = \sqrt{\frac{d^2}{A^2 + B^2}} $$ $$ a_x = x_0 + B \cdot m, a_y = y_0 - A \cdot m $$ $$ b_x = x_0 - B \cdot m, b_y = y_0 + A \cdot m $$

Se tivéssemos resolvido o sistema original de equações usando métodos algébricos, provavelmente obteríamos uma resposta de uma forma diferente com um erro maior. O método geométrico descrito aqui é mais "gráfico" e mais preciso.

Implementação

Conforme indicado no início, assumimos que o círculo está centrado na origem e, portanto, a entrada no programa é o raio $r$ do círculo e os parâmetros $A$, $B$ e $C$ da equação da linha.

double r, a, b, c; // input
double x0 = -a*c/(a*a+b*b), y0 = -b*c/(a*a+b*b);
if (c*c > r*r*(a*a+b*b)+EPS)
    puts ("sem pontos");
else if (abs (c*c - r*r*(a*a+b*b)) < EPS) {
    puts ("1 ponto");
    cout << x0 << ' ' << y0 << '\n';
}
else {
    double d = r*r - c*c/(a*a+b*b);
    double mult = sqrt (d / (a*a+b*b));
    double ax, ay, bx, by;
    ax = x0 + b * mult;
    bx = x0 - b * mult;
    ay = y0 - a * mult;
    by = y0 + a * mult;
    puts ("2 pontos");
    cout << ax << ' ' << ay << '\n' << bx << ' ' << by << '\n';
}

Problemas