geometry - 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 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.

Answer 1

If you don't need the actual euclidean angle, but something that you can use as a base for angle comparisons, then changing to taxicab geometry may be a choice, because you can drop trigonometry and it's slowness while MAINTAINING THE ACCURACY (or at least with really minor loosing of accuracy, see below).

In main modern browser engines the speedup factor is between 1.44 - 15.2 and the accuracy is nearly the same as in atan2. Calculating diamond angle is average 5.01 times faster than atan2 and using inline code in Firefox 18 the speedup reaches factor 15.2. Speed comparison: http://jsperf.com/diamond-angle-vs-atan2/2.

The code is very 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)); 
}

The above code gives you angle between 0 and 4, while atan2 gives you angle between -PI and PI as the following table shows:

Note that diamond angle is always positive and in the range of 0-4, while atan2 gives also negative radians. So diamond angle is sort of more normalized. And another note is that atan2 gives a little more precise result, because the range length is 2*pi (ie 6.283185307179586), while in diamond angles it is 4. In practice this is not very significant, eg. rad 2.3000000000000001 and 2.3000000000000002 are both in diamond angles 1.4718731421442295, but if we lower the precision by dropping one zero, rad 2.300000000000001 and 2.300000000000002 gives both different diamond angle. This "precision loosing" in diamond angles is so small, that it has some significant influence only if the distances are huge. You can play with conversions in http://jsbin.com/bewodonase/1/edit?output (Old version: http://jsbin.com/idoyon/1):

The above code is enough for fast angle comparisons, but in many cases there is need to convert diamond angle to radians and vice verca. If you eg. have some tolerance as radian angles, and then you have a 100,000 times loop where this tolerance is compared to other angles, it's not wise to make comparisons using atan2. Instead, before looping, you change the radian tolerance to taxicab (diamond angles) tolerance and make in-loop comparisons using diamond tolerance and this way you don't have to use slow trigonometric functions in speed-critical parts of the code ( = in loops).

The code that makes this conversion is this:

function RadiansToDiamondAngle(rad)
{
  var P = {"x": Math.cos(rad), "y": Math.sin(rad) };
  return DiamondAngle(P.y, P.x);
}  

As you notice there is cos and sin. As you know, they are slow, but you don't have to make the conversion in-loop, but before looping and the speedup is huge.

And if for some reason, you have to convert diamond angle to radians, eg. after looping and making angle comparisons to return eg. the minimum angle of comparisons or whatever as radians, the code is as follows:

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)};
}

Here you use atan2, which is slow, but idea is to use this outside any loops. You cannot convert diamond angle to radians by simply multiplying by some factor, but instead finding a point in taxicab geometry of which diamond angle between that point and the positive X axis is the diamond angle in question and converting this point to radians using atan2.

This should be enough for fast angle comparisons.

Of course there is other atan2 speedup techniques (eg. CORDIC and lookup tables), but AFAIK they all loose accuracy and still may be slower than atan2.

BACKGROUND: I have tested several techniques: dot products, inner products, law of cosine, unit circles, lookup tables etc. but nothing was sufficient in case where both speed and accuracy are important. Finally I found a page in http://www.freesteel.co.uk/wpblog/2009/06/encoding-2d-angles-without-trigonometry/ which had the desired functions and principles.

I assumed first that also taxicab distances could be used for accurate and fast distance comparisons, because the bigger distance in euclidean is bigger also in taxicab. I realized that contrary to euclidean distances, the angle between start and end point has affect to the taxicab distance. Only lengths of vertical and horizontal vectors can be converted easily and fast between euclidean and taxicab, but in every other case you have to take the angle into account and then the process is too slow (?).

So as a conclusion I am thinking that in speed critical applications where is a loop or recursion of several comparisons of angles and/or distances, angles are faster to compare in taxicab space and distances in euclidean (squared, without using sqrt) space.