Intersección con el objeto de trazado elipsoide

Question

En mi juego de necesito calcular el tiempo cuando un barco llega al planeta. Lo que se sabe es buque a la posición inicial y la velocidad (que es constante), y la posición del planeta en un momento dado (que es el que sigue una trayectoria elíptica). Para ser más específicos:

Con respecto a la nave:

$x_0, y_0$ - buques de la posición inicial
$v$ - de la nave a velocidad constante

Sobre el planeta:

La posición del planeta está dada por $$\begin{align}x(t)&=a\cos{\omega_0t}\\y(t)&=b\sin{\omega_0t}\end{align}$$ with $un\ge b\gt0$ and $\omega_0\gt0$. I.e., the planet's path follows an ellipse in standard position with a phase of $0$.

Ahora, lo que necesito saber, es ¿en qué momento las dos posiciones se intersecan (posición del buque y posición del planeta). Así que estoy buscando la intersección de tiempo $t_i$, o un punto de intersección $p_i$, o ángulo de $\alpha$ a que los barcos deben ser despedido, o la distancia $d_i$ de punto de intersección de punto de partida $x_0, y_0$. Cualquiera de estas 4 cosas que debe hacer (calculando la una de la otra es trivial, por supuesto). Estoy buscando el más cercano a dicho punto de intersección de curso (el más pequeño de tales $d_i$ o $t_i$ de todos los posibles).

En otras palabras, necesito saber en qué ángulo se debe enviar a la nave de $x_0, y_0$, de modo que va a llegar al planeta en el menor tiempo posible.

ACTUALIZACIÓN 29.12.2016

Yo soy de la pausa de mi trabajo sobre este problema, ya que ya he pasado 5 días y estoy realmente cansado de él. He probado todo tipo de métodos, pero el código está libre de errores, y que este problema es mucho más complejo de lo que pensé por primera vez. Voy a terminar en algún momento en el futuro, pero ahora mismo hay otros aspectos del juego que han de implementar. Así que me gustaría ayudar a todos los que contribuyeron, voy a upvote/aceptar sus respuestas una vez que llegue a terminar la aplicación (voy a presentar mi último algoritmo en ese punto y la publicaremos para que cualquiera lo use). Gracias de nuevo a todos por ahora!

(P. S., si le interesa, esta es la forma en la cosa funciona cuando funciona: https://youtu.be/KjQCOkWVIvg)

Answer 1

Creo que la búsqueda de $t_i$ puede ser la forma más sencilla de acercarse a este problema, aunque el enfoque no es realmente simple.

La distancia desde su nave espacial a la posición inicial a la posición del planeta en el momento $t$ es $$ \sqrt{(a\cos(\omega_0 t) - x_0)^2 + (b\sin(\omega_0 t) - y_0)^2}. $$ Suponiendo que la nave espacial se inicia en el momento $t_0,$ la distancia de la nave espacial de la posición de partida para la la nave espacial de la posición en el momento $t$ es $v(t - t_0).$ (He introducido el parámetro de $t_0$ porque no estaba claro que usted quería que la nave espacial para que se inicie en el instante en que el planeta pasado el punto de $(a,0).$ Si ¿ desea que la nave espacial para empezar en aquel preciso instante, acaba de establecer $t_0=0$ en todas las ecuaciones; va a simplificar un poco.)

Para que la nave espacial para interceptar el planeta en tiempo $t_i,$ la nave y el planeta se deben a la misma distancia de la nave punto de partida en ese instante. es decir, $$ \sqrt{(a\cos(\omega_0 t_i) - x_0)^2 + (b\sin(\omega_0 t_i) - y_0)^2} = v(t_i - t_0). $$ Así que si definimos una función de $f$ por $$ f(t) = \sqrt{(a\cos(\omega_0 t_i) - x_0)^2 + (b\sin(\omega_0 t_i) - y_0)^2} - v(t_i - t_0), $$ una forma de encontrar un tiempo cuando la nave espacial puede interceptar el planeta es resolver para $t$ en la ecuación de $f(t)= 0.$

Por desgracia, estoy bastante seguro de que no hay forma cerrada de la solución para esta ecuación, al menos no con las funciones que tendría disponible en un típico entorno de programación. Así que la única manera de resolver de la ecuación por métodos numéricos, básicamente, hacer conjeturas y la refinación de las conjeturas hasta que llegue "lo suficientemente cerca" de la solución exacta.

La distancia del planeta a partir de la nave espacial en la posición inicial, $(x_0,y_0),$ periódicamente aumenta y disminuye. La tasa de aumento tiene un valor máximo $u_\max$. Si $v$ es mayor que o igual a $u_\max$ entonces no es exactamente una solución a la ecuación de $f(t)= 0.$ El planeta nunca puede aumentar su distancia de $(x_0,y_0)$ más rápido de lo que es viajar, y nunca viaja más rápido que la la velocidad de $a\omega_0,$ así que si $v \geq a\omega_0$ el problema es ligeramente más sencillo de lo que podría ser. Si $v < a\omega_0$, entonces usted tiene que averiguar el valor de de $u_\max$, de modo que usted puede determinar si $v \geq u_\max$, o usted puede decidir resolver el problema sin haciendo la suposición de que la solución a $f(t) = 0$ es único.

Vamos a considerar en primer lugar lo que sucede cuando sabemos que la solución es única. Sabemos que $f(t)>0$ al $t=t_0$; ahora encontrar un momento de $t_1$ tal que $f(t_1)< 0.$ Establecimiento $r_0=\max\{a,b\},$ cada parte de la elipse está dentro del círculo de radio de $r$ alrededor de $(0,0),$ lo que ninguna parte de la elipse puede ser más que $r_0 + \sqrt{x_0^2+y_0^2}$ a partir de la posición de la la nave espacial. Por lo que cualquier valor de $t_1$ tal que $$ t_1 > t_0 + \frac{r_0 + \sqrt{x_0^2+y_0^2}}{v} $$ será suficiente. Ahora podemos utilizar una de varias maneras de encontrar un valor aproximado de $t_i,$ pero la forma más simple puede ser el "interseccion" método: encontrar el punto medio de un intervalo de tiempo, calcula el $f(t)$ en el punto medio, y, a continuación, cambiar su intervalo el intervalo limitado por el punto medio y uno de los dos anteriores extremos del intervalo, de modo que $f(t)$ cambia de signo entre los nuevos extremos. En otras palabras, dividir el intervalo de tiempo a la mitad y reemplazar el intervalo antiguo con la mitad del intervalo en el que $f(t)$ cambios de el positivo y el negativo. Repita hasta que el intervalo es tan pequeño que ya no hace la diferencia donde en el intervalo de la solución es (es decir, no importa el tiempo que usted elija, la nave espacial se acercan suficiente para el planeta en ese momento en que se considere un "hit"). Si una separación de $\delta$ unidades de distancia es "lo suficientemente cerca" en el espacio, a continuación, una diferencia de tiempo de $\delta/v$ va a ser "lo suficientemente cerca" (posiblemente incluso mejor que "lo suficientemente cerca") en el tiempo.

En el caso simple (solución única), en este punto en el que está hecho. El resto de esta respuesta se refiere a la más complicada "posiblemente no solución única" versión del problema.

Si usted no sabe que la solución es única, usted todavía puede usar el interseccion método, pero si se utiliza como se describe más arriba puede que no encontrar la primera solución. Es posible que $f(t)$ tiene un mínimo local que es menos de cero, pero eso $f(t)$ es positivo en algún momento después de eso. Habría entonces tres (o cinco o siete o más) de las soluciones de antes de $f(t)$ va negativos para el último momento. Para estar seguro de que usted no se pierda la primera solución de $f(t)=0,$ usted tiene que averiguar en qué momento los mínimos locales ocurrir.

Para encontrar los mínimos locales ocurrir, tomar la derivada de $f(t)$ con respecto al $t$ (o han Wolfram Alpha hacerlo por usted), y resolver para $t$ en la ecuación en la que los que la función es cero. Usted solo necesita encontrar una solución a $t=t_2,$ no importa si es la "primera" y, a continuación, todas las otras soluciones son sólo $t_2$ más o menos un múltiplo de $2\pi/\omega.$

Encontrar los primeros mínimo local; si $f(t)<0$ en ese momento, entonces la solución es entre el $t_0$ y que el tiempo; de lo contrario, intente con la siguiente mínimo local, y el siguiente, y así sucesivamente hasta encontrar dos mínimos locales tales que $f(t)>0$ en el primero y $f(t)<0$ en el segundo y, a continuación, buscar una solución entre los dos tiempos; que será la primera solución. (Por supuesto, si $f(t)=0$ en cualquiera de los mínimos locales luego de que su solución. Usted podría incluso aceptar el mínimo local como una solución si $-\delta < f(t) < \delta$ donde $\delta$ es una distancia a la que se considerar "lo suficientemente cerca" para contar como una intercepción.)

Answer 2

Usted tiene la elipse de la trayectoria de los planetas $$ \left( \frac{x}{a} \right)^2 + \left( \frac{y}{b} \right)^2= 1 $$ (Nota: yo uso un sistema de coordenadas, donde el origen no está en la elipse).

Además tiene un punto de inicio de la $u_0 = (x_0, y_0)$ donde la línea recta de la nave de la trayectoria $$ u = u_0 + v t \quad (*) $$ se originan a partir de.

Una posible trayectoria del planeta en la elipse es $$ (x, y) = (a \cos \omega t, b \sin \omega t) \quad (**) $$ Una intersección en algún momento $t \ge 0$ va a llevar a la ecuación: $$ (a \cos \omega t, b \sin \omega t) = (x_0 + v_x t, y_0 + v_y t) $$ o $$ (f(t), g(t)) = (x_0 + v_x t - \cos \omega t, y_0 + v_y t - b \sin \omega t) = (0, 0) = 0 \quad (***) $$

Update:

Knowing now that the direction of $v$ es de un grado de libertad, se puede proceder. $$ v = (v_x,v_y) = \lVert v\rVert (\cos(\phi)\sin(\phi)) $$ Tenemos de todo, junto a la modelo de la intersección problema en GeoGebra. La información que determina que el problema de la instancia es $$ x_0, y_0, a, b, \omega \lVert v\rVert \quad (P) $$ las variables son $$ \phi, t $$ En la imagen de abajo del punto de $A$ es el lugar de inicio de la nave. $B$ es la posición de la nave en $t=1$. El rayo verde de $A$ a través de $B$ es la trayectoria de $(*)$ de la nave. La elipse de color rojo es la trayectoria del planeta $(**)$. Los puntos de intersección de $(*)$$(**)$$C$$D$. Punto de $S$ es la posición de la nave en el momento $t$, $P$ es la posición del planeta en el momento $t$.

En la versión interactiva (ver enlace más abajo), se puede juguetear con el $t$ regulador y el reloj de la nave y el planeta se mueven en sus trayectorias.

El objetivo es encontrar un valor de$\phi$, lo que llevará a una posición común de la nave y el planeta en algún momento $t\ge 0$.

La clave son las dos funciones de $(***)$, que se muestra como $f(x)$ (línea púrpura) y $g(x)$ (línea azul). En la versión interactiva se nota que estas gráficas cambiar dependiendo de el valor de $\phi$. Para resolver el problema uno tiene que encontrar un valor de $\phi$ que hace que los gráficos de $f$ $g$ a que ambos tienen una raíz (valor cero) en algunos $x\ge 0$. En la imagen, te darás cuenta de dos de tales argumentos en torno a $x=1.5$$x=4$. Corresponden a las intersecciones $C$$D$. El actual tiempo $t$ de la escena es visualizada por la línea vertical negra en torno a $x=3.6$ (ver $t$ slider así), por lo que la nave y el planeta están poco antes del impacto en $D$, $t=4$.

En general, dependiendo del problema instancia $(P)$, no puede haber ninguna, una o dos intersecciones.

Para implementar este procedimiento en una máquina, tenemos que sustituir al hombre interactuar con el control deslizante para $\phi$, buscando simultánea raíces de $f$ $g$ por algunos caracteres numéricos, la solución de la ecuación de $(***)$, lo que $$ F(\phi, t) = \begin{pmatrix} x_0 + \lVert v\rVert \cos(\phi) t - a \cos(\omega t) \\ y_0 + \lVert v\rVert \sin(\phi) t - b \sin(\omega t) \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} $$

Los métodos más comunes son la raíz de la constatación, por iteración Newton-Raphson o simple interseccion, o la reformulación como punto fijo de la iteración.

Si nos fijamos en el cuadrado de la distancia entre la nave y el planeta que conseguir que esto $$ q(\phi, t) = (x_0 + \lVert v\rVert \cos(\phi)t - a \cos(\omega t))^2 + (y_0 + \lVert v\rVert \sin(\phi)t - b \sin(\omega t))^2 $$

Actualización:

Aquí hay un enlace a la versión interactiva: GeoGebra

Actualización:

Me explicó el método de Newton-Raphson iteración a mi amigo de Ruby (ver aquí), y tocó un par de veces para mí.

irb> newton($u0, 1e-10, 20)
x0 = 1.0
y0 = 2.0
a  = 2.0
b  = 1.0
v  = 1.0
w  = 1.0
0: u=Vector[1.0, 2.0] f(u)=Vector[2.9128982848305642, 2.7736445427901115]
1: u=Vector[0.382829472675263, 0.3248271541942971] f(u)=Vector[-0.5940984322993181, 1.8021930994105337] d=1.8975913455808797
 .
 .
20: u=Vector[-94.18834695323662, 1959.9371619837884] f(u)=Vector[1955.6477996333003, 118.82040799198684] d=1959.2540941812401
maxstep = 20 reached, fail
=> nil

Así que no convergen, cuando empezamos a ver el $u_0 = (x_0, y_0) = (1,2)$ para una raíz. Por otro lado $u=(\phi, t)$, por lo que no fue una buena idea en el primer lugar.

irb> newton(Vector[-1,4], 1e-10, 20)
 .
 .
20: u=Vector[138.25481797929191, 454.49648517971787] f(u)=Vector[456.3793855184854, 12.384069736222514] d=456.5473783841737
maxstep = 20 reached, fail

Otro pierda.

irb> newton(Vector[-1,1], 1e-10, 20)
0: u=Vector[-1, 1] f(u)=Vector[0.45969769413186023, 0.317058030384207]
1: u=Vector[-1.5668891620557184, 1.0077918056648623] f(u)=Vector[-0.06352118626769587, 0.14656055765459897] d=0.15973396058722875
2: u=Vector[-1.664180141632932, 1.103100791097277] f(u)=Vector[-0.004523100381582101, 0.009095949944068482] d=0.010158481306123844
3: u=Vector[-1.67043452556281, 1.1098339180715397] f(u)=Vector[-1.951140039613275e-05, 4.57909054815131e-05] d=4.9774509241529196e-05
4: u=Vector[-1.670469710132332, 1.1098684183520295] f(u)=Vector[-6.100806526632141e-10, 1.337344013307984e-09] d=1.4699276896108456e-09
5: u=Vector[-1.6704697111186804, 1.1098684193565171] f(u)=Vector[-2.220446049250313e-16, 2.220446049250313e-16] d=3.1401849173675503e-16
d=3.1401849173675503e-16 < eps=1.0e-10, success

Sí, funcionó!

irb> newton(Vector[0,0], 1e-10, 20)
0: u=Vector[0, 0] f(u)=Vector[-1.0, 2.0]
Jacobian Matrix[[-0.0, 1.0], [0.0, -1.0]] is not regular at u=Vector[0, 0]!
=> nil

Ouch, otro mal comienzo. Esto recuerda, que uno tiene que venir para arriba con un buen valor de inicio, cerca de la sospecha de raíz, para que este método funcione.

Answer 3

Las ecuaciones paramétricas para la elipse son $$x=a\cos\omega t~~~;~~~y=b\sin\omega t$$ y las ecuaciones paramétricas para la línea son $$x=x_0+v_0\cos\theta t~~~;~~~y=y_0+v_0\sin\theta t$$ que $\theta$ es el ángulo de la trayectoria con respecto a $x$ eje. A continuación, podemos obtener posiciones se cruzan con estas ecuaciones.

Puedo investigar algunos casos para este problema.

Primera Etapa: Con $a$, $b$, $x_0$, $y_0$ y con lo prescrito $\theta$ $\omega$ que son constantes aquí, queremos determinar $v$, tenemos: $$t=\frac{a\cos\omega t-x_0}{v\cos\theta}=\frac{b\sin\omega t-y_0}{v\sin\theta}$$ así $$(b\cos\theta)\sin\omega t+(a\sin\theta)\cos\omega t=x_0\sin\theta-y_0\cos\theta$$ por substituating $\displaystyle\sin\omega t=\frac{2\tan\frac{\omega t}{2}}{1+\tan^2\frac{\omega t}{2}}$ $\displaystyle\cos\omega t=\frac{1-\tan^2\frac{\omega t}{2}}{1+\tan^2\frac{\omega t}{2}}$ y simplyfing $\tan\frac{\omega t}{2}=k$ llegamos a la conclusión de que $$(b\cos\theta)\frac{2k}{1+k^2}+(a\sin\theta)\frac{1-k^2}{1+k^2}=x_0\sin\theta-y_0\cos\theta$$ así $$\tan\frac{\omega t}{2}=\frac{b\cos\theta\pm\sqrt{(b^2-y_0^2)\cos^2\theta+(a^2-x_0^2)\sin^2\theta+x_0y_0\sin2\theta}}{(a+x_0)\sin\theta-y_0\cos\theta}~~~~~~~~(1)$$ o $$t=\frac{2}{\omega}\tan^{-1}\frac{b\cos\theta\pm\sqrt{(b^2-y_0^2)\cos^2\theta+(a^2-x_0^2)\sin^2\theta+x_0y_0\sin2\theta}}{(a+x_0)\sin\theta-y_0\cos\theta}$$ este es el tiempo de la bruja del planeta llega a la línea recta y en caso de accidente, el barco que debe recorrer una distancia en $t$-tiempo que va allí, o $$v=\frac{x-x_0}{t\cos\theta}$$ si el prescrito $v$ no es igual a este valor, la nave y el planeta no colisionan.

Segunda Etapa: Con $a$, $b$, $x_0$, $y_0$ y con lo prescrito $\theta$ $v$ que son constantes aquí, queremos determinar $\omega$: $$t=\frac{x-x_0}{v\cos\theta}$$ con (1): $$\omega=\frac{2v\cos\theta}{x-x_0}\tan^{-1}\frac{b\cos\theta\pm\sqrt{(b^2-y_0^2)\cos^2\theta+(a^2-x_0^2)\sin^2\theta+x_0y_0\sin2\theta}}{(a+x_0)\sin\theta-y_0\cos\theta}~~~~~~~~(2)$$ como la anterior etapa, el planeta debe recorrer una distancia en que el camino de $t$-tiempo que va allí, de lo contrario, si el prescrito $\omega$ no es igual a este valor, la nave y el planeta no colisionan.

Tercera Etapa:en Este caso es complicado. Con $a$, $b$, $x_0$, $y_0$ y con lo prescrito $\omega$ $v$ que son constantes aquí, queremos determinar $\theta$ que para chocan se produce. Para este propósito se elimina el tiempo entre las ecuaciones $$\left\lbrace\begin{array}{c l}\cos\theta=\frac{x-x_0}{vt}=\frac{a\cos\omega t-x_0}{vt},\\\sin\theta=\frac{y-y_0}{vt}=\frac{b\sin\omega t-x_0}{vt}.\end{array}\right.$$ Ya no sé que estos casos son de interés de @Betalord, yo termine mis notas.