多边形的对角线是在里面还是在外面？

Question

我有三个连续的多边形点，例如 p1，p2，p3。现在我想知道p1和p3之间的正交是在多边形内部还是在多边形外部。

我通过取三个向量 v1、v2 和 v3 来做到这一点。多边形中点 p1 之前的点称为 p0。
<代码> v1 = (p0 - p1)
v2 = (p2 - p1)
v3 = (p3 - p1)

参考这个问题，我正在使用该问题的已接受答案中显示的方法。它仅适用于逆时针方向。如果我的点是顺时针方向怎么办？

我也知道我的整个多边形是顺时针或逆时针的。因此我选择向量 v1 和 v2。但我仍然遇到一些问题。我正在展示一个我遇到问题的案例。

这个多边形是逆时针方向的。是从v1和v2的原点开始的。

Answer 1

由于你的点是连续的，你可以通过检查三角形 p1 p2 p3 的方向来解决这个问题。如果方向与多边形的方向相同，则对角线在内部，否则在外部。

要确定三角形的方向，最简单的方法是计算有符号面积并检查符号。计算

p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p2.x * p1.y - p3.x * p2.y - p1.x * p3.y

如果该值的符号为正，则方向为逆时针。如果符号为负，则方向为顺时针方向。

准确地说，上述方法仅提供对角线位于多边形哪一侧的信息。显然，多边形仍然可以在稍后的点与对角线相交。

Answer 2

基本上，对角线可以完全在内部、完全在外部、既在内部又在外部，并且在所有三种情况下都可能与一条或多条边重叠。这使得确定您的需求变得非常简单。

从数学的角度来看，除了外部面积无限大这样的小细节之外，内部和外部实际上没有太大区别。 （至少对于 2D 平面；在球体上，多边形的内部和外部没有明显区分。）

您还有一个关于多边形边的顺序的子问题。最简单的方法是按顺序将相邻边之间的所有角度相加。这总计为 N*(pi/2)。对于 CCW 多边形，N 为正。

[编辑]
一旦你知道了方向，并且如果你没有上面列出的困难情况，那么问题就很简单了。角度p0-p1-p2小于角度p0-p1-p3。因此，边p1-p3至少部分位于多边形外部。如果它没有穿过其他边，那么它显然完全位于多边形之外。

Answer 3

任意两个向量之间的角度是

alpha = acos(v1.x * v2.x + v1.y * v2.y)

因为你现在可以得到之间的角度

v1 and v3 = alpha1; v1 and v2 = alpha2; 

你可以检查 alpha2 是否在 alpha1 之内：

function normalize(a):
    if a > 2 * pi then a - 2 * pi
    else if a < 2 * pi then a + 2 * pi
    else a

alpha1 = normalize(alpha1)
alpha2 = normalize(alpha2)

if (alpha2 < alpha1) then is_between
else is_not_between

这不是很完整，但你应该明白了。

编辑：如果多边形重叠，正如 MSalters 指出的那样，它将不起作用。