特許

J-GLOBAL ID：200903029127001069

最接近点探索方法及びその前処理方法

発明者： 佐藤 裕一 ,  平田 光徳 ,  永嶋 史朗 ,  丸山 次人
出願人/特許権者： 富士通株式会社
代理人 (1件)： 斉藤 千幹
公報種別：公開公報
出願番号（国際出願番号）：特願平6-209008
公開番号（公開出願番号）：特開平7-134735
出願日： 1994年09月02日
公開日（公表日）： 1995年05月23日
要約：

【要約】【目的】 少ない計算負荷で凸多面体間あるいは非凸多面体間の最接近点探索を実行する。【構成】 2つの凸多面体K1,K2の最接近点を探索する場合、有向グラフ型構造データを作成して各凸多面体を表現する。最接近点探索処理部15は、2つの凸多面体K1,K2の差集合(K1-K2)である差凸多面体までの最接近点を逐次的に求めて最終的に各凸多面体K1,K2上の最接近点を求める。最接近点を求める過程で実行される内積評価において、最接近点探索処理部15は逐次的に求まる差凸多面体までの最接近点に対応する各凸多面体上の最接近点が格子点上に存在するか、辺上に存在するか、ポリゴン上に存在するか判断し、有向グラフ型構造データよりそれぞれの場合において内積評価に使用する格子点を求め、該格子点の位置ベクトルを用いて内積評価する。

請求項（抜粋）：

2つの凸多面体の差集合である差凸多面体上のp個のポイントを要素とする部分集合で形成される形状迄の最接近点を求め、該最接近点の位置ベクトルと各凸多面体の格子点の位置ベクトルとの内積を評価し、評価結果に基づいて該最接近点が、原点から差凸多面体までの最接近点と一致するか判定し、一致しない場合には部分集合を変更し、最終的に原点から差凸多面体までの最接近点を求めて各凸多面体の最接近点を求める最接近点探索方法において、凸多面体の各表面多角形(ポリゴン)の下方に該ポリゴンの要素である格子点、辺を配列し、格子点、辺の下方にそれぞれ格子点、辺を構成するポリゴンを配列してなる有向グラフ型構造データにより各凸多面体を表現し、前記部分集合で形成される形状の最接近点に対応する各凸多面体上の最接近点が格子点上に存在するか、辺上に存在するか、ポリゴン上に存在するか判断し、格子点上に存在する場合には有向グラフ型構造データより該格子点を構成するポリゴンを求め、該ポリゴンの格子点を前記内積評価に用い、辺上に存在する場合には有向グラフ型構造データより該辺を構成するポリゴンを求め、該ポリゴンの格子点を前記内積評価に用い、ポリゴン上に存在する場合には該ポリゴンの格子点を前記内積評価に用いることにより原点から差凸多面体までの最接近点を求めて各凸多面体の最接近点を求める最接近点探索方法。

IPC (3件)：

G06F 17/50 ,  G05B 19/4093 ,  G05D 1/02

FI (2件)：

G06F 15/60 400 A ,  G05B 19/403 E