Encontrando tangentes comuns em dois círculos

Dados dois círculos. É necessário encontrar todas as tangentes comuns, isto é, todas as linhas que tocam os dois círculos simultaneamente.

O algoritmo descrito também funcionará no caso em que um (ou ambos) círculos degeneram(ou seja, são validados apenas como pontos no plano) em pontos. Assim, esse algoritmo também pode ser usado para encontrar tangentes a um círculo que passa por um determinado ponto.

O número de tangentes comuns

O número de tangentes comuns a dois círculos pode ser 0,1,2,3,4... e infinito. Olhe as imagens para diferentes casos.

"Different cases of tangents common to two circles"

Aqui, não consideraremos casos degenerados , ou seja, quando os círculos coincidem (neste caso, eles têm infinitas tangentes comuns, última imagem), ou um círculo fica dentro do outro (nesse caso, eles não têm tangentes comuns, primeira imagem), ou se os círculos são tangentes, existe uma tangente comum, segunda imagem).

Na maioria dos casos, dois círculos têm quatro tangentes comuns.

Se os círculos forem tangentes , eles terão três tangentes comuns, mas isso pode ser entendido como um caso degenerado: como se as duas tangentes coincidissem.

Além disso, o algoritmo descrito abaixo funcionará no caso de um ou ambos os círculos terem raio zero: nesse caso, haverá, respectivamente, duas ou uma tangente comum.

Resumindo, sempre procuraremos quatro tangentes para todos os casos, exceto o caso de tangentes infinitas (o caso de tangentes infinitas precisa ser tratado separadamente e não é discutido aqui). Em casos degenerados, algumas das tangentes coincidem, mas, no entanto, esses casos também se encaixam no quadro geral.

Algoritmo

Por uma questão de simplicidade do algoritmo, assumiremos, sem perder a generalidade, que o centro do primeiro círculo tem coordenadas $(0,0)$. (Se não for esse o caso, isso pode ser alcançado simplesmente mudando a imagem toda e, depois de encontrar uma solução, mudando as linhas retas obtidas de volta).

Denote $r_1$ e $r_2$ os raios do primeiro e segundo círculos e por $(v_x,v_y)$ as coordenadas do centro do segundo círculo e o ponto $v$ diferente da origem. (Observação: não estamos considerando o caso em que os dois círculos são iguais).

Para resolver o problema, abordamos-o puramente algebricamente. Precisamos encontrar todas as linhas da forma $ax + by + c = 0$ que se encontram a uma distância $r_1$ da origem das coordenadas e a uma distância $r_2$ de um ponto $v$. Além disso, impomos a condição de normalização da linha reta: a soma dos quadrados dos coeficientes deve ser igual a um (isso é necessário, caso contrário, a mesma linha reta corresponderá a infinitas representações na forma $ax + by + c = 0$). No total, obtemos esse sistema de equações para os coeficientes $a, b, c$:

$$a^2 + b^2 = 1$$ $$\mid a \cdot 0 + b \cdot 0 + c \mid = r_1$$ $$\mid a \cdot v_x + b \cdot v_y + c \mid = r_2$$

Para se livrar do módulo, observe que existem apenas quatro maneiras de abrir o módulo neste sistema. Todos esses métodos podem ser considerados no caso geral, se entendermos a abertura do módulo como o fato de que o coeficiente do lado direito pode ser multiplicado por -1. Em outras palavras, nos voltamos para este sistema:

$$a^2 + b^2 = 1$$ $$c = \pm r_1$$ $$a \cdot v_x + b \cdot v_y + c = \pm r_2$$

Introduzindo a notação $d_1 = \pm r_1$ and $d_2 = \pm r_2$, chegamos à conclusão de que o sistema deve ter quatro soluções:

$$a^2 + b^2 = 1$$ $$c = d_1$$ $$a \cdot v_x + b \cdot v_y + c = d_2$$

A solução deste sistema é reduzida para resolver uma equação quadrática. Omitiremos todos os cálculos complicados e daremos imediatamente uma resposta pronta(amém, mas não tanto):

$$a = {( d_2 - d_1 ) v_x \pm v_y \sqrt{v_x^2 + v_y^2-(d_2-d_1)^2} \over {v_x^2 + v_y^2} }$$ $$b = {( d_2 - d_1 ) v_y \pm v_x \sqrt{v_x^2 + v_y^2-(d_2-d_1)^2} \over {v_x^2 + v_y^2} }$$ $$c = d_1$$

No total, temos oito soluções em vez de quatro. No entanto, é fácil entender onde surgem as decisões supérfluas: de fato, no último sistema, basta apenas uma solução (por exemplo, a primeira). De fato, o significado geométrico do que tomamos como solução $\pm r_1$ e $\pm r_2$: na verdade, estamos ordenando de que lado de cada círculo há uma linha reta. Portanto, os dois métodos que surgem ao resolver o último sistema são redundantes: basta escolher uma das duas soluções (apenas, é claro, nos quatro casos, você deve escolher a mesma família de soluções).

A última coisa que ainda não consideramos é como mudar a linha reta no caso em que o primeiro círculo não estava originalmente localizado na origem. No entanto, tudo é simples aqui: segue-se da linearidade da equação de uma linha reta que o valor $a \cdot x_0 + b \cdot y_0$ (onde $x_0$ e $y_0$ são as coordenadas do centro original do primeiro círculo) deve ser subtraído do coeficiente $c$.

Implementação

Primeiro, descrevemos todas as estruturas de dados necessárias e outras definições auxiliares:

struct pt {
    double x, y;

    pt operator- (pt p) {
        pt res = { x-p.x, y-p.y };
        return res;
    }
};

struct circle : pt {
    double r;
};

struct line {
    double a, b, c;
};

const double EPS = 1E-9;

double sqr (double a) {
    return a * a;
}

Em seguida, a solução em si pode ser escrita dessa maneira (onde a função principal para a chamada é a segunda; e a primeira função é auxiliar):

void tangents (pt c, double r1, double r2, vector<line> & ans) {
    double r = r2 - r1;
    double z = sqr(c.x) + sqr(c.y);
    double d = z - sqr(r);
    if (d < -EPS)  return;
    d = sqrt (abs (d));
    line l;
    l.a = (c.x * r + c.y * d) / z;
    l.b = (c.y * r - c.x * d) / z;
    l.c = r1;
    ans.push_back (l);
}

vector<line> tangents (circle a, circle b) {
    vector<line> ans;
    for (int i=-1; i<=1; i+=2)
        for (int j=-1; j<=1; j+=2)
            tangents (b-a, a.r*i, b.r*j, ans);
    for (size_t i=0; i<ans.size(); ++i)
        ans[i].c -= ans[i].a * a.x + ans[i].b * a.y;
    return ans;
}