15
$\begingroup$

I'm looking for a numerically stable method for computing the angle between two 3D vectors. Which of the following methods ought to be preferred?

Method 1: $$ u\times v = ||u||~||v|| \sin(\theta) \textbf{n}\\ u\cdot v = ||u||~||v|| \cos(\theta)\\ \theta = \arctan2(||u\times v||,~u\cdot v) $$

Method 2:

$$ \theta = 2~\arctan2(||u/||u|| - v/||v||~||,~||u/||u|| + v/||v||~||) $$

where method 2 is based on the fact that the sum and difference vectors of two unit (or equal length) vectors are orthogonal.

Or is there an even better method which I haven't thought of? The vectors I am considering have angles typically smaller than 2 degrees.

$\endgroup$
1
  • $\begingroup$ I guess you mean $2\,\mathrm{atan2}(\|u/\|u\|-v/\|v\|\|,\|u/\|u\|+v/\|v\|\|)$ in method 2? $\endgroup$ Feb 11, 2015 at 17:53

1 Answer 1

15
$\begingroup$

Short answer: Method 2 is better for small angles. Use this slight rearrangement: $$ \theta = 2~atan2(||~||v||u - ||u||v~||,~||~||v||u + ||u||v~||) $$

This formula comes from W. Kahan's advice in his paper "How Futile are Mindless Assessments of Roundoff in Floating-Point Computation?" (https://www.cs.berkeley.edu/~wkahan/Mindless.pdf), section 12 "Mangled Angles."

Before I found that paper, I also did my own analysis, comparing the double-precision results with result's using bc with 50 digits of precision. Method 2 is commonly within 1 ulp of correct, and almost always within 50 ulps, whereas Method 1 was much, much less accurate.

This might seem surprising, since Method 1 is mathematically insensitive to the magnitude of u and v, whereas they have to be normalized in Method 2. And indeed, the accuracy of the normalization is the limiting factor for Method 2 - virtually all the error comes from the fact that even after normalization, the vectors aren't exactly length 1.

However, for small angles you get catastrophic cancellation in the cross product for method 1. Specifically, all the products like $u_y v_z - u_z v_y$ end up close to 0, and I believe the cross-multiplication before the subtraction loses accuracy, compared to the direct subtraction in Method 2.

$\endgroup$
3
  • $\begingroup$ What about the common method $\arccos(\frac{u \cdot v}{|| u || || v ||})$? $\endgroup$
    – plasmacel
    Aug 17, 2017 at 20:48
  • 4
    $\begingroup$ That's possibly the worst choice for small angles. $\frac{u \cdot v}{||u||||v||}$ approaches 1 for small angles, so you lose most of your precision. $\endgroup$
    – D0SBoots
    Aug 23, 2017 at 4:46
  • $\begingroup$ @D0SBoots I came to this question and your answer because I was indeed in crossroads trying to understand which algorithm should I use. You mention "catastrophic cancellation in the cross product" and also "ulp" (unit of least precision?) but I would like to realize these on my end. I've made this question: stackoverflow.com/questions/77610266/… And would like to grasp why indeed Method2 is better than Method1, even though I'm more biased towards Method1. Thanks $\endgroup$
    – probiner
    Dec 6, 2023 at 4:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .