如何确定向量是否在两个其他向量之间？

Question

我正在寻找一种快速有效的方法来确定矢量B是否在矢量A和矢量C的小角度之间.通常我会使用垂直点积来确定每条线B的哪一侧所在,但在这种情况下不是如此简单,因为以下内容:

• 没有一个向量可以被假定为标准化,并且将它们标准化是我希望避免的额外步骤.
• 关于哪一侧是最小角度,我没有明确的概念,因此很难说该线的哪一侧是好的.
• A和B有可能是共线的,或者恰好相隔180度,在这种情况下我想要返回false.
• 当我在3D环境中工作时,我很容易将其简化为2D,如果这样可以使事情变得更容易,更重要的是更快.此测试将用于需要尽可能快地运行的算法.

如果有一些简单而有效的方法来确定我的垂直向量应该指向哪个方向,我可以使用两个点产品进行测试.

到目前为止,我一直在考虑的另一种方法是使用矩阵.理论上从我对矩阵变换的理解,我应该能够使用A和C作为基础向量.然后将B乘以矩阵I应该能够通过X和Y是否都为正来测试哪个象限B所在.如果我可以使用这种方法,它可能是最好的,因为一个矩阵乘法应该比两个点积更快,我不应该担心哪一侧有最小角度.

问题来自我的测试我不能简单地使用A和C作为基础并正常乘以它并获得正确的行为.我真的不确定我在这里做错了什么.我已经碰过了几次"矢量空间"这个术语,其中尽可能接近似乎是一个非常类似于矩阵变换的概念,而不需要正交基或正交基.它和矩阵一样吗？如果没有,可能会有更好的方法,我将如何使用它？

只是为了更直观地解释我在说什么:

@Aki Suihkonen我似乎无法让它发挥作用.编写了一个模拟案例,我可以查看,看看我是否无法解决问题

对于这种情况使用

Ax 2.9579773 Ay 3.315979

Cx 2.5879822 Cy 5.1630249

对于围绕四个象限旋转的BI,矢量将空间划分为.

我得到的迹象: - 第一季度-- - 第二季度+- - 第三季度+- - 第四季度--

假设我在环境中旋转的方向与图像相同,我相当确定.

Answer 1

我认为Aki的解决方案很接近,但有些情况下它不起作用:

从他的解决方案:

return (ay * bx - ax * by) * (ay * cx - ax * cy) < 0;

这相当于检查B和A之间的叉积是否与C和A之间的叉积符号相同.

交叉积(U x V)的符号告诉您V是位于U的一侧还是另一侧(板外,进入电路板).在大多数坐标系中,如果U需要逆时针旋转(在板外),则符号将为正.

所以Aki的解决方案检查B是否需要在一个方向上旋转才能到达A,而C需要在另一个方向上旋转.如果是这种情况,则B不在A和C中.当您不知道A和C的"顺序"时,此解决方案不起作用,如下所示:

要确定B是否在A和C范围内,您需要检查两种方式.也就是说,从A到B的旋转方向应该与从A到C的旋转方向相同,从C到B的旋转方向应该与从C到A的旋转方向相同.

这减少到:

if (AxB * AxC >= 0 && CxB * CxA >= 0)

// then B is definitely inside A and C

Answer 2

考虑这一点的一种方法是将所有这些矢量A,B,C视为复数.

将A,C all与B*(B的复共轭)相乘,得到的矢量将在复平面中旋转,使得参考轴(B*Conj(B))现在是实轴(或y = 0) ) - 并且不需要计算该轴.在这种情况下,只需检查'y'或虚构组件的符号是否不同.同样在这种情况下,两个结果矢量都被缩放了相同的长度| B |.

`return sign(Imag(A * Conj(B))) != sign(Imag(C * Conj(B)));`

A = ax + i * ay; B = bx + i * by; C = cx + i * cy;
Conj(B) = bx - i * by; 
A * B = (ax * bx - ay * by) + i * (ax * by + ay * bx);

我认为这个等式可以带来更好的性能,因为只需要乘法的虚部.

作为完整的解决方案,这将转换为:

return (ay * bx - ax * by) * (ay * cx - ax * cy) < 0;

中间乘法是一个捷径:

return Sign(ay * bx - ax * by) != Sign(ay * cx - ax * cy);

没有复数,问题也可以看作矢量B是{R cos beta,R sin beta},它可以表示为旋转矩阵.

R*[  cb -sb ]    [ bx -by ],   cb = cos(beta), sb = sin(beta)
  [  sb  cb ] =  [ by  bx ]    cos(-beta) = cos(beta), sin(-beta) = -sin(beta)

将[ax,ay],[cx,cy]与缩放矩阵[bx by,-by bx] 的转置相乘会影响[ax,ay]*rotMatrix(-beta),[cx,cy]*rotMatrix的长度(-beta)以完全相同的方式.