八分木

提供: ORWiki
2007年7月13日 (金) 00:33時点における122.17.2.240 (トーク)による版 (新しいページ: '【はちぶんき (octree)】 与えられた3次元空間の点の集合の分割を表現するデータ構造で, 2次元平面における四分木に対応する. 根に...')
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

【はちぶんき (octree)】

与えられた3次元空間の点の集合の分割を表現するデータ構造で, 2次元平面における四分木に対応する. 根に全体の3次元空間が対応し, 根の8個の子には$x$軸, $y$軸, $z$軸に垂直な平面でそれぞれ二等分して八等分された部分領域が対応する. さらにそれぞれの子$v$に対応する部分領域を同様に八等分して$v$の8つの子に対応させる. このようにして得られる分割を表現するデータ構造が八分木である.