情報処理学会 第76回全国大会講演要旨

2次元平面における物体の衝突判定用のk-d-tree検索のための空間分割アルゴリズムを提案する．通常のk-d-tree検索では，物体が空間をまたいでいる部分で衝突が起きた場合は関係する空間全てにおいて処理を施さなければならない．今回提案する手法では，そのような場合でも適切な空間をひとつに絞り込むアルゴリズムと，そのための空間分割の手法と提案する．今回のアルゴリズムにより，線分で形成された複雑な境界線をもつ空間を自動的に分割して，衝突判定処理の高速化を達成する．