python - 检测改变点时三角形是否翻转

我需要通过替换其中一个点来更改三角形。但是，我需要检测这样做是否会导致三角形翻转。

例如，由点定义的三角形:

[(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 编写的这一事实并不重要。我会接受一个只是公式或详细描述的技术的答案。

编辑:有关三角形“翻转” 意味着什么的更多信息

考虑下面的四个三角形:

左上角是原始三角形。红线(四个都一样)是两个静止点。其余的三个三角形替换第三个点。不翻转右上角和左下角的三角形，而翻转右下角的三角形。本质上，如果第三个点位于由两个静止点形成的假想线的另一侧，则三角形被“翻转”。

UPDATE2:使用叉积的工作函数:

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

最佳答案

计算从三个点生成的两个向量的 cross-product 。
如果叉积的方向改变符号，则三角形已翻转。

例如:

给定 [(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。)

关于python - 检测改变点时三角形是否翻转，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7365531/