区間木が衝突判定に使えそうか知りたかった。

アクションにしろシューティングにしろ、衝突判定のコストを押さえることは重要である。

格子分割、四分木のような手法があるが、他に使えそうなものはないか。
と思い、 区間木を調べてみた。

wikiを良く読むと、計算量は、検索には1件あたりO(log n)かかるので、n個について行えば、O(n log n)である。
さらに、区間の判定時に重複を検知しなければならないようで、あまり判定に向いていないようだ。
そう感じて、今回は調べるのを中断した。