Comparar ángulos y resolver la diferencia

27

Quiero comparar ángulos y tener una idea de la distancia entre ellos. Para esta aplicación, estoy trabajando en grados, pero también funcionaría para radianes y graduados. El problema con los ángulos es que dependen de la aritmética modular, es decir, 0-360 grados.

Digamos que un ángulo está a 15 grados y uno está a 45. La diferencia es de 30 grados, y el ángulo de 45 grados es mayor que el de 15 grados.

Pero, esto se rompe cuando tienes, digamos, 345 grados y 30 grados. Aunque se comparan correctamente, la diferencia entre ellos es de 315 grados en lugar de los 45 grados correctos.

¿Como puedo resolver esto? Podría escribir código algorítmico:

if(angle1 > angle2) delta_theta = 360 - angle2 - angle1;
else delta_theta = angle2 - angle1;

Pero preferiría una solución que evite comparaciones / ramificaciones, y se base completamente en la aritmética.

Thomas O
fuente
En este problema, ¿podemos suponer que los ángulos dados están en el rango [0,360] o (-infinito, + infinito)? Por ejemplo, ¿debería funcionar el algoritmo para comparar -130 grados con 450?
egarcia
Suponga que los ángulos están normalizados a ese rango.
Thomas O

Respuestas:

29

Aquí está mi versión simplificada, sin ramificaciones, sin comparación, sin min / max:

angle = 180 - abs(abs(a1 - a2) - 180); 

Se eliminó el módulo, ya que las entradas están suficientemente restringidas (gracias a Martin por señalarlo).

Dos abdominales, tres restas.

JasonD
fuente
No necesita el módulo, los valores de entrada están restringidos al rango [0,360] (vea el comentario de Thomas al envío original). Con buena pinta.
Martin Sojka
Ah, sí, tienes razón. Tuve una entrada menos estricta cuando lo probé.
JasonD
pero ¿y si quisieras preservar el signo de la diferencia para saber cuál estaba a la izquierda?
Jacob Phillips
9

Aunque se comparan correctamente, la diferencia entre ellos es de 315 grados en lugar de los 45 grados correctos.

¿Qué te hace pensar que 315 es incorrecto? En una dirección, es de 315 grados, en la otra dirección, es de 45. Desea elegir el menor de los 2 ángulos posibles y esto parece requerir intrínsecamente un condicional. No puede resolverlo con aritmética envolvente (es decir, a través del operador de módulo) porque a medida que aumenta gradualmente un ángulo, el ángulo entre ellos crece hasta llegar a 180 y luego comienza a disminuir.

Creo que debe verificar ambos ángulos y decidir qué dirección desea medir, o calcular ambas direcciones y decidir qué resultado desea.

Kylotan
fuente
Lo siento, debería aclararlo. Si lo hiciste al revés, 30 - 345 es -315 y un ángulo negativo no tiene mucho sentido. Supongo que estoy buscando el ángulo más pequeño entre los dos. es decir, 45 grados es menor que 315.
Thomas O
2
Pero no hay 'reversa': tiene 2 ángulos y 2 tipos de rotación que puede realizar para que una coincida con la otra. Un ángulo negativo tiene mucho sentido: después de todo, es solo una medida de rotación desde un eje arbitrario.
Kylotan
Si desea el ángulo más pequeño, entonces abs (a1% 180 - a2% 180) le dará ese ángulo. Sin embargo, no le dirá la dirección. Quitar los abdominales te dará el ángulo más pequeño "pasar de" a1 "a" a2
Chewy Gumball
2
@ Chewy, ¿eh? La diferencia entre 180 y 0 no es 0, y la diferencia entre 181 y 0 no es 1 ...
dash-tom-bang
1
@ dash-tom-bang Tienes toda la razón. No sé lo que estaba pensando, pero no era correcto ahora que lo veo de nuevo. Por favor, ignore mi comentario anterior.
Chewy Gumball
4

Siempre existe el truco de hacer ambas ramas y dejar que el resultado de la comparación elija una:

delta_theta = (angle1 > angle2) * (360 - angle2 - angle1)
              + (angle2 > angle1) * (angle2 - angle1);

No conozco una manera de hacerlo sin comparaciones , pero generalmente la rama es lo que hace que el código sea lento y largo, no la comparación. Al menos en mi opinión, esto es más legible que la respuesta de Martin (cualquier buen programador de C lo reconocerá como un equivalente sin ramas y verá lo que está haciendo), pero también menos eficiente.

Pero como dije en mi comentario, los algoritmos sin ramificación son buenos en los procesadores con tuberías profundas y malas predicciones: un microcontrolador generalmente tiene una pequeña tubería, y una PC de escritorio generalmente tiene una buena predicción, así que a menos que esté apuntando a una consola de juegos, la versión ramificada es probablemente la mejor ruta si reduce el recuento de instrucciones.

Como siempre, la creación de perfiles, que podría ser tan simple como el conteo de operaciones para su sistema, le dará la respuesta real.


fuente
2

Suponiendo que verdadero se evalúa a -1 y falso se evalúa a 0, y '~', '&' y '|' son bit a bit no , y / o operadores respectivamente, y estamos trabajando con aritmética de complemento a dos:

temp1 := angle1 > angle2
/* most processors can do this without a jump; for example, under the x86 family,
   it's the result of CMP; SETLE; SUB .., 1 instructions */
temp2 := angle1 - angle2
temp1 := (temp1 & temp2) | (~temp1 & -temp2)
/* in x86 again: only SUB, AND, OR, NOT and NEG are used, no jumps
   at this point, we have the positive difference between the angles in temp1;
   we can now do the same trick again */
temp2 := temp1 > 180
temp2 := (temp2 & temp1) | (~temp2 & (360 - temp1))
/* the result is in temp2 now */
Martin Sojka
fuente
+1 porque es inteligente, pero en un microcontrolador probablemente tenga un rendimiento mucho peor que la versión ramificada.
Depende un poco del microcontrolador, pero sí, generalmente no vale la pena; Un salto condicional (corto) suele ser lo suficientemente rápido. Además, las líneas tercera y quinta se pueden reescribir para que sean un poco más rápidas utilizando la operación xor (^) de esta manera, pero las dejé en la forma actual para mayor claridad: temp1: = temp2 ^ ((temp2 ^ -temp2) & ~ temp1), temp2: = temp1 ^ ((temp1 ^ (360 - temp1)) y ~ temp2)
Martin Sojka
1

¿Qué hay de esto?

min( (a1-a2+360)%360, (a2-a1+360)%360 )

La adición de 360 ​​está ahí para evitar diferencias negativas, porque un módulo de un número negativo devuelve un resultado negativo. Luego obtienes el menor de los dos resultados posibles.

Todavía hay una decisión implícita, pero no sé cómo evitarla. Básicamente, compara los dos ángulos calculando la diferencia en sentido horario o antihorario, y parece que quiere explícitamente la menor de estas dos diferencias. No sé cómo obtener ese resultado sin compararlos. Es decir, sin usar "abs", "min", "max" o algún operador similar.

CeeJay
fuente
Hay varias formas de calcular min, max y abs de entradas sin instrucciones de ramificación, aunque dado que este es un microcontrolador, la ramificación es probablemente la forma más rápida. graphics.stanford.edu/~seander/bithacks.html#IntegerAbs
1

Si bien su pregunta no hizo referencia a ellos, voy a trabajar asumiendo que su pregunta de cálculo de ángulo proviene de querer saber el ángulo mínimo entre dos vectores .

Ese cálculo es fácil. Asumiendo que A y B son sus vectores:

angle_between = acos( Dot( A.normalized, B.normalized ) )

Si no tuviera vectores y quisiera usar este enfoque, podría construir vectores de longitud unitaria dados sus ángulos al hacerlo new Vector2( cos( angle ), sin ( angle ) ).

Tétrada
fuente
1
El procesador en el que estoy trabajando es un pequeño microcontrolador. No tiene sentido usar funciones trigonométricas para generar un vector solo para obtener la diferencia entre ángulos, cada ciclo es precioso.
Thomas O
1
En un microcontrolador, me sorprende que no sea mejor usar una rama, pero no hay mucha aritmética en mi respuesta si realmente quieres evitar la ramificación.
JasonD
Bueno, una rama es dos ciclos y una suma / resta / etc. es un ciclo, pero la ramificación también requiere memoria de programa adicional. No es crítico, pero sería bueno.
Thomas O
Tengo la sensación de que su respuesta es correcta y la mía es incorrecta, pero no puedo entender por qué ese es el caso. :)
Kylotan
1

Básicamente lo mismo que la respuesta de JasonD, excepto que usa operaciones bit a bit en lugar de la función de valor absoluto.

¡Esto supone que tiene enteros cortos de 16 bits!

short angleBetween(short a,short b) {
    short x = a - b;
    short y = x >> 15;
    y = ((x + y) ^ y) - 180;
    return 180 - ((x + y) ^ y);
}
MickLH
fuente
0

Yo creo que

delta = (a2 + Math.ceil( -a2 / 360 ) * 360) - (a1 + Math.ceil( -a1 / 360 ) * 360);
Saad Ahmed
fuente
0

Como solo le importa eliminar ramas y operaciones "complejas" más allá de la aritmética, le recomendaría esto:

min(abs(angle1 - angle2), abs(angle2 - angle1))

Todavía necesita un absallí a pesar de que todos los ángulos sean positivos. De lo contrario, siempre se elegirá el resultado más negativo (y siempre habrá exactamente una respuesta negativa para positivo y único a y b al comparar ab y ba).

Nota: Esto no preservará la dirección entre el ángulo 1 y el ángulo 2. A veces necesitas eso para propósitos de IA.

Esto es similar a la respuesta de CeeJay, pero elimina todos los módulos. No sé cuál es el costo del ciclo abs, pero supongo que es 1 o 2. También es difícil decir cuál es el costo min. ¿Quizas 3? Entonces, junto con un ciclo por resta, esta línea debería tener un costo de alrededor de 4 a 9.

DrZ214
fuente
0

Obtenga el ángulo relativo más pequeño en forma con signo (+/-), desde la perspectiva de have hacia want :

  • a lo sumo 180 grados | PI radianes
  • -firmado si en sentido antihorario
  • + firmado si en sentido horario

Grados

PITAU = 360 + 180 # for readablility
signed_diff = ( want - have + PITAU ) % 360 - 180

Radianes

PI = 3.14; TAU = 2*PI; PITAU = PI + TAU;
signed_diff = ( want - have + PITAU ) % TAU - PI

Razón fundamental

Me encontré con este hilo después de haberlo descubierto, buscando una solución que evite el módulo; Hasta ahora no he encontrado ninguno . Esta solución es para preservar el signo de perspectiva, como @ jacob-phillips hizo este comentario . Existen soluciones más económicas si solo necesita el ángulo más corto sin signo.

ansioso
fuente
0

Es una pregunta antigua, pero me encontré con el mismo caso: tenía que obtener una diferencia angular firmada y preferiblemente sin ramas y matemáticas pesadas. Esto es lo que terminé con:

int d = (a - b) + 180 + N * 360; // N = 1, 2 or more.
int r = (d / 360) * 360;
return (d - r) - 180;

La limitación es que 'b' no debería tener más de 'N' rotaciones en comparación con 'a'. Si no puede garantizarlo y puede permitir operaciones adicionales, use esto como primera línea:

int d = ((a % 360) - (b % 360)) + 540;

Tengo la idea del comentario 13 de esta publicación: http://blog.lexique-du-net.com/index.php?post/Calculate-the-real-difference-between-two-angles-keeping-the- firmar

Mikk L.
fuente
-1

supongo que podría decir

angle1=angle1%360;
angle2=angle2%360;
var distance = Math.abs(angle1-angle2);
//edited
if(distance>180)
  distance=360-distance;

por supuesto, considerando que el ángulo se mide en grados.

Vishnu
fuente
1
No creo que esto resuelva el problema en la pregunta. 345% 360 == 345, y los abdominales (345-30) siguen siendo 315.
Gregory Avery-Weir
@ Gregory: ¡bien !, perdón por el error. Estoy editando la respuesta, mira esta nueva. :)
Vishnu
1
Por cierto, angle1 = angle1% 360; ángulo2 = ángulo2% 360; var distancia = Math.abs (ángulo1-ángulo2); es lo mismo que var distance = Math.abs (angle1-angle2)% 360, solo que más lento.
Martin Sojka