便宜的算法找出衡量向量之间的夹角 [英] Cheap algorithm to find measure of angle between vectors

问题描述

查找两个向量之间的角度不硬使用余弦法则。但是，因为我编程的资源非常有限的平台，我想避免的计算，例如平方根和反余弦。甚至简单的分割应限制尽可能

Finding the angle between two vectors is not hard using the cosine rule. However, because I am programming for a platform with very limited resources, I would like to avoid calculations such as sqrt and arccos. Even simple divisions should be limited as much as possible.

幸运的是，我并不需要的角度本身，而只需要一些值，该值正比于所述角度

Fortunately, I do not need the angle per se, but only need some value that is proportional to said angle.

所以，我在找一些廉价的计算算法来计算是关系到角两个向量之间的量。到目前为止，我还没有发现的东西，符合该法案，也没有我能拿出自己的东西。

So I am looking for some computationally cheap algorithm to calculate a quantity that is related to the angle between two vectors. So far, I haven't found something that fits the bill, nor have I been able to come up with something myself.

任何帮助是AP preciated。

Any help is appreciated.

吉荣

推荐答案

你有没有尝试过 CORDIC 算法？这是解决极和哈尔的总体框架;矩形的问题，只有加/减/ bitshift +表，由表单的角度基本上是在做旋转谭 ¹ （2 ^-n ）。可以通过改变迭代次数权衡精度执行时间。

Have you tried a CORDIC algorithm? It's a general framework for solving polar ↔ rectangular problems with only add/subtract/bitshift + table, essentially doing rotation by angles of the form tan^-1 (2^-n). You can trade off accuracy with execution time by altering the number of iterations.

在你的情况，采取一向量作为一个固定的参考，另外复制到一个临时的载体，你旋转使用CORDIC角度朝向第一载体（约二分），直到你达到所希望的角度精度。

In your case, take one vector as a fixed reference, and copy the other to a temporary vector, which you rotate using the cordic angles towards the first vector (roughly bisection) until you reach a desired angular accuracy.

（编辑：使用点产品的标志，以确定在每一步是否旋转向前或向后虽然如果乘法是便宜到足以允许使用点积，则不要使用CORDIC打扰，或者用罪恶的表/余弦对的角度亚太裔的旋转矩阵; / 2 ^N 解决与二分问题）

(edit: use sign of dot product to determine at each step whether to rotate forward or backward. Although if multiplies are cheap enough to allow using dot product, then don't bother with CORDIC, perhaps use a table of sin/cos pairs for rotation matrices of angles π/2ⁿ to solve the problem with bisection.)

（修改我喜欢埃里克Bainville的建议的意见：旋转两个向量趋向于零，并跟踪该角度差）

(edit: I like Eric Bainville's suggestion in the comments: rotate both vectors towards zero and keep track of the angle difference.)

这篇关于便宜的算法找出衡量向量之间的夹角的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！