Numerically stable method for angle between 3D vectors Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)How to prove that one formula is numerically better than anotherNumerically stable extraction of Axis-Angle from Unit QuaternionNumerically stable Lanczos process? I need to compute Elements of inverse in sparsity pattern of ANumerically stable way to compute $textTrace[mathbf Amathbf A_1^-1mathbf Bmathbf B_1^-1]$Numerically stable SVDEfficient and stable computation of inverse CDFHow to prove that one formula is numerically better than anotherNumerically stable determinant of matrix productAre these two functions numerically stable?Numerical solution of a system of differential equations with variable coefficientsProof that one cannot calculate the value of an ODE at a point without calculating the previous values
How much damage would a cupful of neutron star matter do to the Earth?
The test team as an enemy of development? And how can this be avoided?
GDP with Intermediate Production
Found this skink in my tomato plant bucket. Is he trapped? Or could he leave if he wanted?
Simple HTTP Server
What does it mean that physics no longer uses mechanical models to describe phenomena?
How can god fight other gods?
Putting class ranking in CV, but against dept guidelines
I got rid of Mac OSX and replaced it with linux but now I can't change it back to OSX or windows
How many time has Arya actually used Needle?
How were pictures turned from film to a big picture in a picture frame before digital scanning?
Is openssl rand command cryptographically secure?
My mentor says to set image to Fine instead of RAW — how is this different from JPG?
malloc in main() or malloc in another function: allocating memory for a struct and its members
Random body shuffle every night—can we still function?
Does silver oxide react with hydrogen sulfide?
A proverb that is used to imply that you have unexpectedly faced a big problem
Can you force honesty by using the Speak with Dead and Zone of Truth spells together?
Does the Black Tentacles spell do damage twice at the start of turn to an already restrained creature?
Is there public access to the Meteor Crater in Arizona?
What order were files/directories output in dir?
Was Kant an Intuitionist about mathematical objects?
One-one communication
What does 丫 mean? 丫是什么意思？
Numerically stable method for angle between 3D vectors
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)How to prove that one formula is numerically better than anotherNumerically stable extraction of Axis-Angle from Unit QuaternionNumerically stable Lanczos process? I need to compute Elements of inverse in sparsity pattern of ANumerically stable way to compute $textTrace[mathbf Amathbf A_1^-1mathbf Bmathbf B_1^-1]$Numerically stable SVDEfficient and stable computation of inverse CDFHow to prove that one formula is numerically better than anotherNumerically stable determinant of matrix productAre these two functions numerically stable?Numerical solution of a system of differential equations with variable coefficientsProof that one cannot calculate the value of an ODE at a point without calculating the previous values
$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:
$$
utimes v = ||u||~||v|| sin(theta) textbfn\
ucdot v = ||u||~||v|| cos(theta)\
theta = arctan2(||utimes v||,~ucdot 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.
numerical-methods numerical-linear-algebra
edited May 12 '16 at 19:07
janmarqz
6,29241630
asked Feb 11 '15 at 11:00
MurphyMurphy
462
$endgroup$
add a comment |
$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:
$$
utimes v = ||u||~||v|| sin(theta) textbfn\
ucdot v = ||u||~||v|| cos(theta)\
theta = arctan2(||utimes v||,~ucdot 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.
numerical-methods numerical-linear-algebra
edited May 12 '16 at 19:07
janmarqz
6,29241630
asked Feb 11 '15 at 11:00
MurphyMurphy
462
$endgroup$
$begingroup$
I guess you mean $2,mathrmatan2(|u/|u|-v/|v||,|u/|u|+v/|v||)$ in method 2?
$endgroup$
– Algebraic Pavel
Feb 11 '15 at 17:53
add a comment |
$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:
$$
utimes v = ||u||~||v|| sin(theta) textbfn\
ucdot v = ||u||~||v|| cos(theta)\
theta = arctan2(||utimes v||,~ucdot 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.
numerical-methods numerical-linear-algebra
edited May 12 '16 at 19:07
janmarqz
6,29241630
asked Feb 11 '15 at 11:00
MurphyMurphy
462
$endgroup$
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:
$$
utimes v = ||u||~||v|| sin(theta) textbfn\
ucdot v = ||u||~||v|| cos(theta)\
theta = arctan2(||utimes v||,~ucdot 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.
numerical-methods numerical-linear-algebra
numerical-methods numerical-linear-algebra
edited May 12 '16 at 19:07
janmarqz
6,29241630
asked Feb 11 '15 at 11:00
MurphyMurphy
462
edited May 12 '16 at 19:07
janmarqz
6,29241630
asked Feb 11 '15 at 11:00
MurphyMurphy
462
edited May 12 '16 at 19:07
janmarqz
6,29241630
edited May 12 '16 at 19:07
janmarqz
6,29241630
edited May 12 '16 at 19:07
janmarqz
6,29241630
6,29241630
asked Feb 11 '15 at 11:00
MurphyMurphy
462
asked Feb 11 '15 at 11:00
MurphyMurphy
462
asked Feb 11 '15 at 11:00
MurphyMurphy
462
462
$begingroup$
I guess you mean $2,mathrmatan2(|u/|u|-v/|v||,|u/|u|+v/|v||)$ in method 2?
$endgroup$
– Algebraic Pavel
Feb 11 '15 at 17:53
add a comment |
$begingroup$
I guess you mean $2,mathrmatan2(|u/|u|-v/|v||,|u/|u|+v/|v||)$ in method 2?
$endgroup$
– Algebraic Pavel
Feb 11 '15 at 17:53
$begingroup$
I guess you mean $2,mathrmatan2(|u/|u|-v/|v||,|u/|u|+v/|v||)$ in method 2?
$endgroup$
– Algebraic Pavel
Feb 11 '15 at 17:53
$begingroup$
I guess you mean $2,mathrmatan2(|u/|u|-v/|v||,|u/|u|+v/|v||)$ in method 2?
$endgroup$
– Algebraic Pavel
Feb 11 '15 at 17:53
add a comment |
1 Answer
1
active
oldest
votes
$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.
answered May 12 '16 at 19:14
D0SBootsD0SBoots
17317
$endgroup$
$begingroup$
What about the common method $arccos(fracu cdot v)$?
$endgroup$
– plasmacel
Aug 17 '17 at 20:48
3
$begingroup$
That's possibly the worst choice for small angles. $fracu cdot v$ approaches 1 for small angles, so you lose most of your precision.
$endgroup$
– D0SBoots
Aug 23 '17 at 4:46
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1143354%2fnumerically-stable-method-for-angle-between-3d-vectors%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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.
answered May 12 '16 at 19:14
D0SBootsD0SBoots
17317
$endgroup$
$begingroup$
What about the common method $arccos(fracu cdot v)$?
$endgroup$
– plasmacel
Aug 17 '17 at 20:48
3
$begingroup$
That's possibly the worst choice for small angles. $fracu cdot v$ approaches 1 for small angles, so you lose most of your precision.
$endgroup$
– D0SBoots
Aug 23 '17 at 4:46
add a comment |
$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.
answered May 12 '16 at 19:14
D0SBootsD0SBoots
17317
$endgroup$
$begingroup$
What about the common method $arccos(fracu cdot v)$?
$endgroup$
– plasmacel
Aug 17 '17 at 20:48
3
$begingroup$
That's possibly the worst choice for small angles. $fracu cdot v$ approaches 1 for small angles, so you lose most of your precision.
$endgroup$
– D0SBoots
Aug 23 '17 at 4:46
add a comment |
$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.
answered May 12 '16 at 19:14
D0SBootsD0SBoots
17317
$endgroup$
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.
answered May 12 '16 at 19:14
D0SBootsD0SBoots
17317
answered May 12 '16 at 19:14
D0SBootsD0SBoots
17317
answered May 12 '16 at 19:14
D0SBootsD0SBoots
17317
answered May 12 '16 at 19:14
D0SBootsD0SBoots
17317
17317
$begingroup$
What about the common method $arccos(fracu cdot v)$?
$endgroup$
– plasmacel
Aug 17 '17 at 20:48
3
$begingroup$
That's possibly the worst choice for small angles. $fracu cdot v$ approaches 1 for small angles, so you lose most of your precision.
$endgroup$
– D0SBoots
Aug 23 '17 at 4:46
add a comment |
$begingroup$
What about the common method $arccos(fracu cdot v)$?
$endgroup$
– plasmacel
Aug 17 '17 at 20:48
3
$begingroup$
That's possibly the worst choice for small angles. $fracu cdot v$ approaches 1 for small angles, so you lose most of your precision.
$endgroup$
– D0SBoots
Aug 23 '17 at 4:46
$begingroup$
What about the common method $arccos(fracu cdot v)$?
$endgroup$
– plasmacel
Aug 17 '17 at 20:48
$begingroup$
What about the common method $arccos(fracu cdot v)$?
$endgroup$
– plasmacel
Aug 17 '17 at 20:48
3
3
$begingroup$
That's possibly the worst choice for small angles. $fracu cdot v$ approaches 1 for small angles, so you lose most of your precision.
$endgroup$
– D0SBoots
Aug 23 '17 at 4:46
$begingroup$
That's possibly the worst choice for small angles. $fracu cdot v$ approaches 1 for small angles, so you lose most of your precision.
$endgroup$
– D0SBoots
Aug 23 '17 at 4:46
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1143354%2fnumerically-stable-method-for-angle-between-3d-vectors%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
I guess you mean $2,mathrmatan2(|u/|u|-v/|v||,|u/|u|+v/|v||)$ in method 2?
$endgroup$
– Algebraic Pavel
Feb 11 '15 at 17:53