交差判定アルゴリズム

2本の直線の座標x1,y1,x2,y2とx3,y3,x4,y4が交差しているか
判断するアルゴリズムで高速なのってどんなのがあるのでしょう？

交差判定はこうさっ！

しょっぱなの軽いギャグはさておき、「線分　交差」で検索されい。

>>2
なんでおめーらはいつもそうなんだ？
おしえてくれてもいーじゃやんかよー。

グダグダ言わずに検索してみろ。
すぐに答えが出るからよ。

一応googleで検索かけてみたのですがいまいちなものばかりだったので。
って、そのいまいちな物も書けない自分は逝ってよしなんですが
逝く前に教えてもらいたいのです。

http://www.wombat.or.jp/tomoyashuttle/shtml/algorithm/IntersectionEX.htm
http://www.infoeddy.ne.jp/~tensyo/prog/linealgo.htm#XROSSLINE
これでは不満だったのか？

3次元に拡張したやつキボン
n次元に拡張ってできる？

n次元に拡張って…
空間は3次元までだろ
大体にして最初の質問は2次元だが

>>6
全然ダメ、
一つ目は条件分岐ありすぎ
二つ目は割り算使うなんてアホ

四次元に拡張したら空間を移動する点になるし、別に何次元でも拡張できるっしょ。

１次独立なベクトルが n 本とれるという意味で n 次元拡張なんですわ。>>8

>>11
そりゃ連立ｎ元ｍ次方程式でいうところのｎ元では？
３本あったら３本とも一点で交差していれば正解なの？

取り敢えず2次元でしょ

1)直線(2点間)と点を見て線上(0)か線のどちらにあるか(1,-1)を判定する
　関数 f() が使えるとする
2)ある点a(x1,y1),b(x2,y2)と直線(cd2点間)の判定値f() を Va, Vbとすると
　Va*Vb <= 0 なら点a,bは直線cdを挟んでいる
3)点a,bは直線cdを挟んでいる かつ 点c,dは直線abを挟んでいる
　なら 直線abと直線cdは交わっている

でどうよ? (どっかの本からのぱくりだが)

んーと、、空間を表すときに必要な１次独立なベクトルの数です。
３本があるっていうわけでは（解釈あってる？）ないと思う。
３次元なら (x1,y1,z1)-(x2,y2,z2)
４次元なら (x1,y1,z1,w1)-(x2,y2,z2,w2)
この解って高校あたりで習いましたっけ…？忘れた。(^^;)

線分1の両端をa1, b1
線分2の両端をa2, b2
とするとき、
四角形a1-a2-b1-b2が凸であれば良い。

ここで、ベクトルv(x1, y1)がベクトルw(x2, y2)の左右どちらにあるかを示す符号は、
vを時計回りに90度回転させたベクトルv'(-y1, x1）と、wとの内積の符号に等しい。
つまり、符号は
　sign(-x2*y1+x1*y2)

この符号が
　ベクトルa1a2とベクトルa2b1
　ベクトルa2b1とベクトルb1b2
　ベクトルb1b2とベクトルb2a1
　ベクトルb2a1とベクトルa1a2
のすべてでどう符号であれば、四角形a1-a2-b1-b2は凸となる。

端点共有する時の処理などを省けば、比較、計算量ともに少なくて判定できる。
でも、符号の計算で加算減算が入り、桁落ちしやすいのが難しいところ。

>>9
> 二つ目は割り算使うなんてアホ

　ってどこの割算があるんだ？

>>7　３次元については
　まず２直線＝４点が同じ平面上にあるかどうかを判定して
　次に交差判定をすればいいのでは？

４点が同じ平面にあるかどうかは色々あると思うけど
３点で作る平面と４点目の距離を求めればいいかと

３次元だったら　先に無限直線同士で交点があるか　あれば交点を計算して

その交点が線分上にあるかどうかチェックした方がいいかも

>>1
2次元なら簡単
(X2-X1)*(Y4-Y3)-(Y2-Y1)*(X4-X3)
の値が0なら平行
それ以外は交点がある。

>>19 補足
実装する場合、
整数だけを対象とするのでなければ
判定にホントに0を使っちゃだめよ。

>>20 更に補足
平行でないと分かれば
実際の交点は連立方程式を解くだけ。
あとは自分でやってね。

>>19=20=21
それは2直線の交差。2線分ではない。

あれ？　1は2直線の交差でいいのか？

・・・
E=(Y2-Y1)*(X3-X4)-(Y4-Y3)*(X1-X2)
F=(X1*Y2-X2*Y1)*(X3-X4)-(X3*Y4-X4*Y3)*(X1-X2)
G=(X3*Y4-X4*Y3)*(Y2-Y1)-(X1*Y2-X2*Y1)*(Y4-Y3)
とおいて
交点の座標は(F/E, G/E)だったかな。(E≠0は判定済み)
最速かどうか、それは知らない。

>>24 補足
どちらかの座標で大小判定すれば終わりでしょ？

>>25
あ、両方やらんと駄目だわ。

>>24
いや考え方は、それが最速じゃない。
あとは実装

http://www.yamagame.com/MyWeb/Heart/heart13.html

昔、Ｃマガにのってた線分交差判定ソース。

bool cross(Point p1, Point p2, Point q1, Point q2)
{
　　// 方程式の係数 Ax + By + C = 0
　　float A, B, C;

　　// 判定式
　　int d;
　
　　A = p2.y - p1.y;
　　B = p1.x - p2.x;
　　C = -( A * p1.x + B * p1.y);

　　d = (int)((A*q1.x + B*q1.y + C) * (A*q2.x + B*q2.y + C));
　
　　if(d > 0){
　　　　return false; // 非交差
　　}
　　else{
　　　　A = q2.y - q1.y;
　　　　B = q1.x - q2.x;
　　　　C = -( A * q1.x + B * q1.y);
　　　
　　　　d = (int)((A*p1.x + B*p1.y + C) * (A*p2.x + B*p2.y + C));
　　　
　　　　if(d > 0){
　　　　　　// 非交差
　　　　　　return false;
　　　　}
　　　　else{
　　　　　　// 交差
　　　　　　return true;
　　　　}
　　}
}

交差判定の高速化なんてたいしたこと出来ないだろう。

if( rand()%2 )
{
　printf("交差してます");
} else {
　printf("交差してません");

}

みんな僕の宿題に付き合ってくれて有難う。
これで提出日に間に合います。

>>29
int d;
のアドレスにfloat型のまま書き込んだ方がよい

>>1
逝ってよし

>>32
誰もおめーの相手なんてしてねーよ

>>33
＞int d;
＞のアドレスにfloat型のまま書き込んだ方がよい

なるほど、参考になります。
いま思いついたんだけど、たしか浮動小数点って
最上位ビットが符号ビットになってるんだよね。

そうならば、d > 0 の部分を工夫できるかも。

>>35
同意。

>>1のレベルをみる限り>>31程度のプログラムで十分だと思うが？

ようは
先に近接判定するとかだけで
計算式はどこ見ても同じなんだねえ
まあ当然なんだろうけど

結局 (a*b±c*d) みたいな計算が３つか・・・

>>19さんありがとうございます！おかげさまでなんとか動くものが出来ました。
他にも>>29さん他アドバイスを下さった皆さんありがとうございます。
これで心置きなく逝くことが出来そうです。
尚、>>29さんのコードを試したら座標にマイナス値が含まれる場合うまく値を
返さないケースがあったことを報告します＞書き方がまずかっただけかも
あ、ちなみに32は私じゃないです。
なにはともあれ助かりました。ありがとうございます。

>>38
あと、原点が(0,0)の式を使うか、頂点の一つを原点にするかにも
その人の性格が出るね

俺はどっちかいうと　頂点派だな

理由は　浮動小数点演算の時に精度が良さそうだし、
整数演算でも桁溢れの率が減りそうだから

□□□□■□□□□□■□□□□□□□□□□□□□□□□□□□□□
□□□■■□□□□□■□□□□□□□■■■■■■■■■■■■□□
□□■■□□□□□■■■■■■□□□□□□□□□□□□□■■□□
□■■□□■□□□■□□□□■□□□□□□□□□□□□■■□□□
□□■□■■□□■■■□□■■□□□□□□□□□□□■■□□□□
□□□■■□□■■□■■■■□□□□□□□□□□□■■□□□□□
□□■■□□□□□□□■■□□□□□□□□□□□■■□□□□□□
□□■□□□■□□□■■■■□□□□□□□□□□■□□□□□□□
□■■■■■■□□■■□□■■□□□□□□□□□■□□□□□□□
□□□□■□□□■■□□□□■■□□□□□□□□■□□□□□□□
□□■□■□■□□□□■■□□□□□□□□□□□■□□□□□□□
□□■□■□■□□□□□■■□□□□□□□□□□■□□□□□□□
□■■□■□■□□□□□□□□□□□□□□□□□■□□□□□□□
□■□□■□□□□■■■□□□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□■■■□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□□□■■□□□□□□■■■■□□□□□□□





続きはコチラです
http://www.geocities.com/entry_k/main/main01.html

age

n次元で通用する簡単な交差判定アルゴリズムもあるよ。

>>44教えてプリーズ！

29の式のdを求めるところで、符号だけ見るんで
掛け算の代わりにXORを使うのってだめ?

どうにもこうにも線形代数の教科書を紐解けば
軽く解法が載ってるような気もする。

>>47
本を読めない or 読んでもプログラムに書けないDQNもいる

ＤＱＮ＝ドキュンね。なんかいいな、それ（藁

>>46
ダメ、直線の両端点がもう一方の直線の左右に分かれる場合がd<0なの

内積理解してれば方程式云々以前の問題なんだけどね

>>50
すまん、dを求める際の全部の掛け算じゃなくって、どまんなかのp1とp2の部分の
合成の掛け算を指してたのじゃ
たしかGraphicsGemsのIIIあたりにあった記憶があるんだけど手元になくって

XORでもいいけど、最近のCPUじゃあんまり高速化につながらない。整数掛算だって早いもの

でもPenシリーズ(元祖,II,!!!,4)の掛算は浮動小数点の掛算より遅いんじゃなかった？

いやほら、floatをintに代入してXORして符号ビットだけ見ればいいからと
思ったのよ
確かにXORって掛け算より使用頻度少なそうだから、最近じゃCPUから
命令無くされてるかも?
(NOTやAND,ORの組合わせにされちゃう?）

>>54
なんぼなんでもそれはない。

いや　掛算は浮動小数点計算する方のユニットで計算されるでしょ
だから整数演算ばかりでも掛算がたまにあるとそっちのユニットも使われて並列性があがるとか？

ペンティアムプロセッサの最適化
http://www.csl.sony.co.jp/person/fnami/pentopt.htm

>>57
古っ。

0近辺だと実数掛け算とXORだと丸めの分、符号が
違くなる気がするな

>>51
スマソ、勘違いしてた
符号が逆なことだけ分かればいいからXORで行ける
でもアセンブラで気合入れて書かんと効果はなさそうだね

>>54
P5では論理演算はNANDのみになります

>>61
がいしゅつです

VC++は浮動小数点から整数に変換するとパイプラインがクリアされるから
２、３個の分岐のために整数にしても逆効果になるよ
テクスチャ座標が0.5ずれる3Dカードのドライバは
高速化のために丸めモードを無視して整数変換しているわけ
8087自体は古いのでしょうがないがintelがアホなことは確か

最近よく思うのだけど、昔のアルゴリズムの本や数値演算の本にでてる方法って
掛け算の数で勝負みたいなとこあったじゃない?(ワークエリアを使ってでも）
今時分のCPUみたく掛け算のコストが加減算程度まで下がったら、そのへんて
見直してるのかしら
そこんとこどーよ＞ 一松信
(ぉぃぉぃぉぃ)

多分>>19や>>24と同じなんだろうけど、
座標をパラメーター表示するので考えてみた。
(x1,y1)と(x2,y2)の線分と(x3,y3)と(x4,y4)の線分は、
パラメーターsとtで表すと、それぞれ
    (x1+(x2-x1)s,y1+(y2-y1)s)
と
    (x3+(x4-x3)t,y3+(y4-y3)t)
となる。ただし、0≦s≦1、0≦t≦1。

これらの交点は、
    x1+(x2-x1)s=x3+(x4-x3)t
    y1+(y2-y1)s=y3+(y4-y3)t
となり、s、tでまとめると、
    (x2-x1)s-(x4-x3)t=x3-x1
    (y2-y1)s-(y4-y3)t=y3-y1
となる。

これをsとtについて解くことにする。
    D=-(x2-x1)(y4-y3)+(x4-x3)(y2-y1)
とすると、D≠0のとき線分を通る直線が交差し、
    s=(-(x3-x1)(y4-y3)+(x4-x3)(y3-y1))/D
    t=((x2-x1)(y3-y1)-(x3-x1)(y2-y1))/D
となる。

このsとtがともに0以上1以下の場合に線分が交差する。

ちなみに、最初の(x1+(x2-x1)s,y1+(y2-y1)s)に代入すれば交点をえる。

おそらく、行列式でもっときれいに表すことができ、
n次元に拡張するのでも同じとなる。

>>64
CPUの性能がいくら上がっても乗算は加減算よりもコストがかかります。

>>66
それほんと?
乗算テーブルをでかく持てないからかな(コスト的に）

>>66 でも加算も　浮動小数点だと、結構大変だよ

　　　　乗算スループット 乗算レイテンシ
Athlon　　　１　　　　　　　　４
P6　　　　　２　　　　　　　　５
　　　　加算スループット 加算レイテンシ
Athlon　　　１　　　　　　　　４
P6　　　　　１　　　　　　　　３

SSEは使い物にならないから、やっぱりAthlonの勝ち

1って宿題が目的だったの？
てっきりゲームでも作ろうともがく厨房かと思った
もし後者ならば今後もさまざまな判定方法で苦しむと思うから
3Dゲーム開発の本を一冊買いなさい
たいていの判定方法は書いてあります。

どうでもいいが、２次元でも３次元でも
平行でないかぎりいつかは交差するだろ？
平行か否かを判定したいの？

実用上はある範囲内でという条件がつくだろうけど、それも不要ですか？

>>71
3次元でも??

>>71
3次元の場合は
2直線が同一平面上あって、なおかつ平行でない場合のみ
交差すると思われ。

すんません。三次元はうそでした。

捩れの位置関係があると思われ＜３次元

定期上げ

>>65 に「優」はやれん
>>29 は惜しいところだが「不可」

線分の交差判定等のアルゴリズムについて勉強したければ，計算幾何学の本を
読むことをお勧めします．「計算幾何学」で検索すれば，おそらく5冊ほど出て
きます．計算幾何学というとプレパラータ，浅野哲夫両先生が有名ですが，他の
著者（＋監訳者）も，アルゴリズムの分野で有名な先生方ばかりです．私は
今井夫妻の本で学びました．

ある点が，２点を通る直線によって作られる二つの半平面のどちらの上にあるか
（直線のどちら側にあるか）を判定するのには，一般に，三角形の符号付面積が
用いられます（除算による計算誤差を回避できる）．

線分ab と線分cd が交差する必要十分条件は，直線ab からみて c と d が
同一半平面上になく，かつ，直線cd からみて a と b が同一半平面上にない
ことです．