检测更改点时三角形是否翻转

Question

我需要通过更改三角形的一个点来改变这个三角形。不过，我需要先判断这样做是否会导致三角形翻转。

比如，下面这个由点定义的三角形：

[(1.0,1.0), (2.0,3.0), (3.0,1.0)]

看起来是这样的：

如果我把第三个点从 (3.0,1.0) 改成 (1.0,2.0)，它就会翻转，如下所示：

我写了一个函数来检测三角形是否翻转，方法是计算静止点的方程，并检查y轴截距的符号是否不同：

def would_flip(stationary, orig_third_point, candidate_third_point):

    #m = (y2-y1)/(x2-x1)
    slope = (stationary[1][3] - stationary[0][4]) / (stationary[1][0] - stationary[0][0])

    #y = mx + b
    #b = y-mx
    yint = stationary[0][5] - slope * stationary[0][0]

    orig_atline = slope * orig_third_point[0] + yint
    candidate_atline = slope * candidate_third_point[0] + yint

    if orig_atline > orig_third_point[1] and not(candidate_atline > candidate_third_point[1]) or \
        orig_atline < orig_third_point[1] and not(candidate_atline < candidate_third_point[1]):
        return True

    return False

这个方法在大多数情况下都很好用：

>>> would_flip([(1.0,1.0), (2.0,3.0)], (3.0,1.0), (1.0,2.0))
True
>>> would_flip([(1.0,1.0), (2.0,3.0)], (3.0,1.0), (4.0,2.0))
False

但我遇到的问题是，如果静止点是垂直的，斜率就会变成无穷大：

>>> would_flip([(1.0,1.0), (1.0,3.0)], (3.0,1.0), (4.0,2.0))
ZeroDivisionError: float division by zero

有没有更好或更快的方法来检测三角形翻转，特别是当静止点形成一条垂直线时？用Python写的并不重要。我也接受仅仅是公式或描述清楚的技术的答案。

补充说明：三角形“翻转”的意思是什么

看看下面这四个三角形：

左上角的是原始三角形。红线（在四个三角形中都是一样的）是两个静止点。其余三个三角形则替换了第三个点。右上角和左下角的三角形没有翻转，而右下角的三角形则翻转了。简单来说，如果第三个点位于由两个静止点形成的虚线的另一侧，三角形就被认为是“翻转”的。

更新2：使用叉乘的有效函数：

def would_flip2(stationary, orig_third_point, candidate_third_point):
    vec1 = numpy.array([stationary[1][0] - stationary[0][0], stationary[1][1] - stationary[0][1], 0])
    vec2_orig = numpy.array([orig_third_point[0] - stationary[0][0], orig_third_point[1] - stationary[0][1], 0])
    vec2_candidate = numpy.array([candidate_third_point[0] - stationary[0][0], candidate_third_point[1] - stationary[0][1], 0])
    orig_direction = numpy.cross(vec1, vec2_orig)[2]
    candidate_direction = numpy.cross(vec1, vec2_candidate)[2]
    if orig_direction > 0 and not(candidate_direction > 0) or \
        orig_direction < 0 and not(candidate_direction < 0):
        return True
    return False

Answer 1

你可以先在你的 would_flip 函数里加一个 is_straight_line 函数，这样只有当不是直线的时候，后面的代码才会执行。

Answer 2

计算由你提供的三个点生成的两个向量的叉积。如果叉积的方向发生了变化，说明三角形翻转了。

举个例子：

假设有点集 [(1.0,1.0), (2.0,3.0), (3.0,1.0)]：

我们可以形成两个三维向量：

(2-1,3-1,0) = (1,2,0) 和 (3-1,1-1,0) = (2,0,0)

接下来计算它们的叉积：

(1,2,0) x (2,0,0) = (0,0,0-4) = (0,0,-4)

或者，使用numpy来计算：

import numpy as  np
np.cross([1,2,0],[2,0,0])
# array([ 0,  0, -4])

再比如，如果我们有点集 [(1.0,1.0), (2.0,3.0), (1.0,2.0)]：我们同样形成两个三维向量：

(2-1,3-1,0) = (1,2,0) 和 (1-1,2-1,0) = (0,1,0)

然后再次计算它们的叉积：

np.cross([1,2,0],[0,1,0])
# array([0, 0, 1])

因为向量 (0,0,-4) 指向“下方”，而向量 (0,0,1) 指向“上方”，所以三角形翻转了。

---

其实你并不一定需要用numpy来做这个。如果你在纸上计算数学公式，发现如果点的坐标是 (x1,y1), (x2,y2) 和 (x3,y3)，那么叉积中的关键数字可以用下面的公式表示：

(y2-y1)*(x2-x1) - (y3-y1)*(x2-x1)

你只需要计算这个值，并观察它的符号变化。（如果上面的表达式等于0，说明这三个点是共线的。）