動く線分と「点」の衝突

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
アバター
SUE
記事: 41
登録日時: 7年前

動く線分と「点」の衝突

#1

投稿記事 by SUE » 7年前

SUEです。あからさまに前回の続きです。

今回やりたいのは、動く線分上に静止した点が来る時刻を求めることです。いろんなやり方があるとは思いますが、僕はこのサイトを参考にして(一応サイトと添付した図の文字は対応しています)、

線分L0,L1のそれぞれの終点を通る直線と、Ltの始点と図のAを通る直線との交点をPとし、PとLtの終点が一致するtを求める、という考え方をしました。
すると、そのサイトより、交点P = S2 + v2 * t2, Ltの終点 = S2 + v2 * t となり、再びサイトより、t2 = ( v × v1 ) / ( v1 × v2 ) だから、これと等しくなるtを求めればいい・・・
のですが、式展開の途中で見事に挫折しました。どなたか助力願います。もっといいアプローチもあると思います。
添付ファイル
figure2.png
figure2.png (2.41 KiB) 閲覧数: 798 回
pop'n music 20 fantasia ポップンクエストPhase MAX Ⅱ ムラクモ/少年は空を辿る【Power Of Nature】

たいちう
記事: 418
登録日時: 9年前

Re: 動く線分と「点」の衝突

#2

投稿記事 by たいちう » 7年前

前回の質問でも思ったのですが、何故対象が動いている必要があるのですか?
静止している物体の判定ならば、数学的に数段簡単です。
特に重い処理でもないので、フレーム毎に静止した物体の衝突判定をすれば良いでしょう。

何秒後に衝突するかを予め知りたい場合も、静的な衝突判定で事足ります。
例えば現時点から1秒後、2秒後、3秒後、、、の座標で静的な衝突判定を行い、
最初に衝突した時と、その直前の衝突していない時の間を2分探索することで、
必要な精度で衝突の時刻を求めることが出来ます。

例では1秒となっている時間間隔は、判定する物体の大きさ・相対距離・速度に応じて
調整してください。衝突しない場合の判定打ち切りの判断も必要です。

静的な衝突判定よりは手間がかかりますが、数学的な難易度は上がっていません。
数学的に直接求める必要がないならば、解決していると思うのですが。

beatle
記事: 1280
登録日時: 8年前
住所: 埼玉
連絡を取る:

Re: 動く線分と「点」の衝突

#3

投稿記事 by beatle » 7年前

衝突対象が点だから、フレーム毎に衝突判定をするとすり抜けちゃって判定できないんじゃないでしょうか?

アバター
GRAM
記事: 164
登録日時: 9年前
住所: 大阪

Re: 動く線分と「点」の衝突

#4

投稿記事 by GRAM » 7年前

beatle さんが書きました:衝突対象が点だから、フレーム毎に衝突判定をするとすり抜けちゃって判定できないんじゃないでしょうか?
問題の難易度は前回と変わっておらず、どうせ大雑把な判定しかできないので
ある瞬間に、当たっているかどうかの判定だけならば微小時間tの間に
線分が作る四角形領域、もしくは三角形領域2つ分(見かけ上微小時間内に線分が回転しているように見える場合)
の中に、点が存在するか否かを確かめればいいでしょう。

あるフレームと次のフレーム(もしくは前のフレーム)の線分の位置を調べれば、
(ごくまれにすり抜ける場合もあるが)だいたい判定できると思います。

ある多角形領域内に点が存在するかどうかを判定するのは簡単な問題です。
(各頂点から点へのベクトルと、各辺との外積をとってすべてのベクトルの向きが一致するか確かめればいい。)

fulls
記事: 72
登録日時: 8年前
住所: 埼玉

Re: 動く線分と「点」の衝突

#5

投稿記事 by fulls » 7年前

SUEさんは線の上で点が止まった時刻を知ること自体が目的なのですか?
他に目的があったりしませんか?
例えば、3Dで動く物体と動く壁とのあたり判定をしたいなど。
もしそれがあるなら違った解決策とかもアドバイスできる(私は経験が浅いですし発想も乏しいのでできる自信はあまりありませんが)と思うのですが。

アバター
SUE
記事: 41
登録日時: 7年前

Re: 動く線分と「点」の衝突

#6

投稿記事 by SUE » 7年前

返信遅れました。すみません。この件に関しては自己解決しました。添付した図にあるとおりです。

そんなことより、色々お騒がせしているみたいで申し訳ありません。できる限りお答えします。

>>たいちうさん
仰る通りで、確かに僕の行おうとしていることで、対象が動いている必要は必ずしもありません。また、二分探索も大事なアルゴリズムです、すっかり忘れていました。
僕が対象が動いていることについてしつこく質問したのは、敢えて言えば細かいこと拘る性格が災いしてどうしても気になったからです。ただしこれが駄目ならば
いい加減諦めようとは思っていました。何度もすいませんでした。

>>beatleさん
実は対象は点ではないのですが、点にして考えると楽だと思ったので、このような題になりました。

>>GRAMさん
問題の難易度は変わっていないと聞いて焦りましたが、この式は多分あっている筈です。様々確かめました。間違っていたら教えてください。

>pefs3dさん
いいえ、僕の目的は違うことですが、途中でこのような問題が出てきたという感じです。
具体的な方法は余り美しくないものなので、ここには書けませんが、とりあえず問題はすべて解決しました(と思います)。
書くとしたら後日日記とかに書くと思います。その時にアドバイスがあれば是非お願いします。

総じて妙な質問を連発してしまいましたが、心配していただいてありがとうございました。これ以上この手の質問はしない予定です。
それでは、これで解決とします。
添付ファイル
figure3.png
v1×v2 + (v1×v4+v3×v2)t + (v3×v4)t^2 = 0
v3とv4が平行なら一次式。加えて交点でない、かつ、内側にいる判定をして外積は計7回。
figure3.png (1.95 KiB) 閲覧数: 620 回
pop'n music 20 fantasia ポップンクエストPhase MAX Ⅱ ムラクモ/少年は空を辿る【Power Of Nature】

閉鎖

“C言語何でも質問掲示板” へ戻る