10/01/06 04:31:17
>>500
どうもです、ちなみに最初はそれに近い実装をしていました。
ただし、一次元で考えて、グリッドが{0, 1, 2}のように整数上にあり、
球の直径１として、球の中心がそれぞれ0.9と、2.1にあるときに失敗します
ので、もう少し拡大する必要がありそうです。が、125セルに対して衝突判定
したり、グリッドサイズを直径の２倍とかにすると重そう。
そこで、まず各球の中心からの近傍セルに球へのポインタを登録しておき
（上の例なら中心・上下左右・斜めと27つのセルに登録）、同じセル内に
登録された球同士で衝突判定していました。一応O(n)アルゴリズムのはず。
ただ、実装の問題もありますが、１千万点のデータで、メモリ１Ｇ近くに
なったので。メモリ的にきつかったり、グリッドサイズを決めるのが難しい
かなと。