Encontrar la arista de salida con los ángulos más pequeños, dada una arista incidente y múltiples aristas de salida

Question

Tengo una arista incidente y múltiples aristas salientes, para las que quiero elegir una arista saliente tal que los ángulos entre la arista saliente y la arista entrante sean los más pequeños de todos. Conocemos las coordenadas del vértice $V$ .

El ángulo debe partir de la arista entrante ( $e_1$ ) y termina en otro borde ( $e_2$ , $e_3$ , $e_4$ ).

Además, el ángulo debe formarse de tal manera que la cara construida de $e_1$ a $e_2$ debe estar en dirección contraria a la del cierre. En otras palabras, la cara que se construye al unir todos los vértices $V$ en $e_1$ y $e_i$ juntos, debe ser un ciclo en sentido contrario a las agujas del reloj.

Así, en el caso siguiente, el borde $e_2$ debe ser elegido porque el $\theta$ es el más pequeño.

¿Existe un algoritmo que lo haga con elegancia? Los pocos algoritmos que ideo son simplemente feos y requieren muchos hacks.

Actualización: Un método que se me ocurre ( y propuesto a continuación ) es utilizar el producto cruzado de cada arista contra la arista entrante $e_1$ y obtener el mínimo $\theta_{i}$ es decir,

$$e_{1} \times e_{i} = |e_{1}||e_{i}| \sin\, \theta_{i}$$

Pero el problema de esto es que no funciona realmente. Considere los siguientes casos de prueba: $$e_1=(1,0)$$ $$e_2=(-1/\sqrt(2),1/\sqrt(2) )$$ $$e_3=(1/\sqrt(2),-1/\sqrt(2))$$

Uno se daría cuenta de que

$$\theta_2 = -45^o$$ $$\theta_3=-45^o$$

Ambos son iguales aunque sabemos que $e_2$ debe ser seleccionado.

Answer 1

Suponiendo que encontrar las coordenadas (de sus vectores) no sea demasiado difícil.

Puedes utilizar la definición de los productos punto y o cruz, y luego resolver los ángulos.

Así, por ejemplo, puede utilizar $| a \times b | = |a||b| \sin\, \theta$

Answer 2

Si intentas poner esto en código puedes considerar la función atan2(y,x), está disponible en la mayoría de los lenguajes. Ten en cuenta que toma la coordenada y como primer parámetro. Dado que atan2 toma dos parámetros, puede averiguar en qué cuadrante se encuentra tu vector, y puede mostrar el ángulo en el rango $-\pi$ a $\pi$ .

Aquí hay un fragmento de perl para demostrar cómo funciona para sus dos ángulos:

#!/usr/bin/perl

use Math::Trig;

$t_rad = atan2(1/sqrt(2),-1/sqrt(2));
$t_deg = $t_rad * 180 / pi;
print "theta_2 = $t_deg\n";

$t_rad = atan2(-1/sqrt(2),1/sqrt(2));
$t_deg = $t_rad * 180 / pi;
print "theta_3 = $t_deg\n";

Y aquí está la salida cuando se ejecuta para los dos ejemplos anteriores:

theta_2 = 135
theta_3 = -45