八分木

【はちぶんき (octree)】

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