[解決済み] 2つの線分が交差しているかどうかを確認するにはどうすればよいですか？

質問

2つのセグメントが交差しているかどうかを確認するにはどうすればよいですか。

以下のようなデータがあります。

Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ] 

私は2つの線が交差しているかどうかを検出するためにPythonで小さなアルゴリズムを記述する必要があります。

どのように解決するのですか？

直線の方程式は

f(x) = A*x + b = y

セグメントについては、xが区間Iに含まれることを除いて、全く同じである。

次のように定義された2つのセグメントがある場合。

Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}

交点(Xa,Ya)のポテンシャルXaは、次のように定義される区間I1とI2の両方に含まれなければならない。

I1 = [min(X1,X2), max(X1,X2)]
I2 = [min(X3,X4), max(X3,X4)]

そして、Xaは.に含まれていると言えるでしょう。

Ia = [max( min(X1,X2), min(X3,X4) ),
      min( max(X1,X2), max(X3,X4) )]

さて、この区間Iaが存在するかどうかを確認する必要があります。

if (max(X1,X2) < min(X3,X4)):
    return False  # There is no mutual abcisses

ということで、2つの線分式と、相互間隔があります。あなたの線分式は

f1(x) = A1*x + b1 = y
f2(x) = A2*x + b2 = y

セグメントで2点得られたので、A1、A2、b1、b2を決定することができる。

A1 = (Y1-Y2)/(X1-X2)  # Pay attention to not dividing by zero
A2 = (Y3-Y4)/(X3-X4)  # Pay attention to not dividing by zero
b1 = Y1-A1*X1 = Y2-A1*X2
b2 = Y3-A2*X3 = Y4-A2*X4

セグメントが平行である場合、A1 == A2 。

if (A1 == A2):
    return False  # Parallel segments

両直線上に立つ点(Xa,Ya)は、式f1、f2の両方を検証する必要があります。

Ya = A1 * Xa + b1
Ya = A2 * Xa + b2
A1 * Xa + b1 = A2 * Xa + b2
Xa = (b2 - b1) / (A1 - A2)   # Once again, pay attention to not dividing by zero

最後にXaがIaに含まれることを確認します。

if ( (Xa < max( min(X1,X2), min(X3,X4) )) or
     (Xa > min( max(X1,X2), max(X3,X4) )) ):
    return False  # intersection is out of bound
else:
    return True

これに加えて、起動時に提供された4点のうち2点が等しくないことをチェックして、すべてのテストを回避することもできます。