交差判定アルゴリズム
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
NGNG判断するアルゴリズムで高速なのってどんなのがあるのでしょう？
0028デフォルトの名無しさん
NGNG0029デフォルトの名無しさん
NGNGbool 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;
}
}
}
0030デフォルトの名無しさん
NGNG0031デフォルトの名無しさん
NGNG{
printf("交差してます");
} else {
printf("交差してません");
}
00321
NGNGこれで提出日に間に合います。
0033デフォルトの名無しさん
NGNGint d;
のアドレスにfloat型のまま書き込んだ方がよい
0034デフォルトの名無しさん
NGNG逝ってよし
0035デフォルトの名無しさん
NGNG誰もおめーの相手なんてしてねーよ
0036デフォルトの名無しさん
NGNG＞int d;
＞のアドレスにfloat型のまま書き込んだ方がよい
なるほど、参考になります。
いま思いついたんだけど、たしか浮動小数点って
最上位ビットが符号ビットになってるんだよね。
そうならば、d > 0 の部分を工夫できるかも。
>>35
同意。
0038デフォルトの名無しさん
NGNG先に近接判定するとかだけで
計算式はどこ見ても同じなんだねえ
まあ当然なんだろうけど
結局 (a*b±c*d) みたいな計算が３つか・・・
00391
NGNG他にも>>29さん他アドバイスを下さった皆さんありがとうございます。
これで心置きなく逝くことが出来そうです。
尚、>>29さんのコードを試したら座標にマイナス値が含まれる場合うまく値を
返さないケースがあったことを報告します＞書き方がまずかっただけかも
あ、ちなみに32は私じゃないです。
なにはともあれ助かりました。ありがとうございます。
0040デフォルトの名無しさん
NGNGあと、原点が(0,0)の式を使うか、頂点の一つを原点にするかにも
その人の性格が出るね
0041デフォルトの名無しさん
NGNG理由は 浮動小数点演算の時に精度が良さそうだし、
整数演算でも桁溢れの率が減りそうだから
0042無能な姦理人＠Shiri-Q
NGNG□□□■■□□□□□■□□□□□□□■■■■■■■■■■■■□□
□□■■□□□□□■■■■■■□□□□□□□□□□□□□■■□□
□■■□□■□□□■□□□□■□□□□□□□□□□□□■■□□□
□□■□■■□□■■■□□■■□□□□□□□□□□□■■□□□□
□□□■■□□■■□■■■■□□□□□□□□□□□■■□□□□□
□□■■□□□□□□□■■□□□□□□□□□□□■■□□□□□□
□□■□□□■□□□■■■■□□□□□□□□□□■□□□□□□□
□■■■■■■□□■■□□■■□□□□□□□□□■□□□□□□□
□□□□■□□□■■□□□□■■□□□□□□□□■□□□□□□□
□□■□■□■□□□□■■□□□□□□□□□□□■□□□□□□□
□□■□■□■□□□□□■■□□□□□□□□□□■□□□□□□□
□■■□■□■□□□□□□□□□□□□□□□□□■□□□□□□□
□■□□■□□□□■■■□□□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□■■■□□□□□□□□□□■□□□□□□□
□□□□■□□□□□□□□■■□□□□□□■■■■□□□□□□□
続きはコチラです
http://www.geocities.com/entry_k/main/main01.html
0043デフォルトの名無しさん
NGNG0044デフォルトの名無しさん
NGNG0045デフォルトの名無しさん
NGNG0046デフォルトの名無しさん
NGNG掛け算の代わりにXORを使うのってだめ?
0047デフォルトの名無しさん
NGNG軽く解法が載ってるような気もする。
0048デフォルトの名無しさん
NGNG本を読めない or 読んでもプログラムに書けないDQNもいる
0049デフォルトの名無しさん
NGNG0050デフォルトの名無しさん
NGNGダメ、直線の両端点がもう一方の直線の左右に分かれる場合がd<0なの
内積理解してれば方程式云々以前の問題なんだけどね
005146
NGNGすまん、dを求める際の全部の掛け算じゃなくって、どまんなかのp1とp2の部分の
合成の掛け算を指してたのじゃ
たしかGraphicsGemsのIIIあたりにあった記憶があるんだけど手元になくって
0052デフォルトの名無しさん
NGNG0053デフォルトの名無しさん
NGNG0054デフォルトの名無しさん
NGNG思ったのよ
確かにXORって掛け算より使用頻度少なそうだから、最近じゃCPUから
命令無くされてるかも?
(NOTやAND,ORの組合わせにされちゃう?）
0055デフォルトの名無しさん
NGNGなんぼなんでもそれはない。
0056デフォルトの名無しさん
NGNGだから整数演算ばかりでも掛算がたまにあるとそっちのユニットも使われて並列性があがるとか？
0057デフォルトの名無しさん
NGNGhttp://www.csl.sony.co.jp/person/fnami/pentopt.htm
0058デフォルトの名無しさん
NGNG古っ。
0059デフォルトの名無しさん
NGNG違くなる気がするな
006050
NGNGスマソ、勘違いしてた
符号が逆なことだけ分かればいいからXORで行ける
でもアセンブラで気合入れて書かんと効果はなさそうだね
0061デフォルトの名無しさん
NGNGP5では論理演算はNANDのみになります
0062デフォルトの名無しさん
NGNGがいしゅつです
0063デフォルトの名無しさん
NGNG２、３個の分岐のために整数にしても逆効果になるよ
テクスチャ座標が0.5ずれる3Dカードのドライバは
高速化のために丸めモードを無視して整数変換しているわけ
8087自体は古いのでしょうがないがintelがアホなことは確か
0064デフォルトの名無しさん
NGNG掛け算の数で勝負みたいなとこあったじゃない?(ワークエリアを使ってでも）
今時分のCPUみたく掛け算のコストが加減算程度まで下がったら、そのへんて
見直してるのかしら
そこんとこどーよ＞ 一松信
(ぉぃぉぃぉぃ)
0065デフォルトの名無しさん
NGNG座標をパラメーター表示するので考えてみた。
(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次元に拡張するのでも同じとなる。
0066デフォルトの名無しさん
NGNGCPUの性能がいくら上がっても乗算は加減算よりもコストがかかります。
0067デフォルトの名無しさん
NGNGそれほんと?
乗算テーブルをでかく持てないからかな(コスト的に）
0068デフォルトの名無しさん
NGNG0069デフォルトの名無しさん
NGNGAthlon １ ４
P6 ２ ５
加算スループット 加算レイテンシ
Athlon １ ４
P6 １ ３
SSEは使い物にならないから、やっぱりAthlonの勝ち
0070デフォルトの名無しさん
NGNGてっきりゲームでも作ろうともがく厨房かと思った
もし後者ならば今後もさまざまな判定方法で苦しむと思うから
3Dゲーム開発の本を一冊買いなさい
たいていの判定方法は書いてあります。
0071デフォルトの名無しさん
NGNG平行でないかぎりいつかは交差するだろ？
平行か否かを判定したいの？
実用上はある範囲内でという条件がつくだろうけど、それも不要ですか？
0072デフォルトの名無しさん
NGNG3次元でも??
0073デフォルトの名無しさん
NGNG3次元の場合は
2直線が同一平面上あって、なおかつ平行でない場合のみ
交差すると思われ。
0074デフォルトの名無しさん
NGNG0075デフォルトの名無しさん
NGNG0076デフォルトの名無しさん
NGNG0078デフォルトの名無しさん
NGNG読むことをお勧めします．「計算幾何学」で検索すれば，おそらく5冊ほど出て
きます．計算幾何学というとプレパラータ，浅野哲夫両先生が有名ですが，他の
著者（＋監訳者）も，アルゴリズムの分野で有名な先生方ばかりです．私は
今井夫妻の本で学びました．
ある点が，２点を通る直線によって作られる二つの半平面のどちらの上にあるか
（直線のどちら側にあるか）を判定するのには，一般に，三角形の符号付面積が
用いられます（除算による計算誤差を回避できる）．
線分ab と線分cd が交差する必要十分条件は，直線ab からみて c と d が
同一半平面上になく，かつ，直線cd からみて a と b が同一半平面上にない
ことです．
■ このスレッドは過去ログ倉庫に格納されています