「四分木」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (他の1人の利用者による、間の1版が非表示) | |||
| 2行目: | 2行目: | ||
2次元平面の領域分割を表現するデータ構造で, 与えられた点の集合や図形を効率的に処理するために用いられる. 根に全体領域が対応し, 根の4つの子には<math>x\,</math>座標の中央値および<math>y\,</math>座標の中央値を通る水平線および垂直線をひいて四分割された部分領域が対応する. さらにそれぞれの子<math>v\,</math>に対応する部分領域を同様に水平線および垂直線で四等分して<math>v\,</math>の4つの子に対応させる. このようにして得られる分割を表現するデータ構造が四分木である. | 2次元平面の領域分割を表現するデータ構造で, 与えられた点の集合や図形を効率的に処理するために用いられる. 根に全体領域が対応し, 根の4つの子には<math>x\,</math>座標の中央値および<math>y\,</math>座標の中央値を通る水平線および垂直線をひいて四分割された部分領域が対応する. さらにそれぞれの子<math>v\,</math>に対応する部分領域を同様に水平線および垂直線で四等分して<math>v\,</math>の4つの子に対応させる. このようにして得られる分割を表現するデータ構造が四分木である. | ||
| + | |||
| + | [[Category:計算幾何|しぶんぎ]] | ||
2008年11月9日 (日) 18:30時点における最新版
【しぶんぎ (quadtree)】
2次元平面の領域分割を表現するデータ構造で, 与えられた点の集合や図形を効率的に処理するために用いられる. 根に全体領域が対応し, 根の4つの子には座標の中央値および座標の中央値を通る水平線および垂直線をひいて四分割された部分領域が対応する. さらにそれぞれの子に対応する部分領域を同様に水平線および垂直線で四等分しての4つの子に対応させる. このようにして得られる分割を表現するデータ構造が四分木である.
