四分木とは

空間的なデータ構造をあれこれする必要が出てきそうなので
四分木についてのお勉強メモ。

四分木とは
すべての内部ノードが4つの子ノードを持つように構成するツリーのこと。
ツリー中のどのノードも1つの正方形に対応している。

1つの正方形を4分割して、できた正方形を更に4分割
こんなことを再帰的に繰り返し行い、最終的には
領域に点が1つしか含まれなくなるまで分割を行う。
この最終的な領域（領域の単位）をリーフって言う・・でいいのかな？

大量のボールの衝突判定などを行う際、
全ての判定を1つ1つ行うのではなく、
四分木を利用して、隣接方向やリーフの深さなどを利用した隣接探査を行うことで
より効率的な衝突判定をできるとかできないとか。
求めたい隣接が内部ノードであるとき、すぐに見つかり
そうでなければその親ノードを調べ、と再帰的に求めたい隣接を求める。

参考書が数式だらけで意味不明だったので概要を言葉だけで書いてみました。
けどやっぱりちょっとよくわからない。
粒子法とかに適用できるのかな。

ちなみに、3Dバージョンは内部ノードが8つの八分木らしい。