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

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编写的事实并不重要.我将接受一个只是一个公式或描述良好的技术的答案.

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

考虑下面的四个三角形:

左上角是原始三角形.红线(所有四个相同)是两个静止点.三个三角形的其余部分代替第三个点.右上角和左下角三角形不会翻转,而右下角的三角形则会翻转.基本上,如果第三点最终位于由两个静止点形成的假想线的相对侧,则三角形"翻转".

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

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时,这三个点是共线的.)