Encontrar las tangentes comunes a dos círculos

Se dan dos círculos. Se requiere encontrar todas sus tangentes comunes, es decir, todas las rectas que tocan ambos círculos a la vez.

El algoritmo descrito también funcionará en el caso en que uno (o ambos) círculos degeneren en puntos. Así, este algoritmo también se puede usar para encontrar tangentes a un círculo que pasan por un punto dado.

El número de tangentes comunes

El número de tangentes comunes a dos círculos puede ser 0,1,2,3,4 e infinito. Véanse las imágenes para los distintos casos.

Distintos casos de tangentes comunes a dos círculos

Aquí no consideraremos los casos degenerados, es decir, cuando los círculos coinciden (en este caso tienen infinitas tangentes comunes), o un círculo yace dentro del otro (en este caso no tienen tangentes comunes, o si los círculos son tangentes, hay una tangente común).

En la mayoría de los casos, dos círculos tienen cuatro tangentes comunes.

Si los círculos son tangentes, entonces tendrán tres tangentes comunes, pero esto se puede entender como un caso degenerado: como si las dos tangentes coincidieran.

Además, el algoritmo descrito a continuación funcionará en el caso en que uno o ambos círculos tengan radio cero: en este caso habrá, respectivamente, dos o una tangente común.

Resumiendo, siempre buscaremos cuatro tangentes para todos los casos excepto el de infinitas tangentes (el caso de infinitas tangentes hay que manejarlo por separado y no se discute aquí). En los casos degenerados, algunas de las tangentes coincidirán, pero no obstante estos casos también encajarán en el panorama general.

Algoritmo

Por simplicidad del algoritmo, asumiremos, sin pérdida de generalidad, que el centro del primer círculo tiene coordenadas $(0, 0)$ . (Si no es así, esto se puede lograr simplemente trasladando toda la figura, y después de encontrar una solución, trasladando de vuelta las rectas obtenidas.)

Denotemos $r_1$ y $r_2$ los radios del primer y del segundo círculo, y por $(v_x,v_y)$ las coordenadas del centro del segundo círculo y el punto $v$ distinto del origen. (Nota: no estamos considerando el caso en el que ambos círculos son el mismo).

Para resolver el problema, lo abordamos de forma puramente algebraica. Necesitamos encontrar todas las rectas de la forma $ax + by + c = 0$ que yazcan a distancia $r_1$ del origen de coordenadas, y a distancia $r_2$ de un punto $v$ . Además, imponemos la condición de normalización de la recta: la suma de los cuadrados de los coeficientes debe ser igual a uno (esto es necesario, de lo contrario la misma recta correspondería a infinitas representaciones de la forma $ax + by + c = 0$ ). En total obtenemos el siguiente sistema de ecuaciones para los $a, b, c$ buscados:

$\begin{aligned} a^{2} + b^{2} & = 1 \\ ∣ a \cdot 0 + b \cdot 0 + c ∣ & = r_{1} \\ ∣ a \cdot v_{x} + b \cdot v_{y} + c ∣ & = r_{2} \end{aligned}$

Para deshacernos del valor absoluto, nótese que solo hay cuatro formas de abrir el valor absoluto en este sistema. Todos estos métodos se pueden considerar por el caso general, si entendemos la apertura del valor absoluto como el hecho de que el coeficiente del lado derecho puede multiplicarse por -1. En otras palabras, pasamos a este sistema:

$\begin{aligned} a^{2} + b^{2} & = 1 \\ c & = \pm r_{1} \\ a \cdot v_{x} + b \cdot v_{y} + c & = \pm r_{2} \end{aligned}$

Introduciendo la notación $d_1 = \pm r_1$ y $d_2 = \pm r_2$ , llegamos a la conclusión de que el sistema debe tener cuatro soluciones:

$\begin{aligned} a^{2} + b^{2} & = 1 \\ c & = d_{1} \\ a \cdot v_{x} + b \cdot v_{y} + c & = d_{2} \end{aligned}$

La solución de este sistema se reduce a resolver una ecuación cuadrática. Omitiremos todos los cálculos engorrosos y daremos de inmediato una respuesta lista:

$\begin{aligned} a & = \frac{(d_{2} - d_{1}) v_{x} \pm v_{y} \sqrt{v_{x}^{2} + v_{y}^{2} - (d_{2} - d_{1})^{2}}}{v_{x}^{2} + v_{y}^{2}} \\ b & = \frac{(d_{2} - d_{1}) v_{y} \pm v_{x} \sqrt{v_{x}^{2} + v_{y}^{2} - (d_{2} - d_{1})^{2}}}{v_{x}^{2} + v_{y}^{2}} \\ c & = d_{1} \end{aligned}$

En total obtuvimos ocho soluciones en lugar de cuatro. Sin embargo, es fácil entender de dónde surgen las soluciones superfluas: de hecho, en el último sistema basta tomar solo una solución (por ejemplo, la primera). De hecho, el significado geométrico de tomar $\pm r_1$ y $\pm r_2$ es claro: en realidad estamos recorriendo de qué lado de cada círculo está la recta. Por tanto, los dos métodos que aparecen al resolver el último sistema son redundantes: basta elegir una de las dos soluciones (solo que, por supuesto, en los cuatro casos hay que elegir la misma familia de soluciones).

Lo último que aún no hemos considerado es cómo trasladar las rectas en el caso en que el primer círculo no estaba originalmente en el origen. Sin embargo, aquí todo es simple: de la linealidad de la ecuación de una recta se sigue que el valor $a \cdot x_0 + b \cdot y_0$ (donde $x_0$ e $y_0$ son las coordenadas del centro original del primer círculo) hay que restarlo del coeficiente $c$ .

Implementación

Primero describimos todas las estructuras de datos necesarias y otras definiciones 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;
}

Luego la solución misma se puede escribir así (donde la función principal a llamar es la segunda, y la primera función es 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;
}

Problemas

TIMUS 1163 Chapaev