ポイントを変更するときに三角形が反転するかどうかを検出する

Question

ポイントの1つを置き換えて三角形を変更する必要があります。しかし、そうすると、三角形が反転するかどうかを検出する必要があります。

例えば、点によって定義される三角形：

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

このようになります。私は(3.0,1.0)から(1.0,2.0)に第三の点を変更した場合

が、それはのように、フリップここに示す：

Iは、三角形が固定点の方程式を計算し、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で書かれているという事実は重要ではありません。私は数式またはよく記述されたテクニックである答えを受け入れます。

EDIT：左上がオリジナルの三角形である

：それは、以下の4つの三角形を考える「フリップ」

にある三角形のために何を意味するのかについての詳細。赤い線（四つとも同じ）は2つの静止点です。残りの3つの三角形が第3の点を置き換えます。右上と左下の三角形は反転されず、右下の三角形は反転されます。本質的に、第3の点が2つの静止点によって形成される仮想線の反対側で終わる場合、三角形は「反転」される。

アップデート2：クロス製品を使用して作業する機能：

Answer 1

3点から生成された2つのベクトルのcross-productを計算します。 クロス積の方向が符号を変更すると、三角形が反転しています。例えば

：[(1.0,1.0), (2.0,3.0), (3.0,1.0)]考える

：

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

または、numpyのを使用して：：

フォーム2（3D）は、それらの外積を取る

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

ベクトル

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)

そして再び：我々は2つ（3D）ベクトルを形成ベクトル（0ので

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

を0、-4）が「下」を示し、ベクトル（0,0,1）が「上」を指している場合、三角形は反転している。

---

これには本当にnumpyは必要ありません。紙で数学を計算すると、ポイントが（x1、y1）、（x2、y2）、（x3、y3）、 で与えられる場合、外積のキー番号は

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

その値を計算して、その変更の有無を監視するだけで済みます。 （3つの点は、上記の式が0に等しい場合にのみ同一直線上にあります）

Answer 2

あなたはis_straight_line機能を使用してwould_flip機能を開始することができ、それが直線でない場合は、コードの残りの部分にのみ実行されます。