6 votos

¿Cómo probar si un punto está dentro del casco convexo de dos círculos?

Después de mi pregunta anterior, me pregunto cómo puedo determinar si un punto está dentro del casco convexo de los dos círculos (un valor booleano). No hay ningún problema, prueba de si el punto está en cualquiera de los dos círculos, pero también puede ser "entre" ellos y no sé cómo probar que.

Ver Wolfram MathWorld del artículo en Círculo-Círculo Tangeants, parece que inecuaciones que comprueba si el punto está en el lado interno de los dos círculo externo tangeants que hacer el truco, pero me temo que mis habilidades de resolución están demasiado lejos para ser capaz de convertir el es tangente ecuaciones en una instalación de la desigualdad.

Estoy definiendo el casco convexo de dos círculos con ambos centros y los radios.

8voto

PhilPursglove Puntos 257

Usted puede calcular los cuatro puntos de tangenciaprimero utilice el algoritmo de punto en Polígono para determinar si el punto está dentro del cuadrilatero (esto es asumiendo que tienes un problema relacionado con programación)

De lo contrario, una vez que ha encontrado los cuatro puntos de tangencia, puede formar cuatro líneas y obtener cuatro desigualdades simultáneas.

1voto

Jason Sparks Puntos 948

La solución a este problema es, de hecho, para comprobar si el punto está en uno de los círculos o en el trapecio isósceles determinado por los puntos eran círculos de contacto de la tangente líneas. Sin embargo, sin el cuidado de las ecuaciones poco lioso.

Vamos a empezar con un círculo en (x1', y1') de radio r1', un círculo en (x2', y2') con radio r2', y un punto (x', y') a prueba. Podemos suponer que la r1' es, al menos, r2'. Cambiando seguido por la rotación de la descamación esto puede ser transformado en un simple ejemplo: un círculo en (0,0) de radio r1, círculo (1,0) de radio r2, y un punto (x,y) para probar. Tenemos: r1=r1'/D, r2=r2'/D,

$x=((y'-y'_1)\sin\alpha+(x'-x'_1)\cos\alpha)/D$

$y=((y'-y'_1)\sin\alpha-(x'-x'_1)\cos\alpha)/D$

donde

$D^2=(x'_1-x'_2)^2+(y'_1-y'_2)^2$

y $\alpha$ es el ángulo donde (x2'x1',y2'-y1') mentiras. (En C, hay una función atan2 que toma las dos coordenadas de un punto y da el ángulo. En matemáticas, atan realmente no distinguir entre los puntos simétricos wrt (0,0).)

  1. Si el punto está en uno de los círculos de decir que SÍ, de lo contrario continúe.
  2. Si r1=r2, a continuación, volver (0 < x < 1 y |y| < r1), de lo contrario continúe. (En este punto la diferencia entre los radios Dr=r1-r2 es estrictamente entre 0 y 1.)
  3. Si x < r1 Dr, decir que NO.
  4. Si x > 1 + r2 Dr, decir que NO.
  5. Si $x\Delta r + |y|\sqrt{1-{\Delta r}^2}>r_1$, dicen que NO.
  6. Decir que SÍ.

Sólo hay una cosa que he usado, realmente, es decir, que ciertos triángulos son semejantes. Dibujar la tangente que toca los dos círculos 'de arriba'. Digamos que la intersección con el círculo grande en Una=(x1,y1), el pequeño círculo en B=(x2,y2), y el eje horizontal en C=(d,0). También vamos a escribir D=(0,0) y E=(x1,0) y F=(1,0) y G=(x2,0). Los triángulos semejantes son ADC, AED, BFC, y BGD. Desde ADC similar a BFC encontrar d = r1/Dr. De ADC similar a la AED usted encontrar x1 = r1 Dr y de BFD similar a BGD encontrar x2 - 1 = r2 Dr.

Para comprobar que un punto está en el lado derecho de una línea de escribir su ecuación ax+by+c=0 y reemplazar la igualdad por la desigualdad. (Es bueno recordar que el vector $(a,b)^T$ es perpendicular a la línea y que la ecuación se puede interpretar como la definición de todos los vectores/puntos cuya escalar/producto escalar de un vector fijo $(a,b)^T$ da la constante c.)

Déjeme saber si me equivocaba de nuevo :P


Esta es la respuesta anterior, lo cual es incorrecto, como se señalaba en el primer comentario abajo. Se inicia con las mismas transformaciones (sin dar más detalles), pero luego se utiliza una cierta línea que claramente no es tangente a los círculos.

Dicen que el primer círculo tiene centro en (0,0) (si no, el cambio de la figura) con un radio de r_1, y el segundo a (1,0) (si no, rotar la figura, y la escala) con un radio de r_2. Si el punto (x,y) y no está en uno de los dos círculos, entonces x debe estar entre 0 y 1 y |y| se debe en la mayoría de los r_1+(r_2-r_1)x.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X