使用针状三角形计算两个向量之间的角度

Calculating the angle between two vectors using a needle-like triangle

提问人:FirefoxMetzger 提问时间:10/5/2021 最后编辑:FirefoxMetzger 更新时间:10/6/2021 访问量:200

问:

我实现了一个函数()来计算两个向量之间的角度。它利用针状三角形,并基于针状三角形的错误计算面积和角度以及这个相关问题angle_between

该函数似乎大部分时间都工作正常,除了一个奇怪的情况,我不明白发生了什么:

import numpy as np
vectorA = np.array([0.008741225033460295, 1.1102230246251565e-16], dtype=np.float64)
vectorB = np.array([1, 0], dtype=np.float64)
angle_between(vectorA, vectorB)  # is np.nan

深入研究我的函数,它是通过取负数的平方根产生的,负数似乎是该方法精度提高的结果:np.nan

foo = 1.0                  # np.linalg.norm(vectorA)
bar = 0.008741225033460295 # np.linalg.norm(vectorB)
baz = 0.9912587749665397   # np.linalg.norm(vectorA- vectorB)

# algebraically equivalent ... numerically not so much
order1 = baz - (foo - bar)
order2 = bar - (foo - baz)

assert order1 == 0
assert order2 == -1.3877787807814457e-17

根据 Kahan 的论文,这意味着三元组(foo、bar、baz)实际上并不代表三角形的边长。但是,考虑到我如何构造三角形,这应该是这种情况(请参阅代码中的注释)。

从这里开始,我对在哪里寻找错误的来源感到有点迷茫。有人可以向我解释发生了什么吗?


为了完整起见,以下是我的函数的完整代码:

import numpy as np
from numpy.typing import ArrayLike

def angle_between(
    vec_a: ArrayLike, vec_b: ArrayLike, *, axis: int = -1, eps=1e-10
) -> np.ndarray:
    """Computes the angle from a to b

    Notes
    -----
    Implementation is based on this post:
    https://scicomp.stackexchange.com/a/27694
    """

    vec_a = np.asarray(vec_a)[None, :]
    vec_b = np.asarray(vec_b)[None, :]

    if axis >= 0:
        axis += 1

    len_c = np.linalg.norm(vec_a - vec_b, axis=axis)
    len_a = np.linalg.norm(vec_a, axis=axis)
    len_b = np.linalg.norm(vec_b, axis=axis)

    mask = len_a >= len_b
    tmp = np.where(mask, len_a, len_b)
    np.putmask(len_b, ~mask, len_a)
    len_a = tmp

    mask = len_c > len_b
    mu = np.where(mask, len_b - (len_a - len_c), len_c - (len_a - len_b))

    numerator = ((len_a - len_b) + len_c) * mu
    denominator = (len_a + (len_b + len_c)) * ((len_a - len_c) + len_b)

    mask = denominator > eps
    angle = np.divide(numerator, denominator, where=mask)
    np.sqrt(angle, out=angle)
    np.arctan(angle, out=angle)
    angle *= 2
    np.putmask(angle, ~mask, np.pi)
    return angle[0]

编辑:当使用较大的浮点数执行计算时,该问题肯定与此相关并消失:float64

import numpy as np

vectorA = np.array([0.008741225033460295, 1.1102230246251565e-16], dtype=np.float128)
vectorB = np.array([1, 0], dtype=np.float128)
assert angle_between(vectorA, vectorB) == 0
python numpy 几何图形 数字 浮点精度

评论

0赞 Lukas S 10/6/2021
回想一下,如果 3 条边满足强三角形不等式,则它们组成一个三角形,即两条短边的总和必须严格大于长边。但对你来说不是这样,因为.bar + baz == 1 == foo
0赞 FirefoxMetzger 10/6/2021
我猜@user2640045来自浮点不准确?三个向量的长度 , 应该始终形成一个有效的三角形,不是吗?除此之外,函数应正确处理 和 的两种退化情况。前者为 0,后者为 。bar + baz == 1 == foovectorAvectorBvectorA - vectorBvectorA == vectorBvectorA == -vectorBlen_cnp.putmask(angle, ~mask, np.pi)
0赞 Lukas S 10/6/2021
不,当向量 A 和向量 B 是彼此的倍数时,也会出现这种情况。这里几乎就是这种情况。如果我用零代替。他们会的。我想与零的差异不足以避免这个问题。1.1102230246251565e-161.1102230246251565e-16
0赞 FirefoxMetzger 10/6/2021
@user2640045 我刚刚尝试了设置为倍数的情况 - 有趣的是 - 它有时会产生 ,有时 有时它失败并产生一个小的量级角......有什么想法为什么吗?vectorBvectorAnan01e-8

答:

2赞 Lukas S 10/6/2021 #1

我刚刚尝试了将 vectorB 设置为向量 A 的倍数的情况,有趣的是 - 它有时产生 nan,有时产生 0,有时它失败并产生一个 1e-8 大小的小角度......有什么想法为什么吗?

是的,我认为这就是你的问题归结为什么。这是伯克利论文中的公式,由于你一直在使用Kahan。angle formula假设 ,(只有这样公式才有效)和 。 如果我们忽略一秒钟,看看平方根下的其他一切,它一定都是正的,因为这是最长的边。并且是.如果该错误为零,则得到零,顺便说一句。正确的结果。如果误差为负数,则平方根为您提供 nan,如果误差为正,则得到一个小角度。a≥ba≥cb+c≈amuamuc-(a-b)0 ± a small error

请注意,当非零但小于误差时,相同的参数有效。b+c-a

评论

0赞 Lukas S 10/6/2021
@wikikikitiki 我们昨天才谈到这一点,是不是很奇怪?
0赞 FirefoxMetzger 10/6/2021
嗯,在这种情况下,避免的首选方法是什么?我想到的两种策略是:(1) 在 0 处剪辑,或 (2) 将其设置为如果它靠近它。然而,我对此没有很好的动机,除了他们觉得很自然。nanmu0eps
0赞 Lukas S 10/6/2021
你检查一下强三角形不等式是否成立怎么样。如果不是,即 a≈b+c,如果 vec_a 和 vec_b 在 pi 上指向同一方向,则返回 0,如果它们指向相反的方向,则返回 180°。您可以确定它们是否与点积指向同一方向。如果它是正数,它们指向同一个方向,如果它是负数,则指向相反的方向。
0赞 Lukas S 10/6/2021
@FirefoxMetzger顺便说一句,您还可以检查向量是否与线性无关(这是等效的)。也许这样说会更合理:我的向量是线性依赖的,它们必须形成 0 或 pi/180° 的角度。编辑:但想想看。前者可能更好,因为你知道如果 a、b、c 满足强三角形不等式,你的公式就会起作用。既然论文这么说,你就不必担心数字,那就:)。