5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

交差判定アルゴリズム

1 :デフォルトの名無しさん:2001/07/26(木) 23:33
2本の直線の座標x1,y1,x2,y2とx3,y3,x4,y4が交差しているか
判断するアルゴリズムで高速なのってどんなのがあるのでしょう?

2 :デフォルトの名無しさん:2001/07/26(木) 23:35
交差判定はこうさっ!

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

3 ::2001/07/26(木) 23:36
>>2
なんでおめーらはいつもそうなんだ?
おしえてくれてもいーじゃやんかよー。

4 :デフォルトの名無しさん:2001/07/26(木) 23:39
グダグダ言わずに検索してみろ。
すぐに答えが出るからよ。

5 :1:2001/07/26(木) 23:41
一応googleで検索かけてみたのですがいまいちなものばかりだったので。
って、そのいまいちな物も書けない自分は逝ってよしなんですが
逝く前に教えてもらいたいのです。

6 :デフォルトの名無しさん:2001/07/26(木) 23:52
http://www.wombat.or.jp/tomoyashuttle/shtml/algorithm/IntersectionEX.htm
http://www.infoeddy.ne.jp/~tensyo/prog/linealgo.htm#XROSSLINE
これでは不満だったのか?

7 :デフォルトの名無しさん:2001/07/26(木) 23:56
3次元に拡張したやつキボン
n次元に拡張ってできる?

8 :デフォルトの名無しさん:2001/07/27(金) 00:01
n次元に拡張って…
空間は3次元までだろ
大体にして最初の質問は2次元だが

9 :1ではない:2001/07/27(金) 00:06
>>6
全然ダメ、
一つ目は条件分岐ありすぎ
二つ目は割り算使うなんてアホ

10 :デフォルトの名無しさん:2001/07/27(金) 00:06
四次元に拡張したら空間を移動する点になるし、別に何次元でも拡張できるっしょ。

11 :7:2001/07/27(金) 00:11
1次独立なベクトルが n 本とれるという意味で n 次元拡張なんですわ。>>8

12 :デフォルトの名無しさん:2001/07/27(金) 00:22
>>11
そりゃ連立n元m次方程式でいうところのn元では?
3本あったら3本とも一点で交差していれば正解なの?

13 :デフォルトの名無しさん:2001/07/27(金) 00:30
取り敢えず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は交わっている

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

14 :7:2001/07/27(金) 00:39
んーと、、空間を表すときに必要な1次独立なベクトルの数です。
3本があるっていうわけでは(解釈あってる?)ないと思う。
3次元なら (x1,y1,z1)-(x2,y2,z2)
4次元なら (x1,y1,z1,w1)-(x2,y2,z2,w2)
この解って高校あたりで習いましたっけ…?忘れた。(^^;)

15 :デフォルトの名無しさん:2001/07/27(金) 01:01
線分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は凸となる。

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

16 :デフォルトの名無しさん:2001/07/27(金) 06:14
>>9
> 二つ目は割り算使うなんてアホ

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

17 :デフォルトの名無しさん:2001/07/27(金) 06:49
>>7 3次元については
 まず2直線=4点が同じ平面上にあるかどうかを判定して
 次に交差判定をすればいいのでは?

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

18 :デフォルトの名無しさん:2001/07/27(金) 08:30
3次元だったら 先に無限直線同士で交点があるか あれば交点を計算して

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

19 :デフォルトの名無しさん:2001/07/27(金) 09:25
>>1
2次元なら簡単
(X2-X1)*(Y4-Y3)-(Y2-Y1)*(X4-X3)
の値が0なら平行
それ以外は交点がある。

20 :19:2001/07/27(金) 09:30
>>19 補足
実装する場合、
整数だけを対象とするのでなければ
判定にホントに0を使っちゃだめよ。

21 :19:2001/07/27(金) 09:43
>>20 更に補足
平行でないと分かれば
実際の交点は連立方程式を解くだけ。
あとは自分でやってね。

22 :デフォルトの名無しさん:2001/07/27(金) 09:48
>>19=20=21
それは2直線の交差。2線分ではない。

23 :22:2001/07/27(金) 09:50
あれ? 1は2直線の交差でいいのか?

24 :19:2001/07/27(金) 10:23
・・・
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は判定済み)
最速かどうか、それは知らない。

25 :19:2001/07/27(金) 10:24
>>24 補足
どちらかの座標で大小判定すれば終わりでしょ?

26 :19:2001/07/27(金) 10:38
>>25
あ、両方やらんと駄目だわ。

27 :デフォルトの名無しさん:2001/07/27(金) 11:57
>>24
いや考え方は、それが最速じゃない。
あとは実装

28 :デフォルトの名無しさん:2001/07/27(金) 12:02
http://www.yamagame.com/MyWeb/Heart/heart13.html

29 :デフォルトの名無しさん:2001/07/27(金) 13:12
昔、Cマガにのってた線分交差判定ソース。

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;
    }
  }
}

30 :デフォルトの名無しさん:2001/07/27(金) 13:35
交差判定の高速化なんてたいしたこと出来ないだろう。

31 :デフォルトの名無しさん:2001/07/27(金) 13:45
if( rand()%2 )
{
 printf("交差してます");
} else {
 printf("交差してません");

}

32 :1:2001/07/27(金) 13:46
みんな僕の宿題に付き合ってくれて有難う。
これで提出日に間に合います。

33 :デフォルトの名無しさん:2001/07/27(金) 13:48
>>29
int d;
のアドレスにfloat型のまま書き込んだ方がよい

34 :デフォルトの名無しさん:2001/07/27(金) 13:56
>>1
逝ってよし

35 :デフォルトの名無しさん:2001/07/27(金) 13:57
>>32
誰もおめーの相手なんてしてねーよ

36 :デフォルトの名無しさん:2001/07/27(金) 14:17
>>33
>int d;
>のアドレスにfloat型のまま書き込んだ方がよい

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

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

>>35
同意。

37 :デフォルトの名無しさん:2001/07/27(金) 14:44
>>1のレベルをみる限り>>31程度のプログラムで十分だと思うが?

38 :デフォルトの名無しさん:2001/07/27(金) 16:10
ようは
先に近接判定するとかだけで
計算式はどこ見ても同じなんだねえ
まあ当然なんだろうけど

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

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

40 :デフォルトの名無しさん:2001/07/27(金) 21:38
>>38
あと、原点が(0,0)の式を使うか、頂点の一つを原点にするかにも
その人の性格が出るね

41 :デフォルトの名無しさん:2001/07/27(金) 23:28
俺はどっちかいうと 頂点派だな

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

42 :無能な姦理人@Shiri-Q:2001/07/27(金) 23:38
□□□□■□□□□□■□□□□□□□□□□□□□□□□□□□□□
□□□■■□□□□□■□□□□□□□■■■■■■■■■■■■□□
□□■■□□□□□■■■■■■□□□□□□□□□□□□□■■□□
□■■□□■□□□■□□□□■□□□□□□□□□□□□■■□□□
□□■□■■□□■■■□□■■□□□□□□□□□□□■■□□□□
□□□■■□□■■□■■■■□□□□□□□□□□□■■□□□□□
□□■■□□□□□□□■■□□□□□□□□□□□■■□□□□□□
□□■□□□■□□□■■■■□□□□□□□□□□■□□□□□□□
□■■■■■■□□■■□□■■□□□□□□□□□■□□□□□□□
□□□□■□□□■■□□□□■■□□□□□□□□■□□□□□□□
□□■□■□■□□□□■■□□□□□□□□□□□■□□□□□□□
□□■□■□■□□□□□■■□□□□□□□□□□■□□□□□□□
□■■□■□■□□□□□□□□□□□□□□□□□■□□□□□□□
□■□□■□□□□■■■□□□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□■■■□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□□□■■□□□□□□■■■■□□□□□□□





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

43 :デフォルトの名無しさん:2001/07/28(土) 17:38
age

44 :デフォルトの名無しさん:2001/07/30(月) 07:13
n次元で通用する簡単な交差判定アルゴリズムもあるよ。

45 :デフォルトの名無しさん:2001/07/30(月) 11:06
>>44教えてプリーズ!

46 :デフォルトの名無しさん:2001/07/30(月) 15:32
29の式のdを求めるところで、符号だけ見るんで
掛け算の代わりにXORを使うのってだめ?

47 :デフォルトの名無しさん:2001/07/30(月) 17:38
どうにもこうにも線形代数の教科書を紐解けば
軽く解法が載ってるような気もする。

48 :デフォルトの名無しさん:2001/07/30(月) 17:43
>>47
本を読めない or 読んでもプログラムに書けないDQNもいる

49 :デフォルトの名無しさん:2001/07/30(月) 17:53
DQN=ドキュンね。なんかいいな、それ(藁

50 :デフォルトの名無しさん:2001/07/30(月) 19:44
>>46
ダメ、直線の両端点がもう一方の直線の左右に分かれる場合がd<0なの

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

51 :46:2001/07/30(月) 20:18
>>50
すまん、dを求める際の全部の掛け算じゃなくって、どまんなかのp1とp2の部分の
合成の掛け算を指してたのじゃ
たしかGraphicsGemsのIIIあたりにあった記憶があるんだけど手元になくって

52 :デフォルトの名無しさん:2001/07/30(月) 20:56
XORでもいいけど、最近のCPUじゃあんまり高速化につながらない。整数掛算だって早いもの

53 :デフォルトの名無しさん:2001/07/30(月) 21:03
でもPenシリーズ(元祖,II,!!!,4)の掛算は浮動小数点の掛算より遅いんじゃなかった?

54 :デフォルトの名無しさん:2001/07/30(月) 22:08
いやほら、floatをintに代入してXORして符号ビットだけ見ればいいからと
思ったのよ
確かにXORって掛け算より使用頻度少なそうだから、最近じゃCPUから
命令無くされてるかも?
(NOTやAND,ORの組合わせにされちゃう?)

55 :デフォルトの名無しさん:2001/07/30(月) 22:08
>>54
なんぼなんでもそれはない。

56 :デフォルトの名無しさん:2001/07/31(火) 07:44
いや 掛算は浮動小数点計算する方のユニットで計算されるでしょ
だから整数演算ばかりでも掛算がたまにあるとそっちのユニットも使われて並列性があがるとか?

57 :デフォルトの名無しさん:2001/07/31(火) 21:48
ペンティアムプロセッサの最適化
http://www.csl.sony.co.jp/person/fnami/pentopt.htm

58 :デフォルトの名無しさん:2001/07/31(火) 22:36
>>57
古っ。

59 :デフォルトの名無しさん:2001/07/31(火) 23:03
0近辺だと実数掛け算とXORだと丸めの分、符号が
違くなる気がするな

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

61 :デフォルトの名無しさん:2001/08/01(水) 01:34
>>54
P5では論理演算はNANDのみになります

62 :デフォルトの名無しさん:2001/08/01(水) 12:03
>>61
がいしゅつです

63 :デフォルトの名無しさん:2001/08/01(水) 12:52
VC++は浮動小数点から整数に変換するとパイプラインがクリアされるから
2、3個の分岐のために整数にしても逆効果になるよ
テクスチャ座標が0.5ずれる3Dカードのドライバは
高速化のために丸めモードを無視して整数変換しているわけ
8087自体は古いのでしょうがないがintelがアホなことは確か

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

65 :デフォルトの名無しさん:2001/08/02(木) 23:21
多分>>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次元に拡張するのでも同じとなる。

66 :デフォルトの名無しさん:2001/08/03(金) 20:34
>>64
CPUの性能がいくら上がっても乗算は加減算よりもコストがかかります。

67 :デフォルトの名無しさん:2001/08/03(金) 22:58
>>66
それほんと?
乗算テーブルをでかく持てないからかな(コスト的に)

68 :デフォルトの名無しさん:2001/08/04(土) 06:46
>>66 でも加算も 浮動小数点だと、結構大変だよ

69 :デフォルトの名無しさん:2001/08/06(月) 12:58
    乗算スループット 乗算レイテンシ
Athlon   1        4
P6     2        5
    加算スループット 加算レイテンシ
Athlon   1        4
P6     1        3

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

70 :デフォルトの名無しさん:2001/08/06(月) 13:49
1って宿題が目的だったの?
てっきりゲームでも作ろうともがく厨房かと思った
もし後者ならば今後もさまざまな判定方法で苦しむと思うから
3Dゲーム開発の本を一冊買いなさい
たいていの判定方法は書いてあります。

71 :デフォルトの名無しさん:2001/08/06(月) 15:09
どうでもいいが、2次元でも3次元でも
平行でないかぎりいつかは交差するだろ?
平行か否かを判定したいの?

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

72 :デフォルトの名無しさん:2001/08/06(月) 15:12
>>71
3次元でも??

73 :デフォルトの名無しさん:2001/08/06(月) 15:16
>>71
3次元の場合は
2直線が同一平面上あって、なおかつ平行でない場合のみ
交差すると思われ。

74 :デフォルトの名無しさん:2001/08/06(月) 15:16
すんません。三次元はうそでした。

75 :デフォルトの名無しさん:2001/08/06(月) 16:42
捩れの位置関係があると思われ<3次元

76 :デフォルトの名無しさん:2001/08/10(金) 08:42
定期上げ

77 :デフォルトの名無しさん:2001/08/10(金) 12:57
>>65 に「優」はやれん
>>29 は惜しいところだが「不可」

78 :デフォルトの名無しさん:2001/08/11(土) 10:34
線分の交差判定等のアルゴリズムについて勉強したければ,計算幾何学の本を
読むことをお勧めします.「計算幾何学」で検索すれば,おそらく5冊ほど出て
きます.計算幾何学というとプレパラータ,浅野哲夫両先生が有名ですが,他の
著者(+監訳者)も,アルゴリズムの分野で有名な先生方ばかりです.私は
今井夫妻の本で学びました.

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

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

21 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)