Finding the Angle Between Two Vectors

Daron Stinnett (darons@netcom.com), comp.graphics.algorithms, 6 Jan 1994

I am trying to quickly calculate the angle of a given 2D vector expressed in terms of (dx,dy). I am using 16/16 fixed point numbers and my angles are also integers in the range of 0-16K.

I am currently using this algorithm: 

theta = acos( U (dot) V / |U| * |V| )
Since my unit vector (U) is (0,1) the equation ends up looking like this: 

if (POS (dx))
{
    theta = acos (dy/|V|);
}
else
{
    theta = acos (-dy/|V|);
}
What I have is reasonably fast with the exception of the acos call. I cannot afford the time to call the c lib version and I cannot count on a FPU. I have tried to generate a table lookup version of acos but the table is 128K (and that's half the full period!).

Does anyone have any suggestions?

David Eberly (eberly@cs.unc.edu), comp.graphics.algorithms, 7 Jan 1994

You might trying using the CORDIC scheme (COordinate Rotation DIgital Computer = CORDIC), which is a system of finite difference equations that is used to calculate functions on a hand calculator. A decent article on it is in the Amer. Math. Soc. Monthly, "Calculator Function Approximation" by Charles W. Schelin, May 1983, pages 317-325. If you cannot locate the reference, I've got some notes on it (in Latex format) which I can email to you. I have not recently tried to compare the speed of this approach compared to other software implementations for trigonometric functions.

Ron Capelli (capelli@vnet.IBM.COM), comp.graphics.algorithms, 7 Jan 1994

First, avoid square roots in normalizing your vectors by using the arctangent function to determine angles. The atan2(dy,dx) function is the best form for this.

If an approximate angle is acceptable, see: "Fast Approximation to the Arctangent", Graphics Gems II, Academic Press (1991), pp.389-391.

This describes a function that requires only three comparisons and one divide to get an angle measure in the range 0 to 8 (corresponding to 0 to 2*PI) with a max error of about one percent.

Stokes Kevin (kds@phy.duke.edu), comp.graphics.algorithms, 8 Jan 1994

What you really want is to use arctan() Theta= Atan2(x,y); You'll want to save the signs of x & y to get quad #.

Inside your atan2() routine, you'll want to eventually calculate ATAN(y/x)

Make a small table of Atan() values, but use two tricks:

  1. Interpolate between the two nearest table values.
  2. Save the sign infromation from x&y, and the take ABS() of both. Add or subtract 180 degress or change sign etc to restore quadrant info to result.
  3. Have the table only cover from 0 to 1. (y<x) If x > y, then swap x and y, and add 90 degrees to your result.