algorithm - sacar - calcular el angulo de un vector en 3 dimensiones
Algoritmo barato para encontrar la medida del ángulo entre vectores. (9)
No es difícil encontrar el ángulo entre dos vectores usando la regla del coseno . Sin embargo, dado que estoy programando para una plataforma con recursos muy limitados, me gustaría evitar cálculos como sqrt y arccos . Incluso las divisiones simples deben limitarse tanto como sea posible.
Afortunadamente, no necesito el ángulo per se, sino que solo necesito algún valor que sea proporcional a dicho ángulo.
Así que estoy buscando algún algoritmo computacionalmente barato para calcular una cantidad que esté relacionada con el ángulo entre dos vectores. Hasta ahora, no he encontrado algo que se ajuste a mis requisitos, ni he podido encontrar algo por mi cuenta.
¿Has probado un algoritmo CORDIC ? Es un marco general para resolver problemas polares ↔ rectangulares con solo sumar / restar / cambios de bits + tabla, esencialmente haciendo rotación por ángulos de la forma tan -1 (2 -n ). Puede cambiar la precisión con el tiempo de ejecución modificando el número de iteraciones.
En su caso, tome un vector como referencia fija, y copie el otro en un vector temporal, que gire utilizando los ángulos cordicos hacia el primer vector (aproximadamente bisección) hasta que alcance la precisión angular deseada.
( Editar: use el signo del producto de puntos para determinar en cada paso si se gira hacia adelante o hacia atrás. Aunque los multiplicadores son lo suficientemente económicos para permitir el uso del producto de puntos, entonces no se moleste con CORDIC, tal vez use una tabla de pares sin / cos para Matrices de rotación de ángulos π / 2 n para resolver el problema con bisección.)
( Editar: Me gusta la sugerencia de Eric Bainville en los comentarios: gire ambos vectores hacia cero y realice un seguimiento de la diferencia de ángulo.)
Aquí en SO, todavía no tengo el privilegio de comentar (aunque tengo en math.se) así que esto es en realidad una respuesta a la publicación de Timo sobre ángulos de diamante.
El concepto completo de ángulos de diamante basados en la norma L1 es muy interesante y si fuera simplemente una comparación de qué vector tiene una mayor / menor resistencia al eje X positivo, sería suficiente. Sin embargo, el OP mencionó el ángulo entre dos vectores genéricos, y supongo que el OP quiere compararlo con cierta tolerancia para encontrar el estado de suavidad / esquina o algo así, pero desafortunadamente, parece que solo con las fórmulas proporcionadas en jsperf.com o freesteel.co.uk (enlaces anteriores) parece que no es posible hacerlo usando ángulos de diamante.
Observe el siguiente resultado de mi implementación de Asymptote de las fórmulas:
Vectors : 50,20 and -40,40
Angle diff found by acos : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond : 1.21429
Convert that to degrees : 105.255
Rotate same vectors by 30 deg.
Vectors : 33.3013,42.3205 and -54.641,14.641
Angle diff found by acos : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond : 1.22904
Convert that to degrees : 106.546
Rotate same vectors by 30 deg.
Vectors : 7.67949,53.3013 and -54.641,-14.641
Angle diff found by acos : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond : 1.33726
Convert that to degrees : 116.971
Entonces, el punto es que no puedes hacer diamante (alfa) -diamante (beta) y compararlo con alguna tolerancia, a diferencia de lo que puedes hacer con la salida de atan2. Si todo lo que quieres hacer es diamante (alfa)> diamante (beta), supongo que el diamante está bien.
El producto punto podría funcionar en su caso. No es proporcional al ángulo, sino "relacionado".
El producto cruzado es proporcional al ángulo entre dos vectores, y cuando los vectores están normalizados y el ángulo es pequeño, el producto cruzado está muy cerca del ángulo real en radianes debido a la aproximación del ángulo pequeño.
específicamente:
I1Q2-I2Q1 es proporcional al ángulo entre I1Q1 y I2Q2.
El producto de puntos de dos vectores (x1, y1) y (x2, y2) es
x1 * x2 + y1 * y2
y es equivalente al producto de las longitudes de los dos vectores por el coseno del ángulo entre ellos.
Entonces, si normalizas los dos vectores primero (divide las coordenadas por la longitud)
Where length of V1 L1 = sqrt(x1^2 + y1^2),
and length of V2 L2 = sqrt(x2^2 + y2^2),
Entonces los vectores normalizados son
(x1/L1, y1/L1), and (x2/L2, y2/L2),
Y el producto de puntos de los vectores normalizados (que es el mismo que el coseno del ángulo entre los vectores) sería
(x1*x2 + y1*y2)
-----------------
(L1*L2)
Por supuesto, esto puede ser tan difícil como el cálculo del coseno.
En el día de unas pocas K de RAM y máquinas con capacidades matemáticas limitadas, utilicé tablas de búsqueda e interpolación lineal. La idea básica es simple: cree una matriz con tanta resolución como necesite (más elementos reducen el error creado por la interpolación). Luego interpolar entre los valores de búsqueda.
Aquí hay un ejemplo en el procesamiento ( enlace muerto original ).
Puedes hacer esto con tus otras funciones trigonométricas también. En el procesador 6502, esto permitió que los gráficos de trama de alambre 3D completos se computaran con un aumento de velocidad de orden de magnitud.
La solución sería trivial si los vectores se definieran / almacenaran usando coordenadas polares en lugar de coordenadas cartesianas (o, ''así como'' usando coordenadas cartesianas).
Si necesita calcular la raíz cuadrada, considere la posibilidad de utilizar el hack de invsqrt .
acos((x1*x2 + y1*y2) * invsqrt((x1*x1+y1*y1)*(x2*x2+y2*y2)));
Si no necesita el ángulo euclidiano real, pero algo que puede usar como base para las comparaciones de ángulos, entonces cambiar a la geometría del taxi puede ser una opción, ya que puede eliminar la trigonometría y la lentitud al MANTENER LA EXACTITUD (o al menos con una pérdida de precisión realmente menor, ver más abajo).
En los principales motores de los navegadores modernos, el factor de aceleración está entre 1.44 y 15.2 y la precisión es casi la misma que en atan2. El cálculo del ángulo del diamante es un promedio de 5.01 veces más rápido que atan2 y al usar el código en línea en Firefox 18, la aceleración alcanza el factor 15.2. Comparación de velocidad: http://jsperf.com/diamond-angle-vs-atan2/2 .
El código es muy simple:
function DiamondAngle(y, x)
{
if (y >= 0)
return (x >= 0 ? y/(x+y) : 1-x/(-x+y));
else
return (x < 0 ? 2-y/(-x-y) : 3+x/(x-y));
}
El código anterior le da un ángulo entre 0 y 4, mientras que atan2 le da un ángulo entre -PI y PI como muestra la siguiente tabla:
Tenga en cuenta que el ángulo del diamante es siempre positivo y en el rango de 0-4, mientras que atan2 también da radianes negativos. Así que el ángulo del diamante es algo más normalizado. Y otra nota es que atan2 da un resultado un poco más preciso, porque la longitud del rango es 2 * pi (es decir, 6.283185307179586), mientras que en ángulos de diamante es 4. En la práctica esto no es muy significativo, por ejemplo. rad 2.3000000000000001 y 2.3000000000000002 están ambos en ángulos de diamante 1.4718731421442295, pero si disminuimos la precisión al caer un cero, rad 2.300000000000001 y 2.300000000000002 dan ambos ángulos de diamante diferentes. Esta "pérdida de precisión" en los ángulos de diamante es tan pequeña, que tiene una influencia significativa solo si las distancias son enormes. Puedes jugar con las conversiones en http://jsbin.com/bewodonase/1/edit?output (versión anterior: http://jsbin.com/idoyon/1 ):
El código anterior es suficiente para comparaciones rápidas de ángulos, pero en muchos casos es necesario convertir el ángulo del diamante en radianes y viceversa. Si usted por ejemplo. tiene cierta tolerancia como ángulos radianes, y luego tiene un bucle de 100,000 veces donde esta tolerancia se compara con otros ángulos, no es aconsejable hacer comparaciones utilizando atan2. En su lugar, antes de hacer un bucle, cambia la tolerancia al radián a la tolerancia del taxi (ángulos de diamante) y realiza comparaciones en el bucle utilizando la tolerancia de diamante y de esta manera no tiene que usar funciones trigonométricas lentas en partes del código de velocidad crítica (= in bucles).
El código que hace esta conversión es este:
function RadiansToDiamondAngle(rad)
{
var P = {"x": Math.cos(rad), "y": Math.sin(rad) };
return DiamondAngle(P.y, P.x);
}
Como te das cuenta hay cos y sin . Como saben, son lentos, pero no tiene que hacer la conversión en el bucle, pero antes del bucle y la aceleración es enorme.
Y si por alguna razón, tienes que convertir el ángulo del diamante en radianes, por ejemplo. después de hacer un bucle y hacer comparaciones de ángulos para volver, por ejemplo. El ángulo mínimo de comparaciones o lo que sea como radianes, el código es el siguiente:
function DiamondAngleToRadians(dia)
{
var P = DiamondAngleToPoint(dia);
return Math.atan2(P.y,P.x);
}
function DiamondAngleToPoint(dia)
{
return {"x": (dia < 2 ? 1-dia : dia-3),
"y": (dia < 3 ? ((dia > 1) ? 2-dia : dia) : dia-4)};
}
Aquí usas atan2 , que es lento, pero la idea es usar esto fuera de cualquier bucle. No puede convertir el ángulo del diamante en radianes simplemente multiplicando por algún factor, sino que encuentra un punto en la geometría del taxi, cuyo ángulo del diamante entre ese punto y el eje X positivo es el ángulo del diamante en cuestión y convierte este punto en radianes utilizando atan2.
Esto debería ser suficiente para comparaciones de ángulos rápidos.
Por supuesto, hay otras técnicas de aceleración de atan2 (por ejemplo, CORDIC y tablas de búsqueda), pero AFAIK todas pierden precisión y aún pueden ser más lentas que atan2.
ANTECEDENTES: He probado varias técnicas: productos de puntos, productos internos, ley del coseno, círculos de unidades, tablas de búsqueda, etc. pero nada fue suficiente en caso de que tanto la velocidad como la precisión sean importantes. Finalmente encontré una página en http://www.freesteel.co.uk/wpblog/2009/06/encoding-2d-angles-without-trigonometry/ que tenía las funciones y los principios deseados.
Primero, asumí que también se podrían usar las distancias de taxis para las comparaciones de distancias precisas y rápidas, porque la distancia mayor en euclides es más grande también en taxis. Me di cuenta de que, a diferencia de las distancias euclidianas, el ángulo entre el punto inicial y el final afecta a la distancia del taxi. Solo las longitudes de los vectores verticales y horizontales se pueden convertir fácilmente y rápidamente entre euclides y taxis, pero en cualquier otro caso hay que tener en cuenta el ángulo y luego el proceso es demasiado lento (?).
Entonces, como conclusión, estoy pensando que en aplicaciones de velocidad crítica donde hay un bucle o recursión de varias comparaciones de ángulos y / o distancias, los ángulos son más rápidos para comparar en el espacio del taxi y las distancias en el espacio euclidiano (cuadrado, sin usar sqrt).