¿Cómo saber si un segmento de recta se cruza con una circunferencia?

Question

Dado un segmento de línea, denotado por su $2$ puntos finales $(X_1, Y_1)$ y $(X_2, Y_2)$ y un círculo, denotado por su punto central $(X_c, Y_c)$ y un radio $R$ ¿Cómo puedo saber si el segmento de recta es una tangente o pasa por esta circunferencia? No necesito poder discernir entre tangente o que atraviesa una circunferencia, sólo necesito poder discernir entre que el segmento de línea haga contacto con la circunferencia de alguna manera y que no haya contacto. Si el segmento de línea entra pero no sale del círculo (si el círculo contiene un punto final), eso cumple mis especificaciones para que haga contacto.

En resumen, necesito una función que encuentre si algún punto de un segmento de recta se encuentra en o sobre una circunferencia dada.

EDITAR:

Mi aplicación es que estoy usando el círculo como una proximidad alrededor de un punto. Básicamente estoy probando si un punto está dentro de la distancia R de cualquier punto del segmento de línea. Y debe ser un segmento de línea, no una línea.

Answer 1

Encuentra las intersecciones de la recta que contiene el segmento y la circunferencia. Esto equivale a resolver una ecuación cuadrática. Si no hay intersecciones ( es decir las soluciones de la ecuación correspondiente no son reales), entonces su segmento no interseca el círculo. Ahora bien, si hay son intersecciones, ver si están dentro del segmento o no.

Para ponerlo en práctica, dejemos que $P$ y $Q$ sean los puntos finales de su segmento y $C$ y $r$ sea el centro y el radio de tu círculo. Entonces cada punto de la línea que pasa por $P$ y $Q$ viene dada por la fórmula $$t P + (1-t) Q$$ para exactamente un valor de $t\in\mathbb R$ y los puntos del segmento son precisamente aquellos para los que el correspondiente $t$ está en el intervalo $[0,1]$ .

Ahora el punto correspondiente a $t\in\mathbb R$ está en el círculo si y sólo si $$\langle t P + (1-t) Q - C,t P + (1-t) Q - C\rangle = r^2,$$ donde $\langle\mathord\cdot,\mathord\cdot\rangle$ es el producto interno (punto) habitual de los vectores. Si se resuelve esta ecuación -es fácil, ya que es una ecuación cuadrática para $t$ -, se encuentra el $t$ correspondientes a los puntos de intersección del círculo y la línea, y si al menos uno de ellos $t$ pertenecen al intervalo $[0,1]$ entonces el segmento intersecta el círculo.

Más tarde: Intenté tener Mathematica hacer el cálculo por mí. Suponiendo que $C=(0,0)$ y $r=1$ como podemos hasta la traducción y el reescalado, y dejando $P=(p1,p2)$ , $Q=(q1,q2)$ , lo siguiente calcula el $t$ 's:

P = {p1, p2};
Q = {q1, q2};
ts = t /. Solve[Norm[t P + (1 - t) Q]^2 == 1, t];

Esto hace que la variable ts tenga el valor

$$\left\{\frac{-p_1 q_1-p_2 q_2-\sqrt{p_1^2 \left(-q_2^2\right)-2 p_1 q_1+2 p_2 p_1 q_1 q_2-p_2^2 q_1^2-2 p_2 q_2+p_1^2+p_2^2+q_1^2+q_2^2}+q_1^2+q_2^2}{-2 p_1 q_1-2 p_2 q_2+p_1^2+p_2^2+q_1^2+q_2^2},\frac{-p_1 q_1-p_2 q_2+\sqrt{p_1^2 \left(-q_2^2\right)-2 p_1 q_1+2 p_2 p_1 q_1 q_2-p_2^2 q_1^2-2 p_2 q_2+p_1^2+p_2^2+q_1^2+q_2^2}+q_1^2+q_2^2}{-2 p_1 q_1-2 p_2 q_2+p_1^2+p_2^2+q_1^2+q_2^2}\right\}$$

(Esta era una fórmula enorme, que probablemente no quepa en la ventana de tu navegador...) Si la expresión dentro de las raíces cuadradas es negativa, no hay reales $t$ 's, por lo que la línea (por lo tanto, a fortiori el segmento) y el círculo son disjuntos. Si no es así, ahora tenemos que ver si al menos una de las raíces en $[0,1]$ .

Si ahora digo Mma para decirme cuándo es la primera de las raíces en $[0,1]$ diciendo que calcule

Reduce[0 <= ts[[1]] <= 1, Reals]

funciona durante un tiempo, y obtiene una respuesta enorme, presumiblemente equivalente a la original

0 <= ts[[1]] <= 1

¿Alguien puede dar sentido a la enorme respuesta? (si se pregunta en cambio por la más significativa

Reduce[0 <= ts[[1]] <= 1 || 0 <= ts[[2]] <= 1, t, Reals]

ocurre lo mismo)

PS: Ten en cuenta que no he hecho absolutamente ningún intento de ser rápido o particularmente inteligente con esta idea: es sólo la forma directa de plantear el problema y resolverlo.

Answer 2

Tal vez esto es lo que quiere decir... Dada una línea que pasa por los puntos $(x_1,y_1)$ y $(x_2,y_2)$ y dado un único punto $p$ no necesariamente en la línea Queremos averiguarlo: Si dibujamos un círculo de radio $r$ alrededor de $p$ ¿ese círculo se cruza con la línea?

Si esto es lo que quiere, entonces está buscando el distancia perpendicular del punto a la línea .

Es posible que la derivación en MathWorld no te interese en este momento, teniendo en cuenta que estás familiarizado con tantos símbolos, así que vayamos al grano.

Dado que su línea pasa por los dos puntos $(x_1,y_1)$ y $(x_2,y_2)$ un punto $(a,b)$ no necesariamente en la línea, y algunos radios $r$ alrededor del punto $(a,b)$ para ver si su punto $(a,b)$ está dentro de $r$ de la línea, es necesario comprobar

if $r \geq \\frac{|(x_1 - x_2)(a-x_1) + (y_2 - y_1)(b-y_1)|}{\sqrt{(x_1-x_2)^2 + (y_2-y_1)^2}}$

then $(a,b)$ está dentro de $r$ de la línea (tomada como distancia ortogonal).

EDITAR: No creo que esto funcione si se trabaja sólo con un segmento de línea... Esta solución asume que tu línea se extiende infinitamente en ambas direcciones. (actualización: hay escenarios en los que esto fallaría) Creo que el caso de que el segmento en sí esté más lejos que $r$ puede ser atendida en los casos antes de llegar a la declaración "if" anterior. Debería ser algo parecido a

if $r \leq \sqrt{(x_1 - a)^2 + (y_1 - b)^2}$ or $r \leq \sqrt{(x_2-a)^2 + (y_2 - b)^2}$

then el segmento está demasiado lejos para considerar siquiera la comprobación de la desigualdad más larga anterior. (de nuevo, el anterior if/then es insuficiente... aún estoy pensando)

Edición final: Este enfoque ha sido adaptado y completado de forma mucho más satisfactoria por Isaac . Ofreceré una segundo enfoque que puede ser exactamente lo que Mariano pero intentaré ser breve y sencillo.

Answer 3

Bueno, qué diablos... ya se ha derramado tanta tinta virtual a estas alturas que ¿qué es otro galón, realmente?

( actualización : Esta es precisamente la solución Mariano propuso mucho antes que yo, lo que ocurre es que lo expresé en una notación diferente).

El principio en el que se basa este es que podemos averiguar algebraicamente si el conjunto de coordenadas que definen el perímetro de una circunferencia con centro $(h,k)$ y el radio $r$ contiene cualquier punto del segmento de línea que une los puntos $(x_1,y_1)$ y $(x_2,y_2)$ .

En otras palabras, escribir el conjunto de puntos $(x,y)$ a lo largo del segmento de línea como $$tx_1 + (1-t)x_2 = x$$ $$ty_1 + (1-t)y_2 = y$$

donde $t$ oscila entre $0$ y $1$ inclusive, y escribiendo la ecuación del círculo centrado en $(h,k)$ con radio $r$ como $$(x-h)^2 + (y-k)^2 = r^2,$$

entonces podemos simplemente sustituir nuestras expresiones por $x$ y $y$ en la ecuación del círculo, y luego averiguar si hay al menos una $t \in [0,1] \subset \mathbb{R}$ . Si lo hay, entonces el perímetro del círculo y el segmento de recta comparten al menos un punto.

Como estamos de acuerdo en que ya hemos visto suficiente tinta virtual por hoy, me limitaré a escribir cómo es esa sustitución y luego el cálculo final que hay que hacer.

La sustitución :

$$\left(tx_1 + (1-t)x_2 - h \right)^2 + \left(ty_1 + (1-t)y_2 - k \right)^2 = r^2.$$

(Se trata de una ecuación cuadrática en $t$ , obsérvese que los valores de $x_1,x_2,y_1,y_2,h,k,$ y $r$ son conocidos).

El cálculo : $$At^2 + Bt + C = 0$$ con

$A = x_{1}^{2} - 2x_{1}x_{2} + x_{2}^{2},$
$B = 2x_{1}x_{2} - 2x_{2}^{2} - 2hx_{2} + 2hx_{2},$ y
$C = x_{2}^{2} - 2hx_{2} + h^{2} - r^{2}.$

Resolver para $t$ utilizando la fórmula cuadrática y luego probar si al menos una $t$ es un número real entre $0$ y $1$ , inclusive.

PS: Si he pisado la solución de otro que ya ha sido publicada es porque no he hecho la debida diligencia y verificado todas las soluciones dadas anteriormente. Por favor, hágamelo saber en los comentarios.

Answer 4

Si entiendo bien tu edición, tienes razón $C=(x_c,y_c)$ y el segmento de línea con puntos extremos $P=(x_1,y_1)$ y $Q=(x_2,y_2)$ y quiere saber si $C$ está a una distancia $r$ de cualquier punto del segmento de línea $\overline{PQ}$ .

Trabajar desde Respuesta de Tom Stephens Veamos la línea completa $\overleftrightarrow{PQ}$ que contiene el segmento de línea $\overline{PQ}$ . La distancia entre $C$ y $\overleftrightarrow{PQ}$ es $d=\frac{|(x_1 - x_2)(x_c-x_1) + (y_2 - y_1)(y_c-y_1)|}{\sqrt{(x_1-x_2)^2 + (y_2-y_1)^2}}$ .

(1) Si $d>r$ entonces $C$ está demasiado lejos de $\overleftrightarrow{PQ}$ para estar dentro de $r$ de cualquier punto de $\overline{PQ}$ terminado.

Si $d\le r$ entonces $C$ está lo suficientemente cerca de $\overleftrightarrow{PQ}$ pero puede no estar lo suficientemente cerca de $\overline{PQ}$ . $d$ es la distancia perpendicular de $C$ a $\overleftrightarrow{PQ}$ . Consideremos dos casos: primero, que $C$ y $\overline{PQ}$ están dispuestas de forma que la distancia perpendicular es a un punto de $\overline{PQ}$ segundo, que la distancia perpendicular es a un punto que no está en $\overline{PQ}$ .

(2) En el primer caso, $\angle PQC$ y $\angle QPC$ cada uno tiene medida ≤90°, por lo que el coseno de cada ángulo debe ser no negativo por lo que $\frac{(x_1-x_2)^2-(x_1-x_c)^2+(x_2-x_c)^2+(y_1-y_2)^2-(y_1-y_c)^2+(y_2-y_c)^2}{2\sqrt{((x_1-x_2)^2+(y_1-y_2)^2)((x_2-x_c)^2+(y_2-y_c)^2)}}\ge 0$ y $\frac{(x_1-x_2)^2+(x_1-x_c)^2-(x_2-x_c)^2+(y_1-y_2)^2+(y_1-y_c)^2-(y_2-y_c)^2}{2\sqrt{((x_1-x_2)^2+(y_1-y_2)^2)((x_1-x_c)^2+(y_1-y_c)^2)}}\ge 0$ (de la Ley de los Cosenos). [ editar 2 : Tras una lectura más atenta de respuesta de damiano se me ha ocurrido que son mucho más complicados de lo necesario. Los denominadores no afectan en absoluto al signo y los numeradores son algo más sencillos cuando se expanden, por lo que las dos desigualdades pueden sustituirse por: $x_1x_2-x_1x_c+x_2x_c-x_2^2+y_1y_2-y_1y_c+y_2y_c-y_2^2\ge0$ y $x_1x_2+x_1x_c-x_2x_c-x_1^2+y_1y_2+y_1y_c-y_2y_c-y_1^2\ge0$ . Estos son más claramente equivalentes a los criterios de producto vectorial-punto de Damiano. ] Si ambas desigualdades se cumplen, entonces $d\le r$ es la distancia desde $C$ a $\overline{PQ}$ Así que $C$ está dentro de $r$ de $\overline{PQ}$ .

(3) Si esas dos desigualdades de la Ley de los Cosenos no se cumplen, entonces $d$ no es la distancia de $C$ a cualquier punto de $\overline{PQ}$ por lo que la distancia más corta desde $C$ a cualquier punto de $\overline{PQ}$ es la distancia al más cercano de $P$ y $Q$ : $d'=\min(\sqrt{(x_1-x_c)^2+(y_1-y_c)^2},\sqrt{(x_2-x_c)^2+(y_2-y_c)^2})$ . Si $d'\le r$ entonces $C$ está dentro de $r$ de $\overline{PQ}$ .

editar (añadiendo también los números anteriores) :

Dado Respuesta de Corey Ogburn Pensé que podría ser útil añadir un diagrama y discutir qué partes de mi respuesta original se refieren a qué regiones. Los números que aparecen a continuación se refieren a la parte correspondiente de mi respuesta original.

(1) Si $d>r$ , entonces el punto $C$ está en la región del beige.

(2) $d\le r$ Así que si $\angle PQC$ y $\angle QPC$ cada uno tiene medida ≤90°, entonces $C$ se encuentra en la región púrpura.

(3) $C$ no está en las regiones beige o púrpura, por lo que sólo tenemos que ver si está en las regiones azul o roja (en función de si $C$ está lo suficientemente cerca de los puntos finales del segmento).

Answer 5

Si he entendido bien lo que quieres, necesitas encontrar las condiciones de un segmento de línea para que quede completamente fuera de un círculo; un posible motivo de confusión es que los matemáticos tienden a llamar "círculo" sólo a la frontera unidimensional del "disco" y llaman "disco" a su interior. En esta terminología, creo que se quiere que el segmento quede completamente fuera del disco cerrado; ésta es la pregunta a la que voy a dar respuesta.

Primero, una descripción geométrica de la respuesta. Sea $P$ y $Q$ sean los puntos finales del segmento, y que $C$ sea el centro del círculo y que $r$ sea el radio del círculo $C$ .

1) Descartamos la posibilidad de que al menos uno de los $P$ y $Q$ está contenida dentro del disco cerrado.

2) Si en el triángulo $PQC$ uno de los dos ángulos del segmento $PQ$ no es agudo, entonces moviéndose a lo largo del segmento $PQ$ y lejos del ángulo no agudo la distancia desde el centro $C$ aumenta, por lo que no hay intersección en este caso debido a 1). En caso contrario, los dos ángulos del segmento $PQ$ son agudos, de modo que la distancia mínima entre el centro $C$ y los puntos del segmento $PQ$ se consigue dentro del segmento. En este caso (es decir, cuando los dos ángulos en $PQ$ son agudos), nos aseguramos de que la distancia entre el centro $C$ y la línea que une $P$ y $Q$ es mayor que $r$ . A la vista de 1) y de la discusión anterior, esto implica que no hay contacto entre el segmento y el disco.

Traducción a fórmulas:

1) $dist(P,C)>r$ y $dist(Q,C)>r$ ;

2) si las desigualdades $PC \cdot PQ > 0$ y $QC \cdot QP > 0$ se cumple, entonces también la desigualdad $||PC \times PQ|| > r ||PQ||$ debe cumplirse (en las fórmulas, denotamos por $\cdot$ el producto escalar, por $\times$ el producto cruzado, y por $||-||$ la longitud de un vector).

Ecuaciones explícitas, suponiendo que $C$ es el origen (que siempre se puede conseguir mediante traducciones):

1) $x_P^2+y_P^2 > r^2$ y $x_Q^2+y_Q^2 > r^2$ ;

2) si ambos $x_P^2 + y_P^2 \geq x_P x_Q + y_P y_Q$ y $x_Q^2 + y_Q^2 \geq x_P x_Q + y_P y_Q$ mantener, entonces comprueba que también $(x_Py_Q-x_Qy_P)^2 > r^2 ((x_P-x_Q)^2 + (y_P-y_Q)^2)$ se mantiene.