数学orアルゴリズムが得意の方（線分と線分の交点判別）

Ｃ言語のアルゴリズムを勉強中です。
線分Ａ（A(x1,y1),B(x2,y2))と線分Ｂ（C(x3,y3),D(x4,x4))が交差するかどうかを判別し、交差するのであればその交点Ｐ(X,Y)を求める。
また、その交点がどちらか一方の線分上にあるかどうかも判別したいのです。
一番効率よくやるにはどのようにすればよいでしょうか。
例えば
１、三角形の符号付き面積を使って交差するかどうかと各点が線分上にあるかどうかを判別し、その後交点を求める
２、とり合えず交点を求めてその交点が各線分内(上)にあるかどうかを判別

他にもたくさんありそうですがとにかく出来るだけ計算回数を減らしたいのです。（さっき求めた～～を～～するといったかんじで）

出来れば流れ全体を書いていただきたいのですが書き込むのが大変だと思うのでせめて使う判別式だけでも教えてください。
これが出来たら、
多角形と多角形の交点判別のアルゴリズムにも挑戦しようと思っています。

数学の得意な方、アルゴリズムを考えるのが好きな方
よろしくお願いします。

No.6 ベストアンサー 回答者： hogehoge2 回答日時： 2002/11/25 21:34

No.4,5のhogehoge2です。

何度もすみません。
間違っていましたので、訂正いたします。

次の部分を
----------------------------------------
(2)
　det==0のとき(3)へ
　その他(else)のとき(6)へ

(3)
　y1==y2のとき(4)へ
　その他のとき(5)へ
----------------------------------------


次のようにご訂正ください。
----------------------------------------
(2)
　det==0のとき(3)'へ
　その他(else)のとき(6)へ

(3)'
　(x3-x1)*(y4-y1)-(y3-y1)*(x4-x1)==0のとき(3)へ
　その他のとき　線分ＡＢ、ＣＤは共有点をもたない。

関数の終り

(3)
　x1==x2のとき(4)へ
　その他のとき(5)へ
----------------------------------------


以上

この回答へのお礼

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

なんとかなりました…（たぶん）

何度も回答していただき感謝してします。

お礼日時：2002/12/20 09:41

No.5 回答者： hogehoge2 回答日時： 2002/11/24 12:31

No.4のhogehoge2です。

間違っていましたので、訂正いたします。

A(x1,y1),B(x2,y2),C(x3,y3),D(x4,y4)
ただし、x1≠x2 or y1≠y2,x3≠x4 or y3≠y4とする。

以下は、共有点を持つか、持たないかを判別する関数を想定したものです。

(1)
　det=(x2-x1)*(y3-y4)-(y2-y1)*(x3-x4)
　とする。

(2)
　det==0のとき(3)へ
　その他(else)のとき(6)へ

(3)
　y1==y2のとき(4)へ
　その他のとき(5)へ

(4)
　(y3-y1)*(y4-y1)<=0 || (y3-y2)*(y4-y2)<=0 || (y1-y3)*(y2-y3)<=0 || (y1-y4)*(y2-y4)<=0のとき
　線分ＡＢ、ＣＤは共有点をもつ。（無数または一つ）
　その他のとき　線分ＡＢ、ＣＤは共有点をもたない。

関数の終り

(5)
　(x3-x1)*(x4-x1)<=0 || (x3-x2)*(x4-x2)<=0 || (x1-x3)*(x2-x3)<=0 || (x1-x4)*(x2-x4)<=0のとき
　線分ＡＢ、ＣＤは共有点をもつ。（無数または一つ）
　その他のとき　線分ＡＢ、ＣＤは共有点をもたない。

関数の終り

(6)
　da1=y1*x2-x1*y2+x1*y3-y1*x3+y2*x3-x2*y3
　db1=y1*x2-x1*y2+x1*y4-y1*x4+y2*x4-x2*y4

　da2=y3*x4-x3*y4+y1*x3-x1*y3+x1*y4-y1*x4
　db2=y3*x4-x3*y4+y2*x3-x2*y3+x2*y4-y2*x4
　
　d1=da1*db1
　d2=da2*db2
とするとき

(7)
　d1<=0 && d2<=0 のとき　線分ＡＢ、ＣＤは交点をもつ。
　その他(else)のとき 線分ＡＢ、ＣＤは共有点をもたない。

関数の終り

線分ＡＢ、ＣＤが交点をもつときは
交点の座標は２元連立方程式で解くだけです。


以上

No.4 回答者： hogehoge2 回答日時： 2002/11/24 00:31

お役に立つかわかりませんが。

(1)
　da1=y1*x2-x1*y2+x1*y3-y1*x3+y2*x3-x2*y3
　db1=y1*x2-x1*y2+x1*y4-y1*x4+y2*x4-x2*y4

　da2=y3*x4-x3*y4+y1*x3-x1*y3+x1*y4-y1*x4
　db2=y3*x4-x3*y4+y2*x3-x2*y3+x2*y4-y2*x4
　
　d1=da1*db1
　d2=da2*db2
とするとき

(2)
　d1<=0 and d2<=0 のとき　線分ＡＢ、ＣＤは共有点を持ちます。
　その他(else)のとき 線分ＡＢ、ＣＤは共有点を持ちません。
　共有点の判定はこれでできます。

上の共有点を持つ場合の処理ですが

(3)
　(x2-x1)*(y3-y4)-(y2-y1)*(x3-x4)=0
　のとき　無数の共有点を持ちます。

(3)'
　(x2-x1)*(y3-y4)-(y2-y1)*(x3-x4)≠0
　のとき　ただ１つの交点を持ちます。
　交点の座標は２元連立方程式で解くだけです。

以上

No.3 回答者： g_dori 回答日時： 2002/11/21 16:11

あらら、失礼しました。

私がやるとしたら、こんな感じでしょうか。

１．四角形ａ｛x1,x2,y1,y2｝と四角形ｂ｛x3,x4,y3,y4｝の当たり判定を求める
２．(x1,y1)を零点として全部の座標を修正（オーバーフローをこれで防ぎます）
３．あとは適当（笑）

１の四角形の当たり判定は、乗算２回よりも軽く済むはずですので、ないよりはマシだと思います。いきなり計算に入ると非常に重いです。
２は正確性を求めて。。。

←ゲームで導入しようとして挫折した経験者でした（笑）

No.2 回答者： g_dori 回答日時： 2002/11/20 18:13

今更申し訳ないのですが。

。。
どのようなプログラムなのか、それからはじめた方が良いんじゃないでしょうか？

多分ゲームか何かじゃないかと推察しますが、高速処理を追及するソフトでの単純な当たり判定をご希望でしたら、お考えのアルゴリズムは使いませんよ。
多角形同士の当たり判定や、傾きのある直線同士の当たり判定は重すぎる上に、値によっては正確なあたり判定が行えないので、まず使いません。（ちょっと大きな値を使うと、double型でも計算時にオーバーフローします）

交点を求めると言うことは、x1～4、y1～4、X、Yは全て浮動小数演算にならざるを得ないと思いますが、高速処理を追及するなら、そのあたりから既に無駄じゃないでしょうか。

整数しか使わないか、１未満の小数しか使わないプログラムだと言う事ならまだわかりますが、そうでないならそこの点から改善された方が、全体的なスピードアップになると思います。
そして、当たり判定は四角形のみで行う・・と。

正確な当たり判定のアルゴリズムよりも、正確でなくてもそれを誤魔化すアルゴリズムを考えた方が無難じゃないでしょうか。
ひとつの物体に対して四角形の当たり判定をいくつか用意すれば、それなりに当たっているように見えますよ。
最近の３Ｄゲームも全部そうやっているはずですので。。。

勘違いならゴメンなさい！

この回答へのお礼

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

ゲームではないのですが高速処理を追及するソフトです。(正確にはできるだけ…）
一応、断りを入れておきますが、課題や卒論等の類ではありません。
仕事の関係であったらいいな。と思って学生のころの知識でつくっているソフトです。
最悪、1000角形の２乗回演算することになるので少しでも早いほうがと思い、このような質問をさせていただきました。

お礼日時：2002/11/20 20:16

No.1 回答者： hinebot 回答日時： 2002/11/19 17:17

交差するかどうかなら、傾きを比べれるのが一番簡単でしょう。

ABの傾き (y2-y1)/(x2-x1)
CDの傾き (y4-y3)/(x4-x3)
これが、一致しなければ必ずどこかで交差します。
（傾きが一致　⇒　ABとCDは平行　です）
ただし、x2-x1 = 0 or x4-x3=0 のときだけ注意が必要です。
x2-x1=0(つまりx1=x2)かつx4-x3=0(つまりx3=x4)ならば、ABとCDは平行
それ以外は交差します。

結論ですが、
(y2-y1)(x4-x3)と、(y4-y3)(x2-x1)　を計算して両者を比較し、
一致すれば交差しない（平行）、不一致ならば交差します

次に、実際に交点を計算しますが、x2-x1=0 or x4-x3=0 でない限り計算するのはｘ座標だけで構いません。
交点の座標を仮にP(xp,yp)とします。
x1＜x2　として、 x1≦xp≦x2　であるかどうかを調べます。
x1≦xp≦x2であれば、交点は線分AB上にあります。
同様に x3＜x4として
x3≦xp≦x4であれば、交点は線分CD上にあります。
（x2-x1=0 or x4-x3=0 のときはx座標の変わりにｙ座標を計算してください。）

簡単にまとめると
<1>(x2-x1),(x4-x3),(y2-y1),(y4-y3)の４つの値を計算する
<2> <1>から　(y2-y1)(x4-x3)と、(y4-y3)(x2-x1)　を計算
<3>　２つの値が一致するか判定（交差の判定）
<4> 交差する場合、交点のx座標（またはy座標）を計算する
　　ここで、x座標にするかy座標にするかは、x2-x1,x4-x3 が０かどうかで判定する。
<5> 交点のx座標（またはy座標）がでたら、AとBの座標との大小を比較する
　　同様に、CとDの座標との大小を比較する（交点が線分上にあるかを判定）

こんな感じかな。

この回答へのお礼

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

やはり
交点があるかどうかをチェックしてから交点を求めるより
交点を求めてから線分上にあるかどうかをチェックしたほうが効率がいいのですね。

仮に多角形同士の交点に応用する場合等、交点があるかどうかすらきわどい場合が多い場合でもこの流れの方が効率が良いのでしょうか？
それとも場合によっては変えたほうが良いのでしょうか？

お礼日時：2002/11/20 11:15