algorithm - 平面中四点的相对位置

Question

平面上四个点有两个不同的相对位置:

在位置 1 中，四个点可以形成一个凸四边形(即它们的 convex hull )，而在位置 2 中，它们不能(它们的凸包是三角形)。我的问题是:如何编写算法来确定这些点是在位置 1 还是位置 2？ (我知道所有四个点的坐标)。

Answer 1

对于平面中的任意三点 P、Q 和 R(不共线)，您可以通过查看数量的符号来确定角度 P-Q-R 是逆时针还是顺时针:

(P[0] - R[0]) * (Q[1] - R[1]) - (P[1] - R[1]) * (Q[0] - R[0])

其中 P[0] 和 P[1] 分别指 P 的 x 坐标和 y 坐标，Q 和 R 也类似。

现在将您的四个点命名为 P1、P2、P3 和 P4，并为四个三元组 (P1, P2, P3)、(P1, P2, P4)、(P1, P3, P4) 和(P2, P3, P4)(这里要注意:上面表达式中点(P，Q，R)的顺序很重要)。如果所有符号都相等，或者有两个正号和两个负号，则凸包是一个四边形。如果有三个正号和一个负号(或相反)，则您的四个点的凸包是三角形。或者更简单地说，如果您的符号表示为 +1 和 -1，则将四个符号相乘。如果乘积为+1，则为四边形；如果 -1，则属于三角情况。

以上假设四点中没有三点共线；我留给你来列举退化的情况。

由于这是 StackOverflow，这里有一些代码(Python 语言)。首先是 ccw 的定义(使用 sign 辅助函数)。

def sign(x):
    """ Return the sign of a finite number x. """
    if x > 0:
        return 1
    elif x < 0:
        return -1
    else:
        return 0

def ccw(P, Q, R):
    """ Return 1 if P-Q-R is a counterclockwise turn, -1 for clockwise,
        and 0 if the points are collinear (or not all distinct). """
    disc = (P[0] - R[0]) * (Q[1] - R[1]) - (P[1] - R[1]) * (Q[0] - R[0])
    return sign(disc)

然后是四元组点的分类。

def classify_points(P, Q, R, S):
    """ Return 1 if the convex hull of P, Q, R and S is a quadrilateral,
        -1 if a triangle, and 0 if any three of P, Q, R and S are
        collinear (or if not all points are distinct). """
    return ccw(P, Q, R) * ccw(P, Q, S) * ccw(P, R, S) * ccw(Q, R, S)

一个简单的测试:一个正方形应该被分类为结果 1。

>>> # Test case 1: quadrilateral convex hull
>>> P = 0, 0
>>> Q = 0, 1
>>> R = 1, 0
>>> S = 1, 1
>>> classify_points(P, Q, R, S)
1

还有一个结果为 -1 的三角形。

>>> # Test case 2: triangle.
>>> P = 0, 0
>>> Q = 0, 3
>>> R = 3, 0
>>> S = 1, 1
>>> classify_points(P, Q, R, S)
-1

这是一个退化的情况(P、Q 和 S 共线):

>>> P = 1, 1
>>> Q = 2, 2
>>> R = 5, 7
>>> S = 4, 4
>>> classify_points(P, Q, R, S)
0

请注意，如果您使用的是不精确的浮点运算，数值错误可能会导致接近退化的情况被归类为退化，反之亦然。

为证明上述内容:很容易检查交换 ccw 定义中的任意两个输入是否反转结果的符号，以及交换 classify_points 中的任意两个输入> 定义保留产品的标志不变。所以我们可以任意重新排序点，影响 classify_points 结果。

现在假设 P1、P2、P3 和 P4 有一个四边形凸包。然后通过上述观察，我们可以重新排列点，假设 P1、P2、P3 和 P4 以逆时针顺序绕过该四边形的边界。那么每个ccw表达式都是1，所以classify_points的结果是1。类似地，如果 P1、P2、P3 和 P4 具有三角形凸包，我们可以重新排列，使 P1、P2 和 P3 绕三角形边界逆时针旋转，而 P4 在三角形内，在这种情况下，ccw 符号是 1、1、-1 和 1。