二次元多角形の衝突検出と押詰め : スペースモデルの応用
スポンサーリンク
概要
- 論文の詳細を見る
二次元運動図形の衝突検出は, 平面移動ロボットの道順決定, その他, 多くの分野で重要な課題となっている. 本論文は最初に衝突検出の効率的で安定な実現法について述べ, 次にプリント基板やLSIのレイアウト設計, 鉄板の板取り等で必要な図形押詰めへの応用について述べる. 大規模図形の最適な詰合せ設計は難しいため, 最初は隙間の広い配置をし, 後に人の指示で1個ずつ動かしたり, 押し役となる図形を動かして衝突検出をしながらブルドーザーのように押し詰めるためである. 衝突検出では近傍図形を効率的に検索するデータ構造が不可欠である. 本研究では二次元スペースモデルのデータ構造を採用するとともに, 運動多角形の衝突検出における計算誤差問題を検討し, 高速で安定な方式を実現した. また, この応用で凹凸任意角多角形, 任意方向の押詰めも可能にした. 本方式ではN個の多角形中で1個が運動する場合の衝突検出時間は特殊な場合を除き平均O(1), N個の多角形の押詰めは実用上O(N)となることが分かった.
- 一般社団法人情報処理学会の論文
- 1997-03-15
著者
関連論文
- 可視空間追跡法による高速3D表示 : 三次元スペースモデルの研究 (コンピュータグラフィクスの新展開)
- 二次元多角形の衝突検出と押詰め : スペースモデルの応用
- 三次元スペース・モデリングの考察 : 局所的図形論理, 衝突検出, 隠面消去の一貫高速処理
- プリント板回路の配置プログラムについて
- スペースZ-バッファ:安定で高速な隠線・隠面消去二次元スペースモデルの応用
- スペースモデルによる二次元図形処理システムの試作 : 注目,局所集合演算,運動図形の衝突検出
- 多重相貫図形が表現可能なスペースモデル用頂点テーブルの検討
- 二次元スペース・モデリングの考察 : ポインタ方式空間表現による局所的図形処理