四分木
概要
四分木は、2次元領域を再帰的に4つの領域へ分割して表す木構造である。画像や平面領域を効率よく管理するために使われる。
詳しい説明
四分木では、ある正方形領域を必要に応じて4つの小領域に分ける。さらに細かく表したい部分だけを再び4分割することで、均一な格子より少ないデータで領域を表せる場合がある。たとえば、変化の少ない部分は大きな領域のまま保持し、境界や細部がある部分だけを細かく分割できる。画像処理、地図、空間管理、2次元図形の表現などに利用される。
CG制作との関係
CG制作では、2次元領域や画像を階層的に管理する考え方として関係する。細部が必要な部分だけを細かくするため、データ量の削減や処理効率の改善につながる。
ゲーム開発との関係
ゲーム開発では、2D空間の衝突判定、地形管理、オブジェクト検索などに利用できる。すべてを総当たりで調べるより、空間を分割して管理する方が効率的になることがある。
制作・実装での例
2Dゲームで多数のオブジェクトを管理するとき、画面全体を区画に分けると、近いものだけを調べやすくなる。四分木はその考え方を階層的にしたものと考えられる。
検定対策ポイント
四分木は2次元空間を4分割する木構造である。3次元版は八分木であり、次元の違いと分割数の違いを押さえる。
関連用語
タグ
- CGエンジニア検定
- 第2章