(57)【要約】【課題】凸多面体の支持点探索法を提供する．【解決手段】質問ベクトルｑに対する凸多面体Ｑの支持点を探索するシステムにおいて，Ｑの辺と面と頂点を２次元直交座標系のグラフＧの辺と点と面にそれぞれ１対１に対応する関数ｈを所持させ，ｈ（ｑ）を質問点とする点位置決定問題を解き，Ｇの面に対応するＱの頂点を支持点とすることを特徴とするシステム．【選択図】図１
2008282370.tif 000002
【特許請求の範囲】
【請求項１】
３次元凸多面体Ｑと３次元質問ベクトルｑが与えられた時，Ｑの頂点の位置ベクトルとｑの内積を最大とする頂点ｖを探索する機能を持つ計算機システムにおいて，３次元ベクトルａの偏角と天頂角をφとθとするとき，ａを２次元φθ直交座標系の点（φ，θ）に１対１に対応させる関数をｈとし，Ｑの面ｆｋ（ｋ＝１，２，，，，ｋｆＱ）の単位法線ベクトルをｎｆｉとするとき，矩形領域Ｓ＝｛（φ，θ）｜０≦φ≦２π，０≦θ≦π｝を曲線集合｛ｈ（（１−ｔ）・ｎｆｉ＋ｔ・ｎｆｊ）｜０≦ｔ≦１，１≦ｉ≦ｋｆＱ，１≦ｊ≦ｋｆＱ，ｉ≠ｊ，ｆｉとｆｊは互いに隣り合ったＱの面｝によって複数の領域に分割する手段１と，該分割領域群の中からｈ（ｑ）を囲む分割領域を探索する手段２を有し，探索して得た分割領域に対応するＱの頂点をｖとすることを特徴とするシステム．
【請求項２】
３次元凸多面体Ｑと３次元質問ベクトルｑが与えられた時，Ｑの頂点の位置ベクトルとｑの内積を最大とする頂点ｖを探索する機能を持つ計算機システムにおいて，３次元ベクトルａの偏角と天頂角をφとθとするとき，ａを２次元φθ直交座標系の点（φ，θ）に１対１に対応させる関数をｈとし，Ｑの各頂点ｖｉ（ｉ＝１，２，，，，ｋｖＱ）に対して，ｖｉを支持点とする１つ以上の平面Ｐｉ，ｊ（ただし１≦ｊ≦ｕ（ｉ）とし，ｕ（ｉ）はｖｉに応じて定めた正の整数とする）を対応させる手段１と，Ｐｉ，ｊの単位法線ベクトルをｎＰｉ，ｊとするとき，φθ直交座標系の矩形領域Ｓ＝｛（φ，θ）｜０≦φ≦２π，０≦θ≦π｝内の点集合｛ｈ（ｎＰｉ，ｊ）｝の中から点ｈ（ｑ）の近傍にある一点ｈ（ｎＰｉ，ｊ）を探索する手段２と，探索して得たｈ（ｎＰｉ，ｊ）に対応するＱの頂点ｖｉを起点にして頂点ｖを探索して得る手段３を所持させる事を特徴とするシステム．
【発明の詳細な説明】
【技術分野】
【０００１】  ３次元凸多面体Ｑと任意の３次元質問ベクトルｑが与えられた時，Ｑの頂点の位置ベクトルとｑの内積を最大にするＱの頂ｖはｑに対するＱの支持点と呼ばれ，本発明は該支持点を探索する計算機システムの実現技術に関する．
【背景技術】
【０００２】  多面体間の距離計算手法は，ＣＡＤ／ＣＡＭ，ロボット制御，コンピュータグラフィックス，その他数多くの局面で必要とされる基本的な図形処理ツールである．近年，計算機を用いたシミュレーションやアニメーションが頻繁に行われ，衝突防止を目的としてダイナミックに位置が変動する多面体間の距離計算が繰り返し行われている．この際，多面体の頂点が多い場合，距離計算の処理性能の大幅な劣化が起こる．そのため，長年研究者の間で多面体間高速距離計算手法の開発が競われてきた．【０００３】  ３次元凸多面体Ｐ，Ｑ間の最短距離計算手法として，ＧＪＫ法〔Ｅ．Ｇ．Ｇｉｌｂｅｒｔ，Ｄ．Ｗ．Ｊｏｈｎｓｏｎ  ａｎｄ  Ｓ．Ｓ．Ｋｅｅｒｔｈｉ，Ｆａｓｔ  Ｐｒｏｃｅｄｕｒｅ  ｆｏｒ  Ｃｏｍｐｕｔｉｎｇ  ｔｈｅ  Ｄｉｓｔａｎｃｅ  ｂｅｔｗｅｅｎ  Ｃｏｍｐｌｅｘ  Ｏｂｊｅｃｔｓ  ｉｎ  Ｔｈｒｅｅ−Ｄｉｍｅｎｓｉｏｎａｌ  Ｓｐａｃｅ，ＩＥＥＥ  Ｊｏｕｒｎａｌ  ｏｆ  Ｒｏｂｏｔｉｃｓ  ａｎｄ  Ａｕｔｏｍａｔｉｏｎ，Ｖｏｌ．４，Ｎｏ．２，１９３−２０３，Ａｐｒｉｌ（１９８８）〕が公知である．ミンコフスキー差（Ｐ−Ｑ）を｛ｐ−ｑ｜ｐ∈Ｐ，ｑ∈Ｑ｝と定義するとき，ＧＪＫ法では，凸多面体間の最短距離計算問題を３次元凸多面体（Ｐ−Ｑ）と座標原点ｒとの間の最短距離計算問題に変換し，問題を解決している．（Ｐ−Ｑ）とｒとの最短距離計算は，適当に選択した（Ｐ−Ｑ）の高々４個の頂点の凸包（単体）を初期単体として構成し，該単体を構成する頂点の内の１点を他の（Ｐ−Ｑ）の頂点ｖに置き替えることによって，該単体全体をｒに近づくように改造することを繰り返す収束計算により実現されている．ｖを求めるには，ｒから単体への最短点ｓを求め，ｓからｒに向かうベクトルｑを質問ベクトルとし，ｑに対するＰの支持点ｐ１と−Ｑの支持点ｑ１を求め，ｖ＝ｐ１＋ｑ１とする．ＧＪＫ法では，Ｐと−ＱをＰと−Ｑの各面を表す複数の線形不等式の解の共通集合で表現し，目的関数をｑが法線となる平面とする３次元線形計画法を解くことによってｐ１とｑ１を求める．ｋｆＰをＰの面の数とすると，ｋｆＰ個の線形不等式を制約として持つ３次元線形計画法を解く手間はＯ（ｋｆＰ）であることが知られている〔今井浩・今井佳子著，計算幾何学，共立出版〕．ｋｆＰやｋｆＱが大きいと最適解を求めるための計算時間が長くかかることが欠点となっている．しかも，ｐ１とｑ１の計算は収束計算のたびに行う必要があるため，支持点探索法に対する要求が強い．【０００４】  支持点探索を高速化する方法として，ｋｖＰ個の頂点を持つ凸多体ＰのＨｉｅｒａｒｃｈｉｃａｌ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎと呼ばれる計算高速化支援データ構造を前処理として求めておき，支持点計算時に，これを活用すればＯ（ｌｏｇｋｖＰ）で支持点計算ができる〔Ｄ．Ｄｏｂｋｉｎ，Ｄ．Ｋｉｒｋｐａｔｒｉｃｋ，Ｄｅｔｅｒｍｉｎｉｎｇ  ｔｈｅ  ｓｅｐａｒａｔｉｏｎ  ｏｆ  ｐｒｅｐｒｏｃｅｓｓｅｄ  ｐｏｌｙｈｅｄｒａ−  ａ  ｕｎｉｆｉｅｄ  ａｐｐｒｏａｃｈ，Ｐｒｏｃ．ｏｆ  ＩＣＬＡＬＰ  ’９０，４００−４１３，１９９０，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ４４３．〕．しかしながら，Ｈｉｅｒａｒｃｈ���ｃａｌ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎの必要メモリ量とその手間はそれぞれ最適値であるＯ（ｋｖＰ），Ｏ（ｌｏｇｋｖＰ）であるものの，安定的に計算機に実装できた例がないと言われており，しかもＯ（ｋｖＰ），Ｏ（ｌｏｇｋｖＰ）の係数が大きく，その技術の実用化には困難が伴う．
【発明の開示】
【発明が解決しようとする課題】
【０００５】  質問ベクトルｑが与えられた時，ｑに対する３次元凸多面体Ｑの支持点を求めるための，必要メモリ容量と手間が少なく，かつ安定的に計算機に実装が可能なシステムの開発が本発明の課題である．
【課題を解決するための手段】
【０００６】  課題を解決するために，特許請求項１の発明は，３次元ベクトルａの偏角と天頂角をφとθとするとき，ａを２次元φθ直交座標系の点（φ，θ）に１対１に対応させる写像をｈとし，Ｑの面ｆｋ（ｋ＝１，２，，，，ｋｆＱ）の単位法線ベクトルをｎｆｉとするとき，矩形領域Ｓ＝｛（φ，θ）｜０≦φ≦２π，０≦θ≦π｝を曲線集合｛ｈ（（１−ｔ）・ｎｆｉ＋ｔ・ｎｆｊ）｜０≦ｔ≦１，１≦ｉ≦ｋｆＱ，１≦ｊ≦ｋｆＱ，ｉ≠ｊ，ｆｉとｆｊは互いに隣り合ったＱの面｝によって複数の領域に分割する手段１と，該分割領域群の中からｈ（ｑ）を囲む分割領域を探索する手段２を所持させる．【０００７】  また，課題を解決するために，特許請求項２の発明は，３次元ベクトルａの偏角と天頂角をφとθとするとき，ａを２次元φθ直交座標系の点（φ，θ）に１対１に対応させる関数をｈとし，Ｑの各頂点ｖｉ（ｉ＝１，２，，，，ｋｖＱ）に対して，ｖｉを支持点とする１つ以上の平面Ｐｉ，ｊ（ただし１≦ｊ≦ｕ（ｉ）とし，ｕ（ｉ）はｖｉに応じて定めた正の整数とする）を対応させる手段１と，Ｐｉ，ｊの単位法線ベクトルをｎＰｉ，ｊとするとき，φθ直交座標系の矩形領域Ｓ＝｛（φ，θ）｜０≦φ≦２π，０≦θ≦π｝内の点集合｛ｈ（ｎＰｉ，ｊ）｝の中から点ｈ（ｑ）の近傍にある一点ｈ（ｎＰｉ，ｊ）を探索する手段２と，探索して得たｈ（ｎＰｉ，ｊ）に対応するＱの頂点ｖｉを起点にしてｑに対するＱの支持点ｖを探索して得る手段３を所持させる．
【作用】
【０００８】  特許請求項１の手段１は，凸多面体Ｑの辺と面と頂点を枝に対して１対１に対応させられた枝と頂点を持つＳの分割グラフＧを設定し，質問ベクトルｑに応じたＱの支持点を探索する問題を，質問点ｈ（ｑ）を含むようなＧの面を探索する点位置決定問題に変換して解決することを可能にする．手段２は質問点ｈ（ｑ）を含むようなＧの面を探索する点位置決定問題を実際に解決し，探索して得たＧの面に対応するＱの頂点をｑに対する支持点ｖとして得る作用をする．
【０００９】  特許請求項２では特許請求項１で述べたようにＳ内にＧを明示的に描く代わりに，手段１はＱの頂点ｖｉに対応するＧの各面ｆｉ内に含まれるｕ（ｉ）個の点ｈ（ｎＰｉ，ｊ）（ｊ＝１，２，，，ｕ（ｉ））をＳ内に配置する作用をする．手段２はＳ内に配置された複数の点ｈ（ｎＰｉ，ｊ）の中から質問点ｈ（ｑ）の近傍にあるものを探索する作用をし，手段３は，探索して得たｈ（ｎＰｉ，ｊ）に対応するＱの頂点ｖｉを起点にしてｑに対するＱの支持点ｖを探索して得る手段３を所持させる．
【発明を実施するための最良の形態】
【００１０】  特許請求項１では，凸多面体の支持点探索を必要とするプログラムに本発明を組み込む形態で実施される．なお，前処理プログラムに特許請求項１の手段１を実装し，点位置決定問題解決処理を高速化するためのデータ構造Ｄを前処理プログラムで出力しておき，後処理プログラムに特許請求項１の手段２を所持させ，随時，後処理プログラムでは，Ｄを利用し，ｑに対する支持点探索を常に高速処理することができるようになる形態をとることが可能である．これにより，質問ベクトルｑを変更するたびに，手段２を実行するだけで高速の支持点探索処理を繰り返す事が出来る．【００１１】  特許請求項２では，凸多面体の支持点探索を必要とするプログラムに本発明を組み込む形態で実施される．なお，前処理プログラムに特許請求項２の手段１を実装し，Ｓ内の点集合を対象に質問点ｈ（ｑ）の近傍にある点を探索するに際して探索処理を高速化するためのデータ構造Ｍを前処理プログラムで出力しておき，後処理プログラムに特許請求項目２の手段２と手段３を実装し，後処理プログラムを実働する際，Ｍを利用し，ｑに対する近傍点探索の高速処理化に利用する形態をとることが可能である．これにより，質問ベクトルｑを変更するたびに，手段２と手段３を実行するだけで高速の支持点探索処理を繰り返す事が出来る．
【実施例】
【００１２】  特許請求項１にかかわる実施例における実施の形態として，前処理プログラムに特許請求項１の手段１を実装し，点位置決定問題解決処理を高速化するためのデータ構造Ｄを前処理で出力しておき，後処理プログラムに特許請求項１の手段２を所持させ，随時，後処理プログラムでは，Ｄを利用して高速にｈ（ｑ）を含む分割領域を探索し，該分割領域に対応するＱの頂点を得る場合を説明する．【００１３】  まず，手段１の実施例を説明する．３次元ベクトルａの偏角と天頂角をφとθとするとき，ａを２次元φθ直交座標系の点（φ，θ）に１対１に対応させる写像をｈとし，Ｑの面ｆｋ（ｋ＝１，２，，，，ｋｆＱ）の単位法線ベクトルをｎｆｉとするとき，矩形領域Ｓ＝｛（φ，θ）｜０≦φ≦２π，０≦θ≦π｝を曲線集合｛ｈ（（１−ｔ）・ｎｆｉ＋ｔ・ｎｆｊ）｜０≦ｔ≦１，１≦ｉ≦ｋｆＱ，１≦ｊ≦ｋｆＱ，ｉ≠ｊ，ｆｉとｆｊは互いに隣り合ったＱの面｝はＳを複数の分割領域に分割するグラフＧとなる．実際にｈ（ｑ）を含むＧの枝に囲まれた分割領域，すなわちＧの面を探索する後処理プログラムが高速に処理を終えることができるように，点位置決定問題解決高速化支援用データ構造Ｄを前処理プログラムで出力しておく方法を採る．なお，Ｓに関して，φ方向には２πを法とする．すなわち，Ｓの左端の垂直直線線分区間の点（０，θ）とそれに対応した右端の垂直直線線分区間の点（２π，θ）は同一点とみなす．また，Ｓの上端の水平直線線分区間（始点（０，π），終点（２π，π））の上の点はすべて同一点であり，また下端の水平直線線分区間（始点（０，０），終点（２π，０））の上の点はすべて同一点であるとみなす．Ｇの各枝は頂点以外では交差しない．始点（φｓ，θｓ）と終点（φｃ，θｅ）を結ぶＧの枝上の点の座標（φ，θ）のφとθの間には，０≦φ≦２πの範囲で下記の関係が成り立つ．ただし，（１）式はπを法とする．
θ＝ｔａｎ−１（ｔａｎθｃｔａｎθｓｓｉｎ（φｅ−φｓ）／（ｔａｎθｅｓｉｎ（φｃ−φ）＋ｔａｎθｓｓｉｎ（φ−φｓ）））
ｍｏｄπ・・・・・・・・・・・（１）
（１）式の関数は曲線ではあるが１価関数でもあり，Ｇの枝は頂点以外では互いに交差しない．また，Ｇの枝が垂直の直線になるような場合，あるいは法線ベクトルの点頂角θが０又はπになるような場合は，Ｑの図形を適当に回転してＱを再定義し直す．これによって，平面曲線グラフＧのどの面にｈ（ｑ）が属しているかを決定する問題に対しては，スラブ法を用いた点位置決定アルゴリズムが適用できる．本実施例ではスラブ法を利用した，Ｓａｒｎａｋ−Ｔａｒｊａｎの点位置決定アルゴリズム〔Ｎ．Ｓａｒｎａｋ  ａｎｄ  Ｒ．Ｅ．Ｔａｒｊａｎ，Ｐｌａｎａｒ  ｐｏｉｎｔｌｏｃａｔｉｏｎ  ｕｓｉｎｇ  ｐｅｒｓｉｓｔｅｎｔ  ｓｅａｒｃｈ  ｔｒｅｅｓ，Ｃｏｍｍ．ＡＣＭ．２９（１９８６），６６９−６７９〕を採用する．すなわち，Ｇに対して適用して得た該Ｓａｒｎａｋ−Ｔａｒｊａｎのアルゴリズムにおける点位置決定問題解決高速化支援用データ構造Ｄを前処理プログラムの出力とする．該アルゴリズムのＭを記憶するための必要メモリ量はＯ（ｋｖＰ）であり，ｈ（ｑ）が属しているＧの面を探索する手間はＯ（ｌｏｇｋｖＰ）である．【００１４】  次に，質問ベクトルをｑとするとき，ｈ（ｑ）を含むＧの枝が囲む面に対応するＱの頂点を探索して出力する手段２を含む支持点探索用後処理プログラムの実施例を説明する．前処理プログラムが予め作成しておいたＤを用いて，質問点ｈ（ｑ）に対し，Ｇの枝で囲まれた面を求める支持点探索用後処理プログラムも該Ｓａｒｎａｋ−Ｔａｒｊａｎのアルゴリズムに従う．この際，ｈ（ｑ）がスラブを横切る特定の枝（曲線）の下にあるかどうかを判定する処理は次のようにして実現することができる．あるひとつのスラブに着目する．該スラブを横切る（１）式で表されるＧの枝ｂと該スラブの左側垂直線との交点を（φｓ，θｓ）とし，スラブの右側垂直線との交点を（φｅ，θｅ）とし，ｈ（ｑ）の座標値を（φｑ，θｑ）とすると，（１）式にφ＝φｑを代入して得た値θがθｑより小さい場合，ｂよりも下にあり，等しい場合はｂ上にあり，その他の場合はｂよりも上にあると断定できる．【００１５】  特許請求項１の実施例により，前処理を施した後は任意の質問ベクトルｑに対して，メモリ必要量がＯ（ｋｖＰ）で手間がＯ（ｌｏｋｆＱ）でｑに応じたＱの支持点を求めることができる．また，特許請求項１の実施例により，Ｑを移動・回転してもＤを再作成する必要がないため，Ｑの形状自身に変化が起こらない限り常に支持点探索に高速に再利用できる．【００１６】  なお，以上に述べた本実施例の前処理プログラムにおいて，支持点のより一層の探索高速化を図るために，Ｄの他に，前処理プログラムで探索高速化支援データ構造Ｍ２も出力し，Ｍ２を探索に利用する実施例を説明する．【００１７】  手段１を実現する前処理プログラムでは，以上に述べたＤを出力する処理の他に，下記
2008282370.tif 000003
予め定めたｗ個以内のＧの面を覆う場合は，該メッシュにそれらの面に対応するｗ個以内のＱの頂点番号を記憶させ，メッシュがｗ個より多いＧの面を覆う場合は，ｎｕｌｌを記憶させたメッシュデータ構造をＭ２とする．【００１８】  手段２を実現する支持点探索用後処理プログラムでは，まず，Ｍ２を構成するどのメッシュがｈ（ｑ）が含むかを決定する．この処理はＳの縦横のメッシュ幅を知っていれば均等分割なので容易に特定できる．得られたメッシュが記憶するＱの頂点がｎｕｌｌであれば，特許請求項１の実施例においてすでに述べた手段２のＳａｒｎａｋ−Ｔａｒｊａｎの点位置決定アルゴリズムを用いた方法でＤを用いてＱの支持点を探索する．該メッシュがｗ個以内のＱの頂点番号を記憶している場合は，まず，ｑ方向に多面体Ｑから充分離れた距離に，ｑを法線ベクトルとして持つ平面Ｌを作成する．つぎに，該メッシュが記憶するすべての頂点のうち，平面Ｌに最も近い頂点を求める支持点として出力する．【００１９】  この実施例により，支持点探索処理の手間は，任意のｑに対して，ｈ（ｑ）を含むメッシュがｗ個以内の頂点の番号を記憶している場合はＯ（１）であり，ｈ（ｑ）が含むメッシュがｎｕｌｌを記憶している場合でもＯ（ｌｏｇｋｖＱ）となる．また，Ｑを移動・回転してもＭ２を再作成する必要がないため，Ｑの形状自身に変化が起こらない限り常に支持点探索に高速に再利用できる．【００２０】  特許請求項２にかかわる実施例における実施の形態として，前処理プログラムに特許請求項２の手段１を実装し，Ｓ内の点集合を対象に質問点の近傍にある点を探索するに際して探索処理を高速化するためのデータ構造Ｍを前処理で出力しておき，後処理プログラムに特許請求項目２の手段２と手段３を実装し，後処理プログラムを実働する際，Ｍを利用し，近傍点探索の高速処理化に利用する形態をとる２つの実施例Ａ，Ｂを説明する．【００２１】  まず，実施例Ａについて説明する．特許請求項２の手段１を含んだ前処理の実施例を説明する．３次元多面体Ｑの図形構成要素である面，辺，頂点の座標値と位相を管理する２重連結データ構造をＫとする．今，Ｑの面ｆｋ（ｋ＝１，２，，，，ｋｆＱ）の単位法線ベクトルをｎｆｋとし，Ｑの頂点ｖｉを共有する面をｆｉ，ｊとする（３≦ｊ≦ｍ（ｉ））．ｕ（ｉ）＝ｍ（ｉ）＋１とし，ｖｉを支持点とするｕ（ｉ）個の面Ｐｉ，ｊ（４≦ｊ≦ｕ（ｉ））の単位法線ベクトルｎＰｉ，ｊを定義する場合の手段１の実施例を説明する．まずｎＰｉ，ｌをｍ（ｉ）個のｎｆｉ，ｊ（ｊ＝１，２，，，，ｍ（ｉ））の平均ベクトルに等しいとする．次に，ｎＰｉ，ｌ＋ｊ＝（１−ｗ）・ｎＰｉ，ｌ＋ｗ・ｎｆｉ，ｊとする．ｗは１より小さい適当な正の実数とする．例えばｗ＝０．５とする．これにより，ｕ（ｉ）個の平面Ｐｉ，ｊを定義でき，これらの平面の支持点はすべてｖｉとなる．【００２２】  Ｍの作成方法の実施例を説明する．すべての点ｈ（ｎＰｉ，ｊ）の他に，ｈ（ｎＰｉ，ｊ）のφ座標値に２πを加えた点と−２πを加えた点を加えることによって数が３倍になった点群を母点とするボロノイ図Ｇ’をφθ直交座標系平面上に作成する．ボロノイ図の作成方法の実施例として，Ｓ．Ｆｏｒｔｕｎｅ，Ａ  ｓｗｅｅｐｌｉ��ｅ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｖｏｒｏｎｏｉ  ｄｉａｇｒａｍｓ，Ａｌｇｏｒｉｔｈｍｉｃａ  ２，１５３−１７４（１９８７）が挙げられる．Ｇ’に関するＳ内の部分グラフに対して，Ｓａｒｎａｋ−Ｔａｒｊａｎの点位置決定アルゴリズムを適用して得られた点位置決定問題解決高速化支援用データ構造をＭとする．【００２３】  以下に，手段２の実施例を述べる．質問ベクトルｈ（ｑ）が与えられた時，Ｍを用いて，ｈ（ｑ）を含むボロノイ領域を求めるアルゴリズムは該Ｓａｒｎａｋ−Ｔａｒｊａｎの点位置決定アルゴリズムに従う．これによって求めたボロノイ領域の母点がｈ（ｎＰｉ，ｊ）であるとき，ｖｉを手段２の出力とする．【００２４】  以下に，手段３の実施例を述べる．手段２の出力をｐとする．凸多面体Ｑからｑ方向に充分離れた距離に，ｑを法線ベクトルとして持つ平面Ｌを作成する．Ｑの２重連結データ構造Ｋを用いて，ｐに隣接するＱの頂点をすべて列挙し，それらの頂点からＬまでの距離の最も短い頂点ｕを決定し，ｕとＬまでの距離がｐとＬまでの距離よりも小さければｕを新しいｐとして再定義し，この作業を繰り返す．ｕとＬまでの距離がｐとＬまでの距離よりも大きいか等しくなった時点でｐが求める支持点であるとして手続きを終了する．【００２５】  以上の述べた特許請求項２にかかわる実施例Ａにより，Ｑを移動・回転してもＭを再作成する必要がないため，Ｑの形状自身に変化が起こらない限り常にＭを支持点探索に高速に再利用できる．【００２６】  なお，特許請求項２の実施例Ａの手段３の実施例において，ｕとＬまでの距離がｐとＬまでの距離よりも小さければｕを新しいｐとして再定義し，この作業を繰り返す過程において，ｕとＬまでの距離の計算の累積回数が予め定めた回数以上になったとき，この繰り返しを中止し，特許請求項１に述べた実施例を用いて，凸多面体Ｑの支持点を求める方法が可能である．【００２７】  この実施例により，ｕとＬまでの距離の計算の累積回数が予め定めた回数以下で支持点が求まった場合は，手間はＯ（１）であり，この作業を繰り返す回数が予め定めた回数以下で支持点が求まらない最悪の場合でもＯ（ｌｏｇｋｖＱ）となる．【００２８】  つぎに特許請求項２にかかわる実施例Ｂを説明する．実施例における実施の形態として，特許請求項目２の手段１は前処理プログラムとして実現し，Ｓ上の点集合｛ｈ（ｎＰｉ，ｊ）｝を対象に質問点ｈ（ｑ）の近傍にある点を探索する処理の高速化を支援するデータ構造Ｍを予め出力しておき，特許請求項目２の手段２と手段３を実装する後処理プログラムを実働する際，Ｍを利用し，ｈ（ｑ）の近くに存在する点を探索する処理の高速化に利用する形態をとる場合を説明する．【００２９】  ３次元多面体Ｑの図形構成要素である面，辺，頂点の座標値と位相を管理する２重連結データ構造をＫとする．今，Ｑの頂点ｖｉを共有する面をｆｉ，ｊとする（３≦ｊ≦ｍ（ｉ））．ｕ（ｉ）＝ｍ（ｉ）＋１とし，ｖｉを支持点とするｕ（ｉ）個の面Ｐｉ，ｊ（４≦ｊ≦ｕ（ｉ））の単位法線ベクトルｎＰｉ，ｊを定義する場合の手段１の実施例を説明する．まずｎＰｉ，ｌをｍ（ｉ）個のｎｆｉ，ｊ（ｊ＝１，２，，，，ｍ（ｉ））の平均ベクトルに等しいとする．次に，ｎＰ��，ｌ＋ｊ＝（１−ｗ）・ｎＰｉ，ｌ＋ｗ・ｎｆｉ，ｊとする．ｗは１より小さい適当な正の実数とする例えばｗ＝０．５とする．これにより，ｕ（ｉ）個の平面Ｐｉ，ｊを定義でき，これらの平面の支持点はすべてｖｉとなる．【００３０】  次にＭの作成方法を説明する．ＭをＳを根とする４分木とし，Ｓに含まれるｈ（ｎＰｉ，ｊ）をＭで管理することとする．まず，Ｓをφ軸に平行な直線とθ軸に平行な直線で４等分割する．これによってＭの根は４つの葉でもあるノードを持つ．次に各葉について，葉内のｈ（ｎＰｉ，ｊ）の数があらかじめ定めた一定値ｃ以下であれば，その葉はこれ以上分割せず，そうでなければ，再度φ軸に平行な直線とθ軸に平行な直線でその葉を４等分割する．この処理を予め定めた一定の階層深さまで繰り返す．次にＤの各葉には，それが含む複数のｈ（ｎＰｉ，ｊ）の中から適当に選んだ１点ｈ（ｎＰｉ，ｊ）を選び，ｈ（ｎＰｉ，ｊ）に対応するｖｉをその葉に記憶させる．葉が含む複数のｈ（ｎＰｉ，ｊ）の中から適当に選んだ１点ｈ（ｎＰｉ，ｊ）を選ぶ実施例として，該葉がカバーするＳ内のメッシュ領域である長方形の中心に一番近いｈ（ｎＰｉ，ｊ）を選ぶ方法が挙げられる．もしもｈ（ｎＰｉ，ｊ）を１つも含まない葉が存在するならば，該葉がカバーするメッシュ領域である長方形の適当に定めた一点（例えば長方形の中心点）の座標を（φ，θ）とすれば，φ，θを偏角と天頂角とするベクトルを法線ベクトルする平面に対するＱの支持点となる頂点ｖを特許請求項１の実施例で求め，ｖを該葉に記憶させる．【００３１】  以下に，特許請求項２の手段２の実施例を述べる．質問ベクトルｑが与えられた時，Ｍの根を起点にし，各ノード毎に，ｈ（ｑ）が４つの子のうちのどれに属するかを判定することを繰り返して，ｈ（ｑ）が属するＭの葉を決定する．該葉が記憶しているＱの頂点ｐを手段２の出力とす．【００３２】  以下に，手段３の実施例を述べる．手段２の出力をｐとする．凸多面体Ｑからｑ方向に充分離れた距離に，ｑを法線ベクトルとして持つ平面Ｌを作成する．Ｑの２重連結データ構造Ｋを用いて，ｐに隣接するＱの頂点をすべて列挙し，それらの頂点からＬまでの距離の最も短い頂点ｕを決定し，ｕとＬまでの距離がｐとＬまでの距離よりも小さければｕを新しいｐとして再定義し，この作業を繰り返す．ｕとＬまでの距離がｐとＬまでの距離よりも大きいか等しくなった時点でｐが求める支持点であるとして手続きを終了する．【００３３】  以上の述べた特許請求項２にかかわる実施例Ｂにより，Ｍとして簡明な前処理データ構造を採用しながらも，高速な支持点検索処理が可能となる．また，Ｑを移動・回転してもＭを再作成する必要がないため，Ｑの形状自身に変化が起こらない限り常にＭを支持点探索に高速に再利用できる．【００３４】  なお，特許請求項２の実施例Ｂの手段３の実施例において，ｕとＬまでの距離がｐとＬまでの距離よりも小さければｕを新しいｐとして再定義し，この作業を繰り返す過程において，ｕとＬまでの距離の計算の累積回数が予め定めた回数以上になったとき，この繰り返しを中止し，特許請求項１に述べた実施例を用いて，凸多面体Ｑの支持点を求める方法が可能である．【００３５】  この実施例により，ｕ���Ｌまでの距離の計算の累積回数が予め定めた回数以下で支持点が求まった場合は，手間はＯ（１）であり，この作業を繰り返す回数が予め定めた回数以下で支持点が求まらない最悪の場合でもＯ（ｌｏｇｋｖＱ）となる．【００３６】  特許請求項２にかかわる実施例Ａ，Ｂの手段１の実施例において，各頂点ｖｉに対し，ｖｉを支持点とする平面の数を一つに限定することができる．この場合，その平面をＰｉ，ｌとすればよい．これによって，必要メモリ量が少なくなる．【００３７】  特許請求項２にかかわる実施例Ｂの手段１の実施例において，４分木ではなく一般の多分木を採用することもできる．これによって，必要メモリ量が少なくなる．【００３８】  次に，特許請求項１，２の応用として，３次元ｎ制約線形計画法の高速解法を説明する．
（１）ｎ個の線形不等式を満足する３次元部分空間は面数がＯ（ｎ）の３次元凸多面体Ｑになる．まず，線形不等式を線形等式として見なし，線形等式間の交線計算を行い，Ｑの面，辺，頂点を求める．この処理の実施例は公知のアルゴリズム〔Ｆ．Ｐ．Ｐｒｅｐａｒａｔａ  ａｎｄ  Ｄ．Ｅ．Ｍｕｌｌｅｒ，Ｆｉｎｄｉｎｇ  ｔｈｅ  ｉｎｔｅｒｓｅｃｔｉｏｎ  ｏｆ  ｎ  ｈａｌｆ−ｓｐａｃｅｓ  ｉｎ  ｔｉｍｅ  Ｏ（ｎｌｏｇｎ），Ｔｈｅｏｒｅｔｉｃａｌ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ８（１），４５−５５（Ｊａｎ．１９７９）〕を適用する．
（２）３次元ｎ制約線形計画問題における１次目的関数の法線ベクトルをｑとする．
（３）ｑに対するＱの支持点を特許請求項の１または２の実施例を用いて求め，該支持点の座標を最適解とする．
したがって，３次元ｎ制約線形計画問題において，前処理としてＱを作成し，特許請求項の１または２の実施例を用いれば，その目的関数を如何に変更してもその都度高速に最適解を求めることができる．
【発明の効果】
【００３９】  特許請求項１により，前処理を施した後は，メモリ必要量はＯ（ｋｆＱ），手間はＯ（ｌｏｇｋｆＱ）で任意の質問ベクトルｑに応じたＱの支持点を求めることができる．
【００４０】  特許請求項２により，前処理を施した後は任意の質問ベクトルｑが与えられても，その都度高速にｑに応じた支持点を求めることができる．
【図面の簡単な説明】
【００４１】
【図１】  特許請求項１の実施例において，３次元凸多面体Ｑに対応して定められたφθ直交座標系のグラフＧとＱの辺と面と頂点の対応関係を示す図である．
【符号の説明】
【００４２】１．Ｑ：凸多面体
２．ｖｉ：Ｑの頂点
３．ｆｉ：Ｑの面
４．ｎｆｉ：Ｑの面ｆｉの単位法線ベクトル
５．（１−ｔ）ｎｆｉ＋ｔｎｆｊ：ｎｆｉとｎｆｊの間を結ぶ単位ベクトル関数，０≦ｔ≦１
６．ｈ（ａ）：（φａ，θａ），ただしａは偏角をφａ，天頂角θａとする３次元ベクトル
７．Ｓ：ｈの写像領域
【図１】
2008282370.tif 000004