Maneira numericamente estável de calcular ângulos entre vetores

Ao aplicar a fórmula clássica para o ângulo entre dois vetores:

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

verifica-se que, para ângulos muito pequenos / agudos, há uma perda de precisão e o resultado não é exato. Conforme explicado nesta resposta de estouro de pilha , uma solução é usar o arco tangente:

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

E isso realmente dá melhores resultados. No entanto, gostaria de saber se isso daria resultados ruins para ângulos muito próximos de $\pi / 2$ . É esse o caso? Em caso afirmativo, existe alguma fórmula para calcular com precisão ângulos sem verificar se há tolerância dentro de um ifgalho?

algorithms precision numerical-limitations astrojuanlu
fonte

Isso vai depender da implementação da função tangente inversa de dois parâmetros. As versões lentas e estáveis alternam condicionalmente entre trabalhar com x / ye y / x para manter a precisão, enquanto as mais rápidas colocam as coisas no quadrante certo e, portanto, não são mais precisas que a versão de um parâmetro.

origimbo

Você deve definir "perda de precisão": suponha que a resposta correta seja e obtenha . Você precisa de ou ?

α

$\alpha$

α + Δ

$\alpha + \Delta$

Δ ≪ α

$\Delta \ll \alpha$

Δ ≪ π

$\Delta \ll \pi$

Stefano M

Nesse caso, a resposta correta foi e eu recebi , ambos .

α

$\alpha$

α \cdot 10^{8}

$\alpha \cdot 10^8$

≪ 1

$\ll 1$

Astrojuanlu

Respostas:

( Eu testei essa abordagem antes e lembro que funcionou corretamente, mas não a testei especificamente para esta pergunta. )

Até onde eu sei, tanto e podem sofrer um cancelamento catastrófico se forem quase paralelos / perpendiculares - o atan2 não poderá fornecer boa precisão se uma das entradas estiver desativada. $\|\mathbf{v}_1\times \mathbf{v}_2\|$ $\mathbf{v}_1\cdot \mathbf{v}_2$

Comece reformulando o problema ao encontrar o ângulo de um triângulo com comprimentos laterais,e(todos são calculados com precisão na aritmética de ponto flutuante). Há uma variante bem conhecida de fórmula de Heron devido a Kahan ( Área miscalculating e ângulos de uma forma de agulha do triângulo ), que permite calcular a área e o ângulo (entre e ) de um triângulo especificado pelos seus comprimentos laterais, e faça isso numericamente de maneira estável. Como a redução desse subproblema também é precisa, essa abordagem deve funcionar com entradas arbitrárias. $a=|\mathbf{v}_1|$ $b=|\mathbf{v}_2|$ $c=|\mathbf{v}_1-\mathbf{v}_2|$ $a$ $b$

Citando esse artigo (consulte a p.3), assumindo , Todos os parênteses aqui são colocados com cuidado e são importantes; se você encontrar a raiz quadrada de um número negativo, os comprimentos dos lados de entrada não serão os comprimentos laterais de um triângulo. $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)$

Há uma explicação de como isso funciona, incluindo exemplos de valores para os quais outras fórmulas falham, no artigo de Kahan. Sua primeira fórmula para é na página 4. $\alpha$ $C''$

A principal razão pela qual sugiro a fórmula de Kahan Heron é porque ela é uma primitiva muito boa - muitas questões de geometria planar potencialmente complicadas podem ser reduzidas para encontrar a área / ângulo de um triângulo arbitrário; portanto, se você pode reduzir seu problema a isso, existe uma boa fórmula estável para isso, e não há necessidade de criar algo por conta própria.

Editar Após o comentário de Stefano, fiz um gráfico de erro relativo para , ( código ). As duas linhas são os erros relativos de e , ao longo do eixo horizontal. Parece que funciona. $v_1=(1,0)$ $v_2=(\cos\theta, \sin\theta)$ $\theta=\epsilon$ $\theta=\pi/2-\epsilon$ $\epsilon$

Kirill
fonte

Obrigado pelo link e pela resposta! Infelizmente, a segunda fórmula que escrevi não aparece no artigo. Por outro lado, esse método pode ser um pouco complexo, pois requer projeção em 2D.

Astrojuanlu 23/08/19

@astrojuanlu Não há projeção para 2d aqui: quaisquer que sejam os dois vetores 3d, eles definem um único triângulo (plano) entre eles - você só precisa saber os comprimentos laterais.

22917 Kirill

Você está certo, meu comentário não faz sentido. Eu estava pensando em coordenadas em vez de comprimentos. Obrigado novamente!

Astrojuanlu

@astrojuanlu Mais uma coisa que quero observar: parece que há uma prova formal de que a fórmula da área é precisa em Como calcular a área de um triângulo: uma revisão formal , Sylvie Boldo , usando Flocq.

22917 Kirill

Excelente resposta, mas discuto que você sempre pode calcular com precisão na aritmética de ponto flutuante. De fato, se ocorrerão cancelamentos catastróficos na computação dos componentes de .

c

$c$

c < ϵ \cdot min (a, b)

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

(v_{1} - v_{2})

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

23417 Stefano M

A resposta eficiente a esta pergunta está, não surpreendentemente, em outra nota 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)$

onde eu uso como o ângulo feito por com o eixo horizontal. (Talvez você precise inverter a ordem dos argumentos em alguns idiomas.) $\arctan(x,y)$ $(x,y)$

(Fiz uma demonstração do Mathematica da fórmula de Kahan aqui .)

JM
fonte

Você quer dizer ?

\arctan 2

$\arctan2$

Astrojuanlu #

Estou acostumado a apenas descrever o arco de dois argumentos como , sim. Em um idioma como FORTRAN, o equivalente seria .

\arctan (x, y)

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