多面体間(出来れば非凸多面体)の距離計測を行う際に有効な策として、

外積(ベクトル積)以外の方法で最短距離を求めることが出来る策があれば教えて下さい。
C++&OpenGLで計算を行い描写するプログラムを作成したいと考えています。
よろしくお願いします。

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2008/07/23 00:24:02
  • 終了:2008/07/27 02:23:21

回答(2件)

id:ita No.1

ita回答回数203ベストアンサー獲得回数472008/07/23 18:08:06

ポイント50pt
rmin=10000000
for(v=Aの全ての頂点){
for(s=Bの全ての面){
    p = vからsへの垂線の足
    if(pが多角形sの内部) r=pとvの距離
    else r=vとsの各頂点の距離の最小値

    if(r<rmin)rmin=r
}}
AとBを入れ換え同じ処理

て感じですね。このpが多角形の内部にいるかどうか、てのに普通は外積を使うと。それを使わないとすると、たとえばsが凸多角形であることが保証されてるならsの重心(簡単に計算できる)をgとおき、線分gp とsの各辺が交差するかしらべ、交差するものがあればpは外側、なければ内側、と判定できます。

線分と線分が交差するかどうかの判定方法は探せばすぐ出てきます。

http://www5d.biglobe.ne.jp/~tomoya03/shtml/algorithm/Intersectio...

id:tominao

なるほど。交差判定を行う際、「重心と面との距離」という切り口も確かにありますね!

まずは凸多角形という条件付で考えていこうと思っているので、URLとともに参考にさせていただこうと思います。

ありがとうございました。

2008/07/24 22:28:29
id:Z9M9Z No.2

Z9M9Z回答回数343ベストアンサー獲得回数112008/07/24 20:29:17

ポイント50pt

二線分間の最短距離となる線分がどちらかの端点を含むとは限らないので、二多面体間の最短距離となる線分がいずれかの頂点を含むという仮定はよろしくありません。辺と辺とが最短距離になる位置関係の場合、拾えなくなります。

http://www.dh.aist.go.jp/~kawachi/ncmd-j.html

相互に十分に離れているのなら、両者の中心を結ぶ直線を使って全頂点をソートするとか、URLで主張されているようにボロノイ領域を利用するとかによって、「近い方」からシラミツブシ的&分枝限定法的に探す方法が思い浮かびます。

id:tominao

そうなんです。

辺と辺との距離が最短となる場合を考えると、総当り的に拾おうとすると、

モデルが大きい場合には対応できないなぁと考えています。

ご紹介頂いたページは、私も参考にさせていただいていた論文です。

ご紹介いただいて、やはりこの手法でやってみようと感じました。

ある程度回答もおさまったようなので、

これにて締め切らせていただきます。

ご解答頂いた方々、ありがとうございました。

2008/07/25 23:23:39
  • id:ita
    あいた、そうか辺ー辺がありますね。

    線形計画法のシンプレックス法では、N次元空間の多面体の頂点を隣隣とたどって
    一次式の最小値を求めます。そういう感じで、まずは二つの多面体の重心を結ぶ線
    へ射影して辺や頂点の候補を絞る、てことが可能かも。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません