geometry - 座標のペアに基づいて、2 つの間に交点があるかどうかを判断する方法は?

Question

次のように、2 つの x、y 座標で表される 2 つの線分があります。

[(x1,y1),(x2,y2)] //start & end of first line
[(x3,y3),(x4,y4)] //start & end of second line

これらの線に交点があるかどうかを判断する最も効率的な方法は何ですか?

Answer 1

交差点がある場合

(((X3-X1) * (Y2-Y1)-(Y3-Y1) * (X2-X1)) * ((X4-X1) * (Y2-Y1)-(Y4-Y1) * (X2-X1) )) <= 0)

と

(((X1-X3) * (Y4-Y3)-(Y1-Y3) * (X4-X3)) * ((X2-X3) * (Y4-Y3)-(Y2-Y3) * (X4-X3) )) <= 0)

Answer 2

衝突をチェックしている最初のベクトル/ラインとラインの端点によって形成された三角形を取り、行列式を介してその面積を取ります。その面積を、もう一方の端点で形成される三角形の面積と比較します。それらが両方とも正/負の場合、交差はありません。それらの標識が異なる場合、交差点がある可能性があります。

それらの符号が異なる場合は、線の端点の代わりに元のベクトルの端点を使用することを除いて、上記と同じことを行います。(元のベクトルの代わりに行全体を使用します)。

符号が異なれば間違いなく交差点があり、同じであれば交差点はありません。

便利なリンク: 三角形の行列式を取る:こちら

決定要因の評価:こちら

意味が分からない場合はお知らせください。