algorithm - 测试点是否在角度内

Question

在二维平面中有四个点:O、A、B、P。

O, A, B 定义了一个“角度”，即两条射线，都起源于 O ，一个通过 A，而另一个通过 B。如何判断点 P 位于角度的哪“边”，即它是否在两条射线标记的空间内？

请注意，点是任意放置的，即角度的大小可能大于 π。

这类似于确定一个点位于线的哪一侧的问题，如讨论的那样。在 comp.graphics.algorithms FAQ (课题 1.02:如何求点到线的距离？)，但这里是两条射线，而不是一条线。

编辑:抱歉没有更明确地说明:角度是定向的，即给定 P，它可能位于 O、A< 的右侧, B，但是它在O, B, A 的左边。假设三角形 O、A、B 具有顺时针方向。同样，它类似于“线的哪一侧”问题:线是否穿过 A、B 或 B 也很重要>，A。

一个例子:

        \                               \
         A                               B
          \   right                       \    left
   left    \                      right    \
            O------B----                    O------A----

Answer 1

当从 O 看时，我们可以将平面分成两个区域或“边”。

1. 在逆时针旋转的同时将射线 OA 扫向射线 OB 的区域。
2. 其余的，即射线 OB 逆时针扫描到 OA。

要检查该点是否在哪个区域，您可以使用

// if isInRegion(O, A, B) is true, P is in the first region.
// otherwise, isInRegion(O, B, A) will be true.
bool isInRegion(O, A, B, P) {
    return isCCW(O, A, P) && !isCCW(O, B, P)
}

// ref: http://www.cs.cmu.edu/%7Equake/robust.html
// For more robust methods, see the link.
bool isCCW(a, b, c) {
    return ((a.x - c.x)*(b.y - c.y) - (a.y - c.y)*(b.x - c.x)) > 0;
}

I tried it here.