2 つの線分が交差する場所をどのように検出しますか? [closed] 質問する

この問題には、ベクトル積を使用する優れたアプローチがあります。2 次元ベクトル積v  ×  wをv _x  w _y  −  v _y  w _xと定義します。

2 つの線分がpからp  +  rまで、およびqからq  +  sまで伸びているとします。この場合、最初の線上の任意の点はp  +  t  r (スカラー パラメーター tの場合)として表すことができ、2 番目の線上の任意の点はq  +  u  s (スカラー パラメーター uの場合) として表すことができます。

tとu が次の値を満たす場合、2 本の線は交差します。

p + t  r = q + u  s

両側をsで交差させて、

( p + t  r ) × s = ( q + u  s ) × s

そしてs  ×  s = 0なので、これは

t  ( r × s ) = ( q − p ) × s

したがって、tについて解くと次のようになります。

t = ( q − p ) × s / ( r × s )

同様にuについても解くことができます。

( p + t  r ) × r = ( q + u  s ) × r

u  ( s × r ) = ( p − q ) × r

u = ( p − q ) × r / ( s × r )

計算ステップ数を減らすには、これを次のように書き直すと便利です（s  ×  r = −  r  ×  sであることに留意してください）。

u = ( q − p ) × r / ( r × s )

現在、4 つのケースがあります。

1. r  ×  s  = 0 かつ ( q  −  p ) ×  r = 0の場合 、2 つの線は同一直線上にあります。

   この場合、2 番目の線分の端点 ( qとq  +  s ) を最初の線分 ( p + t r )の方程式で表します。

   t ₀ = ( q − p ) ·  r / ( r  ·  r )

   t ₁ = ( q + s − p ) ·  r / ( r  ·  r ) = t ₀ + s  ·  r / ( r  ·  r )

   t ₀とt ₁の間の区間が区間 [0, 1] と交差する場合、線分は同一直線上にあり、重なり合っています。それ以外の場合は、線分は同一直線上にあり、重なり合っていません。

   sとr が反対方向を向いている場合はs  ·  r < 0 となり、チェックする区間は [ t ₀ , t ₁ ] ではなく [ t ₁ , t ₀ ] となることに注意してください。

2. r  ×  s  = 0かつ( q  −  p ) ×  r ≠ 0の場合 、2つの線は平行であり交差しません。

3. r  ×  s  ≠ 0 かつ 0 ≤  t  ≤ 1 かつ 0 ≤  u ≤ 1の場合 、2 つの線分は点p + t  r = q + u  sで交わります。

4. それ以外の場合、2 つの線分は平行ではありませんが、交差しません。

クレジット: この方法は、 Graphics Gemsの 304 ページに掲載された Ronald Goldman による記事「3 空間での 2 本の線の交差」の 3D 線交差アルゴリズムを 2 次元に特化したものです。3次元では、線が斜めになっている (平行でも交差でもない) のが通常ですが、その場合、この方法は 2 本の線が最も接近する点を示します。