Méthode numériquement stable de calcul des angles entre les vecteurs

Lors de l'application de la formule classique de l'angle entre deux vecteurs:

α = \arccos \frac{v_{1} \cdot v_{2}}{‖ v_{1} ‖ ‖ v_{2} ‖}

$\alpha = \arccos \frac{\mathbf{v_1} \cdot \mathbf{v_2}}{\|\mathbf{v_1}\| \|\mathbf{v_2}\|}$

on constate que, pour des angles très petits / aigus, il y a une perte de précision et le résultat n'est pas précis. Comme expliqué dans cette réponse Stack Overflow , une solution consiste à utiliser l'arctangente à la place:

α = \arctan 2 (‖ v_{1} \times v_{2} ‖, v_{1} \cdot v_{2})

$\alpha = \arctan2 \left(\|\mathbf{v_1} \times \mathbf{v_2}\|, \mathbf{v_1} \cdot \mathbf{v_2} \right)$

Et cela donne en effet de meilleurs résultats. Cependant, je me demande si cela donnerait de mauvais résultats pour des angles très proches de $\pi / 2$ . Est-ce le cas? Si oui, existe-t-il une formule pour calculer avec précision les angles sans vérifier la tolérance à l'intérieur d'une ifbranche?

algorithms precision numerical-limitations astrojuanlu
la source

Cela dépendra de la mise en œuvre de la fonction tangente inverse à deux paramètres. Les versions lentes et stables basculent conditionnellement entre travailler avec x / y et y / x pour maintenir la précision, tandis que les versions rapides ne font que coller les choses dans le bon quadrant et ne sont donc pas plus précises que la version à un paramètre.

origimbo

Vous devez définir "perte de précision": supposez que la bonne réponse est et vous obtenez à la place . Avez-vous besoin de ou est suffisant?

α

$\alpha$

α + Δ

$\alpha + \Delta$

Δ ≪ α

$\Delta \ll \alpha$

Δ ≪ π

$\Delta \ll \pi$

Stefano M

Dans ce cas, la bonne réponse était et j'ai obtenu , les deux .

α

$\alpha$

α \cdot 10^{8}

$\alpha \cdot 10^8$

≪ 1

$\ll 1$

astrojuanlu

Réponses:

( J'ai déjà testé cette approche et je me souviens qu'elle a fonctionné correctement, mais je ne l'ai pas testée spécifiquement pour cette question. )

Autant que je sache, les deux et peuvent souffrir d'une annulation catastrophique s'ils sont presque parallèles / perpendiculaires - atan2 ne peut pas vous donner une bonne précision si l'une des entrées est désactivée. $\|\mathbf{v}_1\times \mathbf{v}_2\|$ $\mathbf{v}_1\cdot \mathbf{v}_2$

Commencez par reformuler le problème en trouvant l'angle d'un triangle avec des longueurs de côté,et(ils sont tous calculés avec précision en arithmétique à virgule flottante). Il existe une variante bien connue de la formule de Heron en raison de Kahan ( zone de calcul et angles d'un triangle en forme d'aiguille ), qui vous permet de calculer la zone et l'angle (entre et ) d'un triangle spécifié par ses longueurs de côté, et le faire numériquement de manière stable. Étant donné que la réduction de ce sous-problème est également exacte, cette approche devrait fonctionner pour des entrées arbitraires. $a=|\mathbf{v}_1|$ $b=|\mathbf{v}_2|$ $c=|\mathbf{v}_1-\mathbf{v}_2|$ $a$ $b$

Citant cet article (voir p. 3), en supposant , Toutes les parenthèses ici sont placées avec soin, et elles comptent; si vous vous retrouvez à prendre la racine carrée d'un nombre négatif, les longueurs latérales d'entrée ne sont pas les longueurs latérales d'un triangle. $a\geq b$

μ = {\begin{cases} c - (a - b), & if b \geq c \geq 0, \\ b - (a - c), & if c > b \geq 0, \\ invalid triangle, & otherwise \end{cases}

$\mu = \begin{cases} c-(a-b),&\text{if }b\geq c\geq 0,\\ b-(a-c),&\text{if }c>b\geq 0,\\ \text{invalid triangle},&\text{otherwise} \end{cases}$

a n g l e = 2 \arctan (\sqrt{\frac{((a - b) + c) μ}{(a + (b + c)) ((a - c) + b)}})

$\mathrm{angle} = 2\arctan\left( \sqrt{\frac{((a-b)+c)\mu}{(a+(b+c))((a-c)+b)}} \right)$

Le document de Kahan explique comment cela fonctionne, y compris des exemples de valeurs pour lesquelles d'autres formules échouent. Votre première formule pour est à la page 4. $\alpha$ $C''$

La principale raison pour laquelle je suggère la formule de Heron de Kahan est parce qu'elle fait une très belle primitive — beaucoup de questions de géométrie planaire potentiellement délicates peuvent être réduites à trouver l'aire / l'angle d'un triangle arbitraire, donc si vous pouvez réduire votre problème à cela, il y a une belle formule stable pour cela, et il n'est pas nécessaire de trouver quelque chose par vous-même.

Modifier Suite au commentaire de Stefano, j'ai fait un tracé d'erreur relative pour , ( code ). Les deux lignes sont les erreurs relatives pour et , suivant l'axe horizontal. Il semble que ça marche. $v_1=(1,0)$ $v_2=(\cos\theta, \sin\theta)$ $\theta=\epsilon$ $\theta=\pi/2-\epsilon$ $\epsilon$

Kirill
la source

Merci pour le lien et la réponse! Malheureusement, la deuxième formule que j'ai écrite n'apparaît pas dans l'article. En revanche, cette méthode peut devenir un peu complexe, car elle nécessite une projection en 2D.

astrojuanlu

@astrojuanlu Il n'y a pas de projection en 2D ici: quels que soient les deux vecteurs 3D, ils définissent un seul triangle (plan) entre eux - il suffit de connaître ses longueurs latérales.

Kirill

Tu as raison, mon commentaire n'a aucun sens. Je pensais en coordonnées plutôt qu'en longueurs. Merci encore!

astrojuanlu

@astrojuanlu Une dernière chose que je veux noter: il semble qu'il existe une preuve formelle que la formule de l'aire est exacte dans Comment calculer l'aire d'un triangle: une révision formelle , Sylvie Boldo , en utilisant Flocq.

Kirill

Excellente réponse, mais je conteste que vous pouvez toujours calculer avec précision en arithmétique à virgule flottante. En fait, si alors des annulations catastrophiques se produisent dans le calcul des composants de .

c

$c$

c < ϵ \cdot min (a, b)

$c < \epsilon \cdot \min(a,b)$

(v_{1} - v_{2})

$(\mathbf{v}_1-\mathbf{v}_2)$

Stefano M

La réponse efficace à cette question est, sans surprise, dans une autre note de Velvel Kahan :

α = 2 \arctan (‖ \frac{v_{1}}{‖ v_{1} ‖} + \frac{v_{2}}{‖ v_{2} ‖} ‖, ‖ \frac{v_{1}}{‖ v_{1} ‖} - \frac{v_{2}}{‖ v_{2} ‖} ‖)

$\alpha=2\arctan\left(\left\|\frac{\mathbf v_1}{\|\mathbf v_1\|}+\frac{\mathbf v_2}{\|\mathbf v_2\|}\right\|,\left\|\frac{\mathbf v_1}{\|\mathbf v_1\|}-\frac{\mathbf v_2}{\|\mathbf v_2\|}\right\|\right)$

où j'utilise comme l'angle fait par avec l'axe horizontal. (Vous devrez peut-être inverser l'ordre des arguments dans certaines langues.) $\arctan(x,y)$ $(x,y)$

(J'ai donné une démonstration Mathematica de la formule de Kahan ici .)

JM
la source

Vous voulez dire ?

\arctan 2

$\arctan2$

astrojuanlu

J'ai l'habitude de simplement décrire l'arctangente à deux arguments comme , oui. Dans une langue comme FORTRAN, l'équivalent serait .

\arctan (x, y)

$\arctan(x,y)$ ATAN2(Y, X)