测试点是否在角度内

Question

二维平面中有四个点：O, A, B, P.

O、A、B 定义一个 "angle"，即两条光线，都起源于 O，一条穿过 A，而另一个通过 B。如何判断点P在哪个"side"角上，即是否在两条射线标记的space内？

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

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

编辑：抱歉没有更明确地说明：角度是定向的，即给定 P，它可能位于 O、A、[=13 的右侧=]，但它位于 O、B、A 的左侧。假设三角形 O、A、B 具有顺时针方向。同样，它类似于 "which side of line" 问题：该线是否通过 A、B 或 B、A.[= 也很重要37=]

一个例子：

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

Answer 1

从O看，我们可以将平面分成两个区域或者"sides"。

在逆时针旋转的同时将射线OA扫向射线OB的区域。
其余的，即射线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.

Answer 2

接下来的讨论旨在检测阴影区域内的点。

有两种情况需要考虑：

角AOB小于平面，则点P一定在AO的右边在OB的右边(两个半平面的交点),
角度AOB大于平面，则P点一定在AO的右边或在OB的右边(两个半平面的联合).

完整的布尔表达式为

奥|乙。 (AO|P . OB|P) + ¬ AO|B 。 (AO|P + OB|P),

其中XY|Z表示Z在XY的右边，相当于"XYZ is clockwise"，由三角形面积的符号决定

我认为不可能使表达式更简单，除非您对同一个 AOB 有多个 P。

测试点是否在角度内

Test if point inside angle

algorithm

geometry

2d

computational-geometry