Cómo detectar si una elipse se cruza (colisiona con) un círculo

Question

Quiero mejorar un sistema de colisión.

Ahora detecto si dos objetos irregulares chocan si colisionan sus rectángulos delimitadores.

Quiero obtener el rectángulo para la elipse correspondiente, mientras que el otro para usar un círculo. Encontré un método para obtener las coordenadas de la elipse, pero tengo un problema cuando trato de detectar si se cruza con el círculo.

¿Conoces un algoritmo para comprobar si un círculo se cruza con una elipse?

Answer 1

Respuesta corta: Resolver exactamente si los dos objetos se cruzan es lo suficientemente complicado como para ser inviable con el propósito de detección de colisión. Discretice su elipse como un polígono de n lados para algunos n (según la precisión que necesite) y realice la detección de colisiones con ese polígono.

Respuesta larga: si insiste en determinar si la elipse lisa y el círculo se cruzan, existen dos enfoques principales. Ambos implican resolver primero el punto más cercano al centro del círculo en la elipse, y luego comparar esa distancia con el radio del círculo.

Método 1: Utilice una parametrización de la elipse. Transforme sus coordenadas para que la elipse se encuentre en el origen, con sus ejes alineados con los ejes x-y. Esto es:

• Centro de elipse: (0,0)
• Centro de círculo: c = (cx, cy)
• Radio del círculo: r
• Radio del eje x-alineado de elipse: a
• Radio del eje de elipse alineado con y: b.

La ecuación de la elipse viene dada por a cos(t), b sin(t). Para encontrar el punto más cercano, queremos minimizar la distancia cuadrada || (a cos t, b sin t) - c ||^2. Como Jean señala, esto es "solo cálculo": tomar una derivada y establecerla igual a 0. A menos que me falta algo, sin embargo, resolver la ecuación resultante (bastante desagradable) para t no es posible analíticamente, y debe ser aproximada usando, por ejemplo Método de Newton. Enchufa el t que encuentras en la ecuación paramétrica para obtener el punto más cercano.

• Pro: La solución numérica está solo en una variable, t.
• Con: Debe ser capaz de escribir una parametrización de la elipse, o transformar sus coordenadas para que pueda.Esto no debería ser demasiado difícil para cualquier representación razonable que tenga de la elipse. Sin embargo, voy a mostrarte un segundo método, que es mucho más general y podría ser útil si tienes que generalizar tu problema a, por ejemplo, 3D.

Método 2: Usa cálculo multidimensional. No es necesario un cambio de coordenadas.

• Centro de círculo: c = (cx, cy)
• Radio de cirlce: r
• elipse es dada por g (x, y) = 0 para una función g. Por ejemplo, según la respuesta de Curd puedes usar g (x, y) = distancia de (x, y) desde el foco 1 + distancia de (x, y) desde el foco 2 - e.

Encontrar el punto de la elipse más cercano al centro del círculo a continuación, puede expresarse como una constreñido problema minimización:

Minimize ||(x,y) - c||^2 subject to g(x,y) = 0

(minimizando la distancia cuadrado es equivalente a minimizar la distancia, y mucho más agradable de tratar ya que es un polinomio cuadrático en x, y).

Para resolver el problema de minimización restringido, presentamos el multiplicador de Lagrange lambda, y resolver el sistema de ecuaciones

2 * [ (x,y) -c ] + lambda * Jg(x,y) = 0 
g(x,y) = 0 

Aquí Jg es el gradiente de g. Este es un sistema de tres ecuaciones (no lineales) en tres incógnitas: x, y y lambda. Podemos resolver este sistema usando el Método de Newton, y el (x, y) que obtenemos es el punto más cercano al centro del círculo.

• Pro: No se parametrización hay que encontrar
• Pro: El método es muy general, y funciona bien siempre que la escritura g es más fácil que encontrar una ecuación paramétrica (como en 3D)
• contra: Requiere una resolución multivariable de Newton, que es muy complicada si no tienes acceso a un paquete de métodos numéricos.

Advertencia: ambos enfoques resolver técnicamente para el punto, que extremizes la distancia hasta el centro del círculo. Por lo tanto, el punto encontrado podría ser el punto más alejado del círculo, y no el más cercano. Para ambos métodos, siembra tu resolución con una buena conjetura inicial (el centro del círculo funciona bien para el Método 2, estás solo para el Método 1) reducirá este peligro.

Posible tercer enfoque?: Puede ser posible resolver directamente las raíces del sistema de dos ecuaciones cuadráticas en dos variables que representan el círculo y la elipse. Si existe una raíz real, los objetos se cruzan. La forma más directa de resolver este sistema, de nuevo usando un algoritmo numérico como el Método de Newton, no ayudará porque la falta de convergencia no implica la inexistencia de una raíz real. Sin embargo, para dos ecuaciones cuadráticas en dos variables, puede existir un método especializado que garantice encontrar raíces reales, si existen. Yo mismo no puedo pensar en una manera de hacerlo, pero es posible que desee investigarlo usted mismo (o ver si alguien en stackoverflow puede elaborarlo.)

Answer 2

encontrar el punto de la elipse más cercano al centro del círculo
y compruebe si la distancia desde este punto es menor que el radio del círculo
si necesita ayuda para hacer esto acaba de comentar, pero es simplemente cálculo

edición: He aquí una caminos hacia la solución, ya que hay algo mal con las cuajadas

dado centro α β en la elipse
y (a falta de recordar el término) x radio a, y radio b la parametrización es
r (Θ) = (ab)/(((BcosΘ)^2 + (asinΘ)^2) ^. 5)
x (Θ) = α + sin (Θ) r (Θ)
y (Θ) = β + cos (Θ) r (Θ)

y luego simplemente tomar el círculo con centro en (φ, ψ) y radio r entonces la distancia d (Θ) = ((φ - y (Θ))^2 + (ψ - y (Θ)) 2) ^. 5

el mínimo de esta distancia es cuando d '(Θ) = 0 (' para la derivada)

d '(Θ) = 1/d (Θ) * (-φx' (Θ) '+ x (Θ) x' (Θ) '-' (') + y (Θ) y '(Θ))
==>
x' (Θ) * (-φ + x (Θ)) = y '(Θ) * (ψ - y (Θ))

y seguir y seguir y es de esperar que pueda resolver Θ
el marco está trabajando en podría tener cosas para ayudar a resolver esto, y siempre se puede tomar el camino más fácil y raíces aproximadas a través Newton's Method

Answer 3

Una elipse se define como el conjunto de puntos cuya suma de la distancia al punto A y la distancia al punto B es constante e. (A y B se llaman los focos de la elipse).

Todos los puntos P, cuya suma AP + BP es menor que e, se encuentran dentro de la elipse.

Un círculo se define como el conjunto de puntos cuya distancia al punto C es r.

Una prueba simple para intersección de círculo y la elipse es el siguiente:

Encuentra
P como la intersección del círculo y la línea de CA y
Q como la intersección del círculo y la línea BC.

círculo y la elipse se cruzan (o el círculo se encuentra completamente dentro de la elipse) si
AP + BP < = e   o   AQ + BQ < = e

EDITAR:

Después del comentario de Martin DeMello y de adaptar mi respuesta en consecuencia, pensé más sobre el problema y encontré que la respuesta (con el Segundo cheque) todavía no detecta todos los intersecciones:

Si círculo y la elipse se cruzan sólo es muy escasamente (sólo un poco más que ser tangente) P y Q no se encuentran dentro de la elipse:

Por lo que la prueba descrita anteriormente detecta colisión solo si la superposición es "lo suficientemente grande". Tal vez sea lo suficientemente bueno para sus propósitos prácticos, aunque matemáticamente no es perfecto.

Answer 4

si un círculo y una elipse chocan, entonces o bien sus límites se cruzan 1, 2, 3, o 4 veces (o infinitamente muchos en el caso de una elipse circular que coincide con el círculo), o el círculo está dentro de la elipse o viceversa

Supongo que el círculo tiene una ecuación de (x - a)^2 + (y - b)^2 < = r^2 (1) y la elipse tiene una ecuación de [(x - c)^2]/[d^2] + [(y - e)^2]/[f^2] < = 1 (2)

Para verificar si una de ellas está dentro de la otra, puede evaluar la ecuación del círculo en las coordenadas del centro de la elipse (x = c, y = e), o viceversa, y ver si se cumple la desigualdad.

Para comprobar los otros casos en los que se cruzan sus límites, debe comprobar si el sistema de ecuaciones descrito por (1) y (2) tiene alguna solución.

Usted puede hacer esto mediante la adición de (1) y (2), que le da

(x - a)^2 + (y - b)^2 + [(x - c)^2]/[d^2] + [(y - e)^2]/[f^2] = r^2 + 1

próxima multiplica los términos, dando

x^2 - 2ax + a^2 + y^2 - 2by + b^2 + x^2/d^2 - 2cx/d^2 + c^2/d^2 + y^2/f^2 - 2ey/f^2 + e^2/f^2 = r^2 + 1

recoger los términos semejantes, obtenemos

(1 + 1/d^2)x^2 - (2a + 2c/d^2)x + (1 + 1/f^2)y^2 - (2b + 2e/f^2)y = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

ahora vamos m = (1 + 1/d^2), n = -(2a + 2c/d^2), o = (1 + 1/f^2), and p = -(2b + 2e/f^2)

la ecuación es ahora mx^2 + nx + oy^2 + py = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

ahora tenemos que completar las plazas en el lado izquierdo

m[x^2 + (n/m)x] + o[y^2 + (p/o)y] = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2 

m[x^2 + (n/m)x + (n/2m)^2 - (n/2m)^2] + o[y^2 + (p/o)y + (p/2o)^2 - (p/2o)^2] = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2 

m[(x + n/2m)^2 - (n/2m)^2] + o[(y + p/2o)^2 - (p/2o)^2] = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2 

m(x + n/2m)^2 - m(n/2m)^2 + o(y + p/2o)^2 - o(p/2o)^2 = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2 

m(x + n/2m)^2 + o(y + p/2o)^2 = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2 + m(n/2m)^2 + o(p/2o)^2 

este sistema tiene una solución iff 11 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2 + m(n/2m)^2 + o(p/2o)^2 >= 0

Ahí lo tienes si no cometí ningún error algebraico No sé cuánto puede simplificar la expresión resultante, por lo que esta solución puede ser bastante costosa desde el punto de vista informático si va a verificar muchos círculos/elipses

Answer 5

Olvídese de una solución matemática. Como puede ver fácilmente dibujando, puede tener hasta cuatro soluciones y, por lo tanto, probablemente un polinomio de cuarto grado.

En su lugar, haga una búsqueda binaria a lo largo del borde de una de las figuras. Es fácil determinar si un punto se encuentra dentro de una elipse y más aún en un círculo (solo ver si la distancia es más corta que el radio).

Si realmente quieres ir a las matemáticas, Wolfram MathWorld tiene un buen artículo aquí: http://mathworld.wolfram.com/Circle-EllipseIntersection.html pero ten cuidado, todavía tendrás que escribir un solucionador de ecuaciones polinómicas, probablemente usando algo así como la búsqueda binaria.

Answer 6

Suponiendo: la elipse está centrada en el origen y con la semi-mayor eje (de longitud a) orientado a lo largo del eje x, y con un semi-minor eje de la longitud b; E2 es la excentricidad al cuadrado, es decir (a a-b b)/(a ​​* a); el círculo está centrado en X, Y y de radio r.

Los casos fáciles son: el centro del círculo está dentro de la elipse (es decir hypot (X/a, Y/b) < = 1) así que hay una intersección; el centro del círculo está fuera de un círculo centrado en 0 de radio a + r (es decir, hypot (X, Y)> a + r) por lo que no hay una intersección.

Un enfoque para los otros casos es calcular las coordenadas geodésicas (latitud, altura) del centro del círculo. El círculo corta la elipse si y solo si la altura es menor que el radio.

La latitud geodésica de un punto sobre una elipse es el ángulo la normal a la elipse en el punto que hace con el eje x, y la altura de un punto fuera de la elipse es la distancia del punto desde el apunta en la elipse más cercana a ella. Tenga en cuenta que la latitud geodésica no es la misma que el ángulo polar desde el centro de la elipse hasta el punto a menos que la elipse sea de hecho circular.

En las fórmulas de la conversión de coordenadas de latitud geodésicas, ht a coordenadas cartesianas x, Y es X = (nu + ht) * cos (LAT), Y = (nu * (1-E2) + ht) * sin (lat) donde nu = a/sqrt (1 - E2 * sin (lat) sin (lat)). El punto en la elipse más cercano a X, Y es el punto con la misma latitud, pero altura cero, es decir x = nu cos (lat), y = nu * (1-E2) * sin (lat). Tenga en cuenta que nu es una función de latitud.

Desafortunadamente, el proceso de encontrar lat, ht de X, Y es iterativo. Un enfoque es encontrar primero la latitud, y luego la altura.

un poco de álgebra muestra que los satisface latitud lat = atan2 (Y + E2 * nu sin (lat), X) que puede ser utilizado para calcular aproximaciones sucesivas a la latitud, a partir de lat = atan2 (Y , X (1.0-E2)), o (más eficientemente) puede ser resuelto usando el método de newton.

Cuanto más grande es E2, es decir, cuanto más plana es la elipse, más iteraciones se necesitarán . Por ejemplo, si la elipse es casi circular (digamos E2 < 0.1), cinco iteraciones obtendrán x, y por debajo de dentro de un * 1e-12, pero si la elipse es muy plana, p. E2 = 0.999 ¡necesitará alrededor de 300 iteraciones para obtener la misma precisión!

Finalmente, dada la latitud, la altura se puede calcular mediante el cálculo de (x, y): x = nu cos (LAT), y = nu (1-E2) * sin (lat) y entonces h es la distancia de x, y al centro del círculo, h = hypot (Xx, Yy)

Answer 7

Esto no es tan difícil. La respuesta de user168715 es correcta en general, pero hacer cálculos no es necesario. Sólo trigonometría.

Encuentra el ángulo entre el centro de los dos objetos.El uso de este se encuentra el punto más cercano al centro del círculo de la elipse con el polar formulario:

(Tomado del artículo de Wikipedia sobre Ellipses)

Ahora compare la distancia entre los dos objetos centros, restando el radio de la elipse y el radio del círculo.

Quizás me falta algo; quizás ArcTan/Cos/Sin sea lento, pero no lo creo, y debería haber aproximaciones rápidas si es necesario.

Answer 8

Agrande los radios mayor y menor de la elipse por el radio del círculo. Luego prueba si el centro del círculo dado se encuentra dentro de esta nueva elipse más grande al sumar las distancias a los focos de la elipse ampliada.

Este algoritmo es bastante eficiente. Puedes salir antes si el círculo dado no se cruza con un círculo que circunscribe la elipse. Esto es más lento que una prueba de cuadro delimitador, pero encontrar el cuadro delimitador de una elipse no alineada con el eje es complicado.

Answer 9

Quería proporcionar algo de información sobre el problema más general que involucra el contacto entre dos elipses. Calcular la distancia de aproximación más cercana de dos elipses era un problema de larga data y solo se resolvió analíticamente en los últimos diez años; no es de ninguna manera simple. La solución al problema se puede encontrar aquí http://www.e-lc.org/docs/2007_01_17_00_46_52/.

El método general para determinar si hay contacto entre dos elipses es primero calcular la distancia de aproximación más cercana de las elipses en su configuración actual y luego restarla de su magnitud de separación actual. Si este resultado es menor o igual que 0, entonces están en contacto.

Si alguien está interesado, puedo publicar un código que calcule la distancia más cercana, está en C++. El código es para el caso general de dos elipses arbitrarias, pero obviamente puede hacerlo para un círculo y una elipse, ya que un círculo es una elipse con los mismos ejes menores y mayores.

Answer 10

Sé que es demasiado tarde, pero espero que ayude a alguien. Mi enfoque para resolver este problema fue interpolar la elipse en un polígono de n dimensiones, luego construir una línea entre cada 2 puntos y encontrar si el círculo se cruza con cualquiera de las líneas o no. Esto no proporciona el mejor rendimiento, pero es práctico y fácil de implementar.

para interpolar la elipse a un polígono de n dimensiones, puede utilizar:

float delta = (2 * PI)/n; 

    std::vector<Point*> interpolation; 

    for(float t = 0; t < (2 * PI); t += delta) { 

     float x = rx * cos(t) + c->get_x(); 
     float y = ry * sin(t) + c->get_y(); 

     interpolation.push_back(new Point(x, y)); 
    } 

c: El centro de la elipse. rx: El radio del eje alineado x de la elipse. ry: El radio del eje Y alineado de la elipse.

Ahora tenemos los puntos de interpolación, podemos encontrar la intersección entre el círculo y las líneas entre cada 2 puntos. Una forma de encontrar la intersección línea-cruz se describe here, , una intersección se produce si se produjo una intersección entre cualquiera de las líneas y el círculo.

Espero que esto ayude a cualquiera.