检测当改变一个点时，三角形是否会翻转

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

- jterrace

---

我认为你没有清楚地说明“翻转”的含义：似乎你有一些规则，使得每个三角形中的一个点很特殊，但你并没有明确说明这个规则是什么。 - Croad Langshan

啊，我现在明白了，再看一遍：每个点在三元组中的位置定义了该点的标识。 "flip" 的定义是这样的，即由这些点定义的（“有弹性的”！）物理三角形必须在三维空间中围绕包含您的三角形的二维平面上的轴旋转，才能从第一个三角形到达第二个三角形。也许并不比您最初的解释更清楚！ - Croad Langshan

我更新了一些关于翻转三角形意义的信息。这样更清楚了吗？ - jterrace

另一种表述这个问题的方式是想象一只蚂蚁从点1到点2再到点3，最后回到点1形成一个环。那么问题就是：这只蚂蚁是顺时针还是逆时针转？与此密切相关的术语是绕数，第一个三角形的绕数为-1，第二个三角形的绕数为1。 - SingleNegationElimination

Answer 1

计算由三个点生成的两个向量的叉积。 如果叉积方向改变，三角形就会翻转。

例如：

给定[(1.0,1.0), (2.0,3.0), (3.0,1.0)]： 形成两个（3D）向量

(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)]时：我们形成了两个（3D）向量：

(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时，三个点共线。)

- unutbu

---

那个(2,1,0)不应该是(2,0,0)吗？ - jterrace

Answer 2

你可以从一个 is_straight_line 函数开始编写你的 would_flip 函数，只有在不是一条直线时才会执行其余代码。

- Vanessa MacDougal

---

我可以检测分母是否为0或者结果斜率是否为无穷大，然后根据输入的y值以不同的方式计算方程，但我希望有一个更优雅的解决方案。 - jterrace