Tuesday 31 January 2012

Angle between two vectors

Another use for inverse trigonometric functions is finding the angle between two vectors. Again there is more than one way to do it, and again the most straightforward approach is often not the best.


The vectors are two dimensional, but as before they are supplied as separate numeric values, in preference to a vector class. The code can easily be adapted to work with vectors or any class which supplies positions.


The first, straightforward, approach is as follows.


function AngleBetween1(x1:Number, y1:Number, x2:Number, y2:Number):Number {
    var fDotProduct:Number = x1 * x2 + y1 * y2;
    var fNorm1:Number = Math.sqrt(x1 * x1 + y1 * y1);
    var fNorm2:Number = Math.sqrt(x2 * x2 + y2 * y2);
    return Math.acos(fDotProduct / (fNorm1 * fNorm2));
}


This derives naturally from the definition of the dot product, as it can be used to define the angle, especially in higher dimensions, using the following formula




The above function derives straightforwardly from this formula. But it has a number of problems:

  • It is expensive, with two sqrt functions as well as the acos
  • It is inaccurate for small angles, so for near-parallel vectors
  • For parallel vectors it sometimes give an error, if rounding errors make the fraction passed to acos greater than one. This needs handling with an additional step
  • It doesn't return a signed angle, so there's no sense of the direction of rotation
The cost can be reduced by multiplying before taking a single sqrt, but the other issues are difficult to avoid without additional calculations and special-case code. But there is another way that deals with all of the issues.

function AngleBetween2(x1:Number, y1:Number, x2:Number, y2:Number):Number {
    var fDotProduct:Number = x1 * x2 + y1 * y2;
    var fPerpDotProduct:Number = x1 * y2 - y1 * x2;
    return Math.atan2(fPerpDotProduct, fDotProduct);
}

This works because the atan2 function takes two parameters, so has more information to calculate the correct result. The result is signed so can be positive or negative, up to ±π / ±180°, useful for determining the direction of rotation. It is accurate over the entire range unlike acos or asin. And because the vectors don't need normalising, and the various other problems don't need coding around, it is much more efficient.

A final benefit of the above approach is the numbers passed to Math.atan2 can be thought of as a complex number. Normalised it can be used to perform rotations directly, using e.g. the rotation function I described a month ago, avoiding angles altogether.

No comments:

Post a Comment