平面上四点的相对位置

Question

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

在位置1，这四个点可以形成一个凸四边形（即它们的凸包），而在位置2，它们不能形成凸四边形（它们的凸包是三角形）。我的问题是：我如何编写算法来判断这些点是处于位置1还是位置2？（我知道所有四个点的坐标）。

- gonthalo

---

首先，编写一个算法来查找点的凸包。然后，将凸包中的顶点数与平面上的点数进行比较。如果它们相等，则为位置1。如果它们不相等，则为位置2。 - Kevin

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。

- Mark Dickinson