Numerisch stabile Methode zur Berechnung von Winkeln zwischen Vektoren

Bei Anwendung der klassischen Formel für den Winkel zwischen zwei Vektoren:

α = \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}\|}$

man stellt fest, dass bei sehr kleinen / spitzen Winkeln ein Präzisionsverlust auftritt und das Ergebnis nicht genau ist. Wie in dieser Antwort zum Stapelüberlauf erläutert , besteht eine Lösung darin, stattdessen den Arkustangens zu verwenden:

α = \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)$

Und das ergibt in der Tat bessere Ergebnisse. Ich frage mich jedoch, ob dies bei Winkeln nahe schlechten Ergebnissen führen würde $\pi / 2$ . Ist es der fall Wenn ja, gibt es eine Formel, mit der Winkel genau berechnet werden können, ohne eine Toleranz innerhalb eines ifZweigs zu prüfen ?

algorithms precision numerical-limitations Astrojuanlu
quelle

Dies hängt von der Implementierung der inversen Tangensfunktion mit zwei Parametern ab. Die langsamen, stabilen Versionen wechseln bedingt zwischen der Arbeit mit x / y und y / x, um die Präzision beizubehalten, während die schnellen nur den richtigen Quadranten einhalten und daher nicht genauer sind als die Version mit einem Parameter.

Origimbo

Sie sollten "Genauigkeitsverlust" definieren: Angenommen, die richtige Antwort lautet und Sie erhalten stattdessen

α

$\alpha$

α + Δ

$\alpha + \Delta$ . Benötigen Sie oder ist ausreichend?

Δ ≪ α

$\Delta \ll \alpha$

Δ ≪ π

$\Delta \ll \pi$

Stefano M

In diesem Fall war die richtige Antwort und ich habe , beide .

α

$\alpha$

α \cdot 10^{8}

$\alpha \cdot 10^8$

≪ 1

$\ll 1$

Astrojuanlu

Antworten:

( Ich habe diesen Ansatz bereits getestet und erinnere mich, dass er korrekt funktioniert hat, aber ich habe ihn nicht speziell für diese Frage getestet. )

Soweit ich das beurteilen kann, sind beide und können unter einer katastrophalen Löschung leiden, wenn sie nahezu parallel / senkrecht sind - atan2 kann keine gute Genauigkeit liefern, wenn einer der Eingänge ausgeschaltet ist. $\|\mathbf{v}_1\times \mathbf{v}_2\|$ $\mathbf{v}_1\cdot \mathbf{v}_2$

Beginnen Sie mit einer Neuformulierung des Problems, indem Sie den Winkel eines Dreiecks mit den Seitenlängen,und(Diese werden alle in Gleitkomma-Arithmetik genau berechnet.) Es gibt eine bekannte Variante der Heronschen Formel aufgrund von Kahan ( Fehlberechnungsfläche und Winkel eines nadelförmigen Dreiecks ), mit der Sie die Fläche und den Winkel (zwischen und ) eines Dreiecks berechnen können, die durch seine Seitenlängen angegeben sind. und dies numerisch stabil. Da die Reduktion auf dieses Unterproblem ebenfalls genau ist, sollte dieser Ansatz für beliebige Eingaben funktionieren. $a=|\mathbf{v}_1|$ $b=|\mathbf{v}_2|$ $c=|\mathbf{v}_1-\mathbf{v}_2|$ $a$ $b$

Zitiert aus diesem Artikel (siehe S.3), unter der Annahme, dass , Alle Klammern hier sind sorgfältig gesetzt, und sie sind wichtig; Wenn Sie feststellen, dass Sie die Quadratwurzel einer negativen Zahl ziehen, sind die eingegebenen Seitenlängen nicht die Seitenlängen eines Dreiecks. $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)$

Wie dies funktioniert, wird in Kahans Aufsatz erklärt, einschließlich Beispielen für Werte, für die andere Formeln versagen. Ihre erste Formel für lautet auf Seite 4. $\alpha$ $C''$

Der Hauptgrund, warum ich Kahans Herons Formel vorschlage, ist, dass sie ein sehr nettes Primitiv darstellt - viele potenziell knifflige Fragen der planaren Geometrie können auf das Finden der Fläche / des Winkels eines beliebigen Dreiecks reduziert werden eine schöne stabile Formel dafür, und es ist nicht nötig, sich selbst etwas auszudenken.

Bearbeiten Nach Stefanos Kommentar habe ich eine Darstellung des relativen Fehlers für , ( Code ) erstellt. Die zwei Linien sind die relativen Fehler für und ;, wobei entlang der horizontalen Achse verläuft. Es scheint, dass es funktioniert. $v_1=(1,0)$ $v_2=(\cos\theta, \sin\theta)$ $\theta=\epsilon$ $\theta=\pi/2-\epsilon$ $\epsilon$

Kirill
quelle

Danke für den Link und die Antwort! Leider erscheint die zweite Formel, die ich geschrieben habe, nicht im Artikel. Andererseits kann diese Methode etwas komplex werden, da eine Projektion in 2D erforderlich ist.

Astrojuanlu

@astrojuanlu Hier gibt es keine Projektion auf 2d: Unabhängig von den beiden 3D-Vektoren definieren sie ein einziges (planares) Dreieck zwischen sich - Sie müssen nur die Seitenlängen kennen.

Kirill

Sie haben recht, mein Kommentar macht keinen Sinn. Ich habe in Koordinaten statt in Längen gedacht. Danke noch einmal!

Astrojuanlu

@astrojuanlu Eine weitere Sache , ich anmerken möchte: Es scheint , dass es einen formalen Beweis ist , dass der Bereich Formel in genau Wie Berechne die Fläche eines Dreiecks: a Formal Revisit , Sylvie Boldo , mit Flocq.

Kirill

c

$c$

c < ϵ \cdot min (a, b)

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

(v_{1} - v_{2})

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

Die effiziente Antwort auf diese Frage findet sich nicht allzu überraschend in einer weiteren Anmerkung von 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)$

$\arctan(x,y)$ $(x,y)$

(Ich habe eine Mathematica Demonstration von Kahan Formel hier .)

JM
quelle

\arctan 2

$\arctan2$

\arctan (x, y)

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