Intersección círculo-recta

Dadas las coordenadas del centro de un círculo y su radio, y la ecuación de una recta, se requiere encontrar los puntos de intersección.

Solución

En lugar de resolver el sistema de dos ecuaciones, abordaremos el problema de forma geométrica. De este modo obtenemos una solución más precisa desde el punto de vista de la estabilidad numérica.

Asumimos sin pérdida de generalidad que el círculo está centrado en el origen. Si no lo está, lo trasladamos allí y corregimos la constante $C$ en la ecuación de la recta. Así tenemos un círculo centrado en $(0,0)$ de radio $r$ y una recta con ecuación $Ax+By+C=0$.

Empecemos por encontrar el punto de la recta más cercano al origen $(x_0, y_0)$. Primero, tiene que estar a una distancia

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

Segundo, como el vector $(A, B)$ es perpendicular a la recta, las coordenadas del punto deben ser proporcionales a las coordenadas de este vector. Como conocemos la distancia del punto al origen, solo hay que escalar el vector $(A, B)$ a esta longitud, y obtendremos:

$$\begin{array}{rllll}& {\displaystyle x_0}& {\displaystyle =-\frac{AC}{A^2+B^2}}& & \\ & {\displaystyle y_0}& {\displaystyle =-\frac{BC}{A^2+B^2}}& & \end{array}$$$$\begin{align} x_0 &= - \frac{AC}{A^2 + B^2} \ y_0 &= - \frac{BC}{A^2 + B^2} \end{align}$$

Los signos menos no son evidentes, pero se pueden verificar fácilmente sustituyendo $x_0$ e $y_0$ en la ecuación de la recta.

En esta etapa podemos determinar el número de puntos de intersección, e incluso encontrar la solución cuando hay uno o cero puntos. En efecto, si la distancia de $(x_0, y_0)$ al origen $d_0$ es mayor que el radio $r$, la respuesta es cero puntos. Si $d_0=r$, la respuesta es un punto $(x_0, y_0)$. Si $d_0<r$, hay dos puntos de intersección, y ahora hay que encontrar sus coordenadas.

Así, sabemos que el punto $(x_0, y_0)$ está dentro del círculo. Los dos puntos de intersección, $(a_x, a_y)$ y $(b_x, b_y)$, deben pertenecer a la recta $Ax+By+C=0$ y deben estar a la misma distancia $d$ de $(x_0, y_0)$, y esta distancia es fácil de encontrar:

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

Nótese que el vector $(-B, A)$ es colineal a la recta, y así podemos encontrar los puntos en cuestión sumando y restando el vector $(-B,A)$, escalado a la longitud $d$, al punto $(x_0, y_0)$.

Finalmente, las ecuaciones de los dos puntos de intersección son:

$$\begin{array}{rllll}& {\displaystyle m}& {\displaystyle =\sqrt{\frac{d^2}{A^2+B^2}}}& & \\ & {\displaystyle a_x}& {\displaystyle =x_0+B\cdot m,a_y=y_0-A\cdot m}& & \\ & {\displaystyle b_x}& {\displaystyle =x_0-B\cdot m,b_y=y_0+A\cdot m}& & \end{array}$$$$\begin{align} m &amp;= \sqrt{\frac{d^2}{A^2 + B^2}} \ a_x &amp;= x_0 + B \cdot m, a_y = y_0 - A \cdot m \ b_x &amp;= x_0 - B \cdot m, b_y = y_0 + A \cdot m \end{align}$$

Si hubiéramos resuelto el sistema original de ecuaciones usando métodos algebraicos, probablemente obtendríamos una respuesta de otra forma con un error mayor. El método geométrico descrito aquí es más gráfico y más preciso.

Implementación

Como se indicó al comienzo, asumimos que el círculo está centrado en el origen, y por tanto la entrada al programa es el radio $r$ del círculo y los parámetros $A$, $B$ y $C$ de la ecuación de la recta.

double r, a, b, c; // dados como entrada
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 ("no points");
else if (abs (c*c - r*r*(a*a+b*b)) < EPS) {
    puts ("1 point");
    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 points");
    cout << ax << ' ' << ay << '\n' << bx << ' ' << by << '\n';
}

Problemas de práctica

• CODECHEF: ANDOOR