質問: 多角形同士の衝突判定のアルゴリズムを検討しています。 愚直に衝突判定を行う場合、多角形の各直線が別の多角形と衝突していないか、全直線同士組み合わせでチェックしていくのかと思います。 ただし、この方法だと多角形の頂点数が多い場合や、多角形が多い場合に処理が非常に多くなってしまうと思われます。(多少は処理を間引きできるとは思いますが) 高速で衝突判定ができるようなアルゴリズムはあるでしょうか?
回答: 二次元の場合は円、三次元の場合は球で多角形を近似しておき、円または球に衝突判定があったなら厳密判定をすることで手を抜けるでしょう。要するに多角形の重心を円・球の中心、一番外側に飛び出した部分を半径として保持しておけば、「絶対にあたっていない場合」を直ちに判定できるはずです。