Octree

OR事典

八分木

読み方：はちぶんき
【英】：octree

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

「OR事典」の他の用語

計算幾何：

一般距離ボロノイ図  三角形分割  位相優先法  八分木  凸包  凸多面体  凸集合

ウィキペディア

八分木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/18 16:07 UTC 版)

左: 立方体の再帰的な8分割、右: それに対応した八分木

八分木（英: Octree）とは、木構造の一種で、各ノードに最大8個の子ノードがある。3次元空間を8つのオクタント（八分空間）に再帰的に分割する場合によく使われる。四分木を3次元に拡張したものと見ることができる。英語の名称は oct + tree に由来するが "octtree" とは書かず "octree" と書く。

空間表現としての八分木

八分木の各ノードは空間を8つのオクタントに分割する。PR (point region) 八分木の場合、各ノードは明確に1つの3次元の点を格納していて、それがそのノードに対応する空間領域の中心点となる。また、その点は子ノードそれぞれに対応する空間領域の頂点（隅）になり、逆に言えば、その点を中心としてオクタントに分ける。MX八分木では、対応する空間領域の幾何学的中心点を暗黙のうちに分割の中心とする。PR八分木の根ノードは無限の空間を表せるが、MX八分木の根ノードは有限の空間しか表せない（そうでないと幾何学的中心が求められない）。このように空間分割表現として八分木を使う場合、それはkd木の3次元の場合の特殊ケースとなる。

主な用途

• 空間インデックス
• 3次元での効率的な当たり判定
• 視野判定
• 高速多重極展開法
• 有限要素法

色量子化への応用

八分木による色量子化アルゴリズムは、1988年、Gervautz と Purgathofer が考案した。これは、画像の色データを最大9レベルの深さの八分木で符号化するものである。八分木がこの用途に使われるのは、$2^{3}=8$カテゴリ