1

如果我有三个点可以创建一个角度，那么确定第四个点是否位于前三个点创建的角度内的最佳方法是什么？

目前，我确定了从原点到所有三个点的线的角度，然后检查测试角度是否在其他两个角度之间，但我正在尝试找出是否有更好的方法来做到这一点. 该功能每次更新都会运行数万次，我希望有更好的方法来实现我想要做的事情。

4

4 回答 4

2

假设您有角度DEF（E是“尖”部分），ED是左光线，EF是右光线。

      * D (Dx, Dy)
     /
    /          * P (Px, Py)
   /
  /
 *---------------*
E (Ex, Ey)       F (Fx, Fy)

步骤 1。ED以经典的Al * x + Bl * y + Cl = 0 形式为线建立线方程，即简单地计算

    Al = Dy - Ey                    // l - for "left"
    Bl = -(Dx - Ex)
    Cl = -(Al * Ex + Bl * Ey)

（注意减法顺序。）

步骤 2。以经典的Ar * x + Br * y + CrFE = 0 形式为线（反向）建立线方程，即简单地计算

    Ar = Ey - Fy                    // r - for "right"
    Br = -(Ex - Fx)
    Cr = -(Ar * Ex + Br * Ey)

（注意减法顺序。）

步骤 3。为您的测试点P计算表达式

    Sl = Al * Px + Bl * Py + Cl
    Sr = Ar * Px + Br * Py + Cr

当且仅当两者Sl和Sr均为正时，您的点位于角度内。如果其中一个为正而另一个为零，则您的点位于相应的侧射线上。

就是这样。

注意 1：要使此方法正常工作，重要的是要确保角度的左右光线确实是左右光线。即，如果您考虑和作为时钟指针，从到的方向应该是顺时针方向。如果不能保证您的输入是这种情况，则需要进行一些调整。例如，它可以作为算法的附加步骤，插入到步骤 2 和 3 之间EDEFDF

步骤 2.5。计算 的值Al * Fx + Bl * Fy + Cl。如果该值为负，则反转所有 ABC 系数的符号：

Al = -Al, Bl = -Bl, Cl = -Cl
Ar = -Ar, Br = -Br, Cr = -Cr

注 2：上述计算是在假设我们在 X 轴指向右侧、Y 轴指向顶部的坐标系中工作的情况下进行的。如果您的坐标轴之一被翻转，您必须反转所有六个 ABC 系数的符号。请注意，顺便说一句，如果您执行上述步骤 2.5 中描述的测试，它将自动处理所有事情。如果您不执行步骤 2.5，那么您必须从一开始就考虑轴方向。

如您所见，这是一种精确的整数方法（没有浮点计算，没有除法）。其代价是溢出的危险。使用适当大小的类型进行乘法运算。

这种方法对于直线方向或实际非反射角的值没有特殊情况：它对锐角、钝角、零角和直角立即起作用。它可以很容易地与反射角一起使用（只需执行补充测试）。

PS+/-符号的四种可能组合Sl和Sr对应于四个扇区，平面由线ED和分割成EF。 

            * D
           / 
   (-,+)  /    (+,+)
         /
 -------*------------* F
       / E
(-,-) /     (+,-)
     /

通过使用这种方法，您可以执行完整的“点落入哪个扇区”测试。对于小于 180 的角度，您碰巧只对这些扇区中的一个感兴趣：(+, +). 如果在某些时候您还需要将此方法调整为反射角（角度大于 180），则必须测试三个扇区而不是一个扇区：(+,+)、(-,+)、(+,-)。

于 2012-07-14T02:52:44.833 回答
1

描述您的原点 O，以及其他 2 个点 A 和 B，然后您的角度为 AOB。现在考虑您的测试点并将其称为 C，如图所示。

在此处输入图像描述

现在考虑我们可以通过取向量 OA 的某个倍数和 OB 的某个倍数来得到 C 的向量方程。明确地

  C = K1 x OA + K2 OB

对于我们需要计算的一些 K1,K2。通过从所有其他点中减去它（矢量地）将 O 设置为原点。如果 A 的坐标是 (a1,a2), B = (b1,b2) 和 C = (c1,c2) 我们有矩阵项

 [ a1 b1 ] [ K1 ] = [ c1 ]
 [ a2 b2 ] [ K2 ] = [ c2 ]

所以我们可以使用矩阵的逆来求解 K1 和 K2

  1 / (a1b2 - b1a2)  [ b2 -b1 ] [ c1 ] = [ K1 ]
                     [ -a2 a1 ] [ c2 ] = [ K2 ]

这减少到

 K1 = (b2c1 - b1c2)/(a1b2 - b1a2)
 K2 = (-a2c1 + a1c2)/(a1b2 - b1a2)

现在如果点 C 在你的角度内，向量 OA 和 OB 的倍数都将为正。如果 C 位于 OB 下方，那么我们需要负量的 OA 才能以类似的方式到达另一个方向。因此，当K1 和 K2 都大于（或等于） zero时，您的条件得到满足。您必须小心，a1b2 = b1a2因为这对应于奇异矩阵并被零除。在几何上，这意味着 OA 和 OB 是平行的，因此没有解决方案。上面的代数可能需要验证任何轻微的拼写错误，但方法是正确的。可能很啰嗦，但您可以简单地从点坐标中获取所有信息，并节省您计算逆三角函数来获取角度的时间。

以上适用于角度 < 180 度，因此如果您的角度大于 180 度，则应改为检查

 !(K1 >= 0 && K2 >= 0)

因为这是在小于 180 度的段的外部。请记住，对于 0 度和 180 度，您将出现除以零的错误，必须检查（确保a1b2 - b1a2 != 0）

于 2012-07-14T01:19:14.240 回答
0

是的，我的意思是我上面评论中的最小角度。查看此线程以广泛讨论找到两个向量之间角度的度量的廉价方法。我在很多场合都使用了查找表方法并取得了巨大的成功。

于 2012-07-12T17:17:31.557 回答
0

三角形 OBC 必须是正向的，三角形 OC A 也是如此。要计算方向，只需使用鞋带公式。两个值都必须是正的。

于 2012-07-14T16:19:30.197 回答