Cheap algorithm to find measure of angle between vectors

Question

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 divide's should be limited as much as possible.

Fortunately, I do not need the angle perse, 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.

Any help is appreciated.

Jeroen

Answer 1

The solution would be trivial if the vectors were defined/stored using polar coordinates instead of cartesian coordinates (or, 'as well as' using cartesian coordinates).

Answer 2

The dot product might work in your case. It's not proportional to the angle, but "related".

Answer 3

Back in the day of a few K of RAM and machines with limited mathematical capabilities I used lookup tables and linear interpolation. The basic idea is simple: create an array with as much resolution as you need (more elements reduce the error created by interpolation). Then interpolate between lookup values.

Here is an example in processing: http://processing.org/hacks/hacks%3Asincoslookup

You can do this with your other trig functions as well. On the 6502 processor this allowed for full 3D wire frame graphics to be computed with an order of magnitude speed increase.

Answer 4

dot product of two vectors (x1, y1) and (x2, y2) is

x1 * x2 + y1 * y2

and is equivilent to the product of the lengths of the two vectors times the cosine of the angle between them.

So if you normalize the two vectors first (divide the coordinates by the length)

Where length of V1 L1 = sqrt(x1^2 + y1^2),  
  and length of V2 L2 = sqrt(x2^2 + y2^2),

Then normalized vectors are

(x1/L1, y1/L1),  and (x2/L2, y2/L2),

And dot product of normalized vectors (which is the same as the cosine of angle between the vectors) would be

 (x1*x2 + y1*y2)
 -----------------
     (L1*L2)

of course this may be just as computationally difficult as calculating the cosine

Answer 5

if you need to compute the square root, then consider using the invsqrt hack.

acos((x1*x2 + y1*y2) * invsqrt((x1*x1+y1*y1)*(x2*x2+y2*y2)));