線分同士の交点の判定

線分の交差判定についてネットで調べていたら、以下のような処理で
できると書かれていたページがあったのですが、どうしても理解する事が
できません。

もしできれば、解説を頂いてもいいでしょうか。
よろしくお願いします。

//２次元での線分と線分の交差判定と交点
BOOL CheckCrossLine(CONST D3DXVECTOR2* pvA1,
　　　　　　　　　　CONST D3DXVECTOR2* pvA2,
　　　　　　　　　　CONST D3DXVECTOR2* pvB1,
　　　　　　　　　　CONST D3DXVECTOR2* pvB2,
　　　　　　　　　　D3DXVECTOR2* pvOut)
{
D3DXVECTOR2 v1 = *pvA1 - *pvB1;
D3DXVECTOR2 vA = *pvA2 - *pvA1;
D3DXVECTOR2 vB = *pvB2 - *pvB1;

if (*pvA1 != *pvA2) ;
else return FALSE;//線分が点のときは交差していないとする

if (*pvB1 != *pvB2) ;
else return FALSE;//線分が点のときは交差していないとする

FLOAT fDeno = vA.x * vB.y - vA.y * vB.x;//外積の長さ

//分母が０で、平行なときは
if (fDeno != 0.0f) ;
else return FALSE;//交差していないことにする

FLOAT t = (v1.y * vB.x - v1.x * vB.y) / fDeno;
FLOAT s = (v1.y * vA.x - v1.x * vA.y) / fDeno;

if (t < 0.0f || t > 1.0f || s < 0.0f || s > 1.0f)
return FALSE;//交差していない
else {
//交点を返す
pvOut->x = vA.x * t + pvA1->x;
pvOut->y = vA.y * t + pvA1->y;
return TRUE;//交差
}

No.4 回答者： mizuneko 回答日時： 2006/06/01 22:13

はじめまして。

こういった図を見ながらでないとわかりづらい問題は、
書籍をあたったほうがわかりやすいかと思います。
プログラミング関係の本にまじって「～数学」などという本がいくつか
あるはずなのでそれを見るのがよいと思います。
ＷＥＢ上でしたら以下のＵＲＬがお勧めです。

参考URL：http://www12.plala.or.jp/ksp/mathInPhys/index.html

No.3 回答者： ymmasayan 回答日時： 2006/05/31 18:55

No.1です。

とりあえず、１つだけ。

>　なぜfDenoが0の時並行なのか、

ベクトルなのですが。
Ａのｘ成分とｙ成分、Ｂのｘ成分とｙ成分を考えると
平行→傾きが同じ　ということから
Ａのｙ成分／Ａのｘ成分＝Ｂのｙ成分／Ｂのｘ成分が成立します。
これを整理するとfDeno＝０の式になります。

あとは考えてください。

No.2 回答者： Trick--o-- 回答日時： 2006/05/31 14:37

最初の二つのifはいいですね？

二つの線分のうち、どちらかの両端が同じ点（＝線分が点）のときは
交差していないと「定義」しています。

次のif文は、二つのベクトルの平行条件です。
http://aozoragakuen.sakura.ne.jp/taiwaN/taiwaNch …
平行な二直線は当然、交差しませんね。

ここまでで、二直線は平行ではない＝どこかで交差する、となります。
しかし、線分が交差するためには、交点がそれぞれの線分中になければいけません。
その判定が最後のif文です。
ｔとｓがどのような値になるか、実際に計算して確かめてみてください。

この回答への補足

ご回答いただきありがとうございます。

どういう判定をしているかよく分かる事ができました。

ただ、なぜfDenoが0の時並行なのか、
(v1.y * vB.x - v1.x * vB.y) / fDenoや、
(v1.y * vA.x - v1.x * vA.y) / fDenoで、
それぞれの線分中で交差しているかどうかの値を出す事が
できるのですか？

下の方の回答と同じ補足で申し訳ありませんが、もしよければ
教えて頂けますでしょうか？

補足日時：2006/05/31 15:27

No.1 回答者： ymmasayan 回答日時： 2006/05/31 12:30

次の４つに分けて考えます。

１．どちらかが点・・ダメ
２．平行・・ダメ
３．線分が重なる・・ＯＫ
４．延長すれば重なる・・ダメ

線分を単純な数式で扱うのは無理なのでとりあえず直線として交点を求めます。

すると３と４が混じるので交点が両方の線分上にあるかどうかを
チェックして４を除外します。

この回答への補足

ご回答いただきありがとうございます。

どういう判定をしているかよく分かる事ができました。

ただ、なぜfDenoが0の時並行なのか、
(v1.y * vB.x - v1.x * vB.y) / fDenoや、
(v1.y * vA.x - v1.x * vA.y) / fDenoで、
それぞれの線分中で交差しているかどうかの値を出す事が
できるのですか？

もしよければ教えて頂けますでしょうか？

補足日時：2006/05/31 15:27