Обнаружение переворачивания треугольника при изменении точки

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

Вычислите перекрестное произведение двух векторов, сгенерированных из ваших трех точек. Если направление перекрестного произведения меняет знак, треугольник перевернулся.

Например:

Учитывая [(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) указывает «вверх», треугольник перевернулся.

---

Тебе на самом деле не нужен няшка для этого. Если вы решите математику на бумаге, то окажется, что если точки заданы как (x1, y1), (x2, y2) и (x3, y3), тогда номер ключа в перекрестном произведении задается как

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

Вам просто нужно вычислить это значение и следить за изменениями в его знаке. (Три точки коллинеарны тогда и только тогда, когда приведенное выше выражение равно 0.)

Answer 2

Вы можете запустить вашу функцию would_flip с функцией is_straight_line, а остальная часть кода будет выполняться, только если она не является прямой линией.