誰かがこの交差テスト関数を説明してください

Question

ジオメトリクラスで提供されているいくつかの関数を見ていますが、この2つの行の間に交差点があるかどうかをテストする非常に貧弱なコメント付き関数が見つかりました。誰かが私にこの作品の仕組みを説明してもらえますか？私が収集したものから

inline bool LineIntersection2D(Vector2D A, 
           Vector2D B, 
           Vector2D C, 
           Vector2D D) 
{ 
    double rTop = (A.y-C.y)*(D.x-C.x)-(A.x-C.x)*(D.y-C.y); 
    double sTop = (A.y-C.y)*(B.x-A.x)-(A.x-C.x)*(B.y-A.y); 

    double Bot = (B.x-A.x)*(D.y-C.y)-(B.y-A.y)*(D.x-C.x); 

    if (Bot == 0)//parallel 
    { 
     return false; 
    } 

    double invBot = 1.0/Bot; 
    double r = rTop * invBot; 
    double s = sTop * invBot; 

    if((r > 0) && (r < 1) && (s > 0) && (s < 1)) 
    { 
     //lines intersect 
     return true; 
    } 

//lines do not intersect 
return false; 
} 

、A及びBは、最初のラインの二点であり、C及びDは、第二の二点です。その後、私は完全に失われています。前もって感謝します！

Answer 1

まず、いくつかのベクトルを識別できます。 Let u = B - A,v = D - Cおよびw = A - C。

double rTop = (A.y-C.y)*(D.x-C.x)-(A.x-C.x)*(D.y-C.y); 
double sTop = (A.y-C.y)*(B.x-A.x)-(A.x-C.x)*(B.y-A.y); 
double Bot = (B.x-A.x)*(D.y-C.y)-(B.y-A.y)*(D.x-C.x); 

ここ

rtop = v X w 
stop = u X w 
bot = u X v 

u X vに変換最初の行は、エッジu、vで平行四辺形の署名された面積を与えるクロス積の2Dバージョンです。

は、交差点のいくつかの点Pが存在すると仮定し、我々はパラメータrは、線分を与えるために、0から1の範囲で

P = r u + A. 

書き込むことができます。我々はまた、我々が互いに

r u + A = s v + C 

に等しく、これらを設定し、これは、2Dベクトル方程式であるC

r u + A - C = s v 

又は

r u + w = s v 

を引くことができ

P = s v + C 

を書き込むことができます2つの変数rとsにある。 uまたはvとのクロス積をu X u = 0とすることで、rまたはsのいずれかを削除できます。

r u X u + w X u = s v X u 

よう

w X u = s v X u 

と

s = (w X u)/(v X u) 

同様v排除Sとクロス積をとります。

r u X v + w X v = s v X v 
r u X v + w X v = 0 
r = - (w X v)/(u X v) 
r = (v X w)/ (u X v) 

どこかに看板がありますが、それは要点です。

交点がセグメント上にあるためには、rとsの両方が0と1の間でなければなりません。

これを幾何学的に解釈できます。Uは水平であり、vは

垂直である例を取ることができ今u X vは矩形の面積を与え、w X vは、平行四辺形の面積を与えます。 2つの領域の比率はABの長さの比率ABと同じであることがわかります。

より一般的な位置の場合の別の図です。

sTop = v X w平行四辺形ACDEの領域であり、Bot = u X vが大きくparallogramのABFEの領域です。 2つの比率は、交差点ABのどれくらいの距離にあるかを示します。