Calculando intersecciones de un "cono 2D" y segmentos

Question

Configuración

Considere el siguiente diagrama:

El "cono 2D" con origen A separa el plano 2D en 2 regiones, dentro y fuera.

Considere los 4 bordes representativos $c, d, e, f$ que incluyen todos los casos de intersección (asuma que un borde alineado con el límite del cono es equivalente a $e$).

Un borde está completamente dentro del cono, tiene un punto final dentro y otro fuera, tiene ambos puntos finales fuera pero un subconjunto de su interior está dentro, o está completamente fuera.

Estamos buscando los puntos de intersección del cono $A$ con cada borde. Para $c$ sería el punto final más a la derecha y el punto de intersección del borde del cono con el segmento, para $e$ serían los 2 extremos del segmento, para $f$ no existe punto de intersección, para $d$ son los 2 puntos donde el límite del cono intersecta el interior de $d$.

Problema

Con esta configuración, aquí está el problema práctico:

El cono $A$ está definido por un origen $A$ y 2 direcciones $d_1, d_2$. Cada segmento está definido por sus 2 puntos finales $p_1, p_2$.

Dado un cono arbitrario, con un ángulo interior menor que $\pi$ y un segmento arbitrario, usa exclusivamente álgebra de vectores para encontrar los 2 puntos de intersección. Si no es posible la intersección, identifícalo de alguna manera, codificado numéricamente en los 2 puntos. Puedes asumir que las direcciones $d_1, d_2$ siempre te son dadas en orden de las manecillas del reloj.

Enfoque actual

Mi enfoque actual es, tomar los 2 puntos finales del segmento, verificar su signo angular con respecto a la ventana (lo cual se hace mediante el producto punto de 2 productos cruz). Con los ángulos firmados de cada punto final identifico si el punto está dentro o fuera de la ventana. Un punto está en el interior si $0 < \sigma < w$ donde $\sigma, w$ son los ángulos firmados del punto con respecto al borde más a la derecha del cono y $w$ es el ángulo del cono.

Con esa información puedo decidir en qué caso de los 4 realmente estoy, y luego tomar decisiones con esa suposición.

Por ejemplo, si solo uno de los 2 puntos finales está en el interior, sé con certeza que hay un punto de intersección único con uno de los 2 límites, así que averiguo cuál es y luego sé los 2 puntos de intersección.

Esto es excesivamente complicado. Estoy curioso si hay una forma más unificada de encontrar ambos puntos de intersección sin tener que crear un gran árbol de condicionales if else.

Answer 1

Aquí hay un enfoque que evita dividir en casos y cualquier trigonometría. Supongamos que las direcciones $d^1 = (d^1_1,d^1_2)$ y $d^2 = (d^2_1,d^2_2)$ se dan en orden de las manecillas del reloj. Rote estos vectores en sentido horario y antihorario respectivamente para producir $$ l = (d_2^1,-d^1_1), \quad r = (-d^2_2, d^2_1). $$ Un punto $x = (x_1,x_2)$ estará dentro del cono si y solo si satisface $x \cdot l \geq 0$ y $x \cdot r \geq 0$, donde $v \cdot w$ denota el producto punto de los vectores $v$ y $w$. Más específicamente, tenemos que $x \cdot l \geq 0$ si y solo si $x$ se encuentra a la "derecha" del "lado izquierdo" del límite, y $x \cdot r \geq 0$ si y solo si $x$ se encuentra a la "izquierda" del "lado derecho" del límite.

Se nos dan dos puntos finales $p^1 = (p^1_1,p^1_2)$ y $p^2 = (p^2_1,p^2_2)$. La línea que conecta estos puntos es el conjunto de todos los puntos $$ p(t) = (1-t)p^1 + tp^2 $$ con $t \in \Bbb R$. Tenga en cuenta que $p(t)$ está en el segmento de línea que conecta los dos puntos cuando $0 \leq t \leq 1$. Además, $p(0) = p^1$ y $p(1) = p^2$.

Ahora encontramos los "tiempos" $t$ en los que esta línea cruza cualquiera de los límites. Es decir, resolvemos $$ l \cdot p(t_l) = 0 \implies (1-t_l)(l \cdot p^1) + t_l(l \cdot p^2) = 0 \implies t_l = \frac{l \cdot p^1}{(l \cdot p^1) - (l \cdot p^2)},\\ l \cdot p(t_r) = 0 \implies (1-t_r)(l \cdot p^1) + t_r(l \cdot p^2) = 0 \implies t_r = \frac{r \cdot p^1}{(r \cdot p^1) - (r \cdot p^2)}. $$ Si alguno de estos números cumple con $0 \leq t \leq 1$, se inserta en $p(t)$ para producir el punto asociado.

El único caso no contemplado aquí es la división por cero, que ocurre cuando el segmento de línea es paralelo a uno de los límites.