Boidsのように、たくさんのオブジェクトがお互いに力をおよぼすようなものを作るには、総当たりでお互いの距離を計算しなきゃならいため、高負荷。 そんなときQuadTreeを使う。
とりあえずダニエルシフマンの動画
https://thecodingtrain.com/CodingChallenges/098.1-quadtree.html
自分でコードをコピー
考え方１
- ２つのフェーズに分かれる
- ひとつは分割フェーズ＝四文木を作る
- ひとつは検索フェーズ＝検索条件に照らし合わせルートから下層へ順に検索していく
考え方２
- 総当たりで探すのではなく
- 点が存在するか（個数）を基準に４分木で面を分割していく。
- すると点が存在するrectangleとその点の情報がツリー構造でできあがる。
- 探したい点とそこからのある一定の距離、つまり円を考える。その円と重なる点を探したい。
- 円とツリー構造を上から比較していく
- ツリー各階層で持っているrectangleと円を比較し、重なってたらpoints配列に加えていく。
- 円とrectangleが重なっていて、下層も存在するなら深く潜っていく
- すると円のなかに含まれる点だけが得られるようになる
