14

我正在寻找一种快速有效的方法来确定向量 B 是否在向量 A 和向量 C 的小角度之间。通常我会使用垂直点积来确定每条线 B 的哪一侧，但在这种情况下不是如此简单，原因如下：

  • 没有一个向量可以被认为是规范化的，规范化它们是我希望避免的额外步骤。
  • 我不清楚哪一边是最小的角度，所以很难说哪一边是好还是不好。
  • A 和 B 可能是共线的或正好相隔 180 度，在这种情况下我想返回 false。
  • 当我在 3D 环境中工作时，我很容易将其简化为 2D，如果这样可以让事情变得更容易，更重要的是更快。该测试将用于需要尽可能快地运行的算法。

如果有一些简单有效的方法来确定我的垂直向量应该指向哪个方向，我可以使用这两个点积进行测试。

到目前为止，我一直在考虑但没有取得多大成功的另一种方法是使用矩阵。理论上，根据我对矩阵变换的理解，我应该能够使用 A 和 C 作为基向量。然后将 B 乘以矩阵 I 应该能够通过 X 和 Y 是否都为正来测试 B 所在的象限。如果我能让这种方法发挥作用，它可能是最好的，因为一个矩阵乘法应该比两个点积快，而且我不必担心哪一边的角度最小。

问题出在我的测试中，我不能简单地使用 A 和 C 作为基础并将其正常相乘并获得正确的行为。我真的不确定我在这里做错了什么。我已经多次遇到“向量空间”这个术语，据我所知，它似乎是一个与矩阵变换非常相似的概念，不需要正交基或正交基。它和矩阵一样吗？如果没有，是否有更好的方法，我将如何使用它？

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

粗略的例子

@Aki Suihkonen 我似乎无法让它工作。编写了一个我可以通过的模拟案例，看看我是否无法弄清楚

对于这种情况，使用

斧头 2.9579773 Ay 3.315979

Cx 2.5879822 Cy 5.1630249

对于围绕四个象限旋转的 BI，向量将空间划分为。

我得到的迹象： - Q1 -- - Q2 +- - Q3 +- - Q4--

假设我在环境中以与图像相同的方向旋转，我很确定我做了。

象限

4

3 回答 3

16

我认为 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
于 2013-07-05T21:56:26.280 回答
6

考虑这一点的一种方法是将所有这些向量 A、B、C 视为复数。

将 A、C 全部与 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) 以完全相同的方式。

于 2012-11-30T07:52:34.663 回答
0

In polar coordinates, you would just be asking if θA < θB < θC. So transform to polar first:

a_theta = ax ? atan(ay / ax) : sign(ay) * pi
于 2012-11-30T10:33:18.533 回答