|
''k''d木（）は、''k''次元のユークリッド空間にある点を分類する空間分割データ構造である。''k''d木は、多次元探索鍵を使った探索（例えば、範囲探索や最近傍探索）などの用途に使われるデータ構造である。''k''d木はBSP木の特殊ケースである。 ''k''d木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、''k''d木の根ノードから葉ノードまでの各ノードには1つの点が格納される〔Preparata, Franco P., Shamos, Michael Ian. ''Computational Geometry: An Introduction''. Springer-Verlag, 1985: ISBN 3-540-96131-3〕。この点もBSP木とは異なり、BSP木では葉ノードのみが点（または他の幾何学的プリミティブ）を含む。つまり、''k''d木の各分割平面は必ず1つの点を通る。葉ノードのみがデータを格納する派生データ構造を''k''dトライと呼ぶ。また、特記すべき''k''d木の別の定義として、各分割平面が1つの点を通るよう決定されるものの、点を葉ノードでのみ記憶するという定義もある〔de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. ''Computational Geometry: Algorithms and Applications''. Springer-Verlag, 1997: ISBN 3-540-65620-0〕。 ''k''d木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、''k''d木の根ノードから葉ノードまでの各ノードには1つの点が格納される〔Preparata, Franco P., Shamos, Michael Ian. ''Computational Geometry: An Introduction''. Springer-Verlag, 1985: ISBN 3-540-96131-3〕。この点もBSP木とは異なり、BSP木では葉ノードのみが点（または他の幾何学的プリミティブ）を含む。つまり、''k''d木の各分割平面は必ず1つの点を通る。葉ノードのみがデータを格納する派生データ構造を''k''dトライと呼ぶ。また、特記すべき''k''d木の別の定義として、各分割平面が1つの点を通るよう決定されるものの、点を葉ノードでのみ記憶するという定義もある〔de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. ''Computational Geometry: Algorithms and Applications''. Springer-Verlag, 1997: ISBN 3-540-65620-0〕。 'k''d木（）は、''k''次元のユークリッド空間にある点を分類する空間分割データ構造である。''k''d木は、多次元探索鍵を使った探索（例えば、範囲探索や最近傍探索）などの用途に使われるデータ構造である。''k''d木はBSP木の特殊ケースである。 ''k''d木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、''k''d木の根ノードから葉ノードまでの各ノードには1つの点が格納される〔Preparata, Franco P., Shamos, Michael Ian. ''Computational Geometry: An Introduction''. Springer-Verlag, 1985: ISBN 3-540-96131-3〕。この点もBSP木とは異なり、BSP木では葉ノードのみが点（または他の幾何学的プリミティブ）を含む。つまり、''k''d木の各分割平面は必ず1つの点を通る。葉ノードのみがデータを格納する派生データ構造を''k''dトライと呼ぶ。また、特記すべき''k''d木の別の定義として、各分割平面が1つの点を通るよう決定されるものの、点を葉ノードでのみ記憶するという定義もある〔de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. ''Computational Geometry: Algorithms and Applications''. Springer-Verlag, 1997: ISBN 3-540-65620-0〕。 == ''k''d木上の操作 == === ''k''d木の構築 === 軸に対応した分割平面の選択方法は様々なものがあり、''k''d木の構築方法も様々である。典型的な''k''d木の構築方法は以下のようになる。 * 木構造を下降すると共に、分割平面を選択する軸を巡回するようにする。例えば、根において''x''軸に垂直な平面とし、根の子では''y''軸に垂直な平面とし、根の孫では''z''軸に垂直な平面とする、というように軸を巡回するように選択していく。 * 各ステップで、分割平面生成で選択される点は、''k''d木に入れる全ての点の対応する軸の座標値の中央値となる点とする。なお、前提として全ての点の集合がアルゴリズムの先頭で得られるものとする。 この方法では平衡''k''d木が得られ、各葉ノードと根との距離は等しくなる。しかし平衡木があらゆる応用において最適とは限らない。 また、常に中央値となる点を選択することが求められているわけではない。中央値を気にしない場合、単に平衡木となることが保証されないだけである。中央値を選択するアルゴリズムやソートをしない場合のヒューリスティックとしては、固定個の点を無作為に選択し、それらの中の中央値を選んで分割するという方式がある。実用上はこの技法で十分平衡的な木が得られる。 ''n''個の点のリストを与えられたとき、以下のアルゴリズムで平衡''k''d木を構築できる。 function kdtree (''list of points'' pointList, ''int'' depth) 中央値より後ろ（after）の点には、中央値以上の座標値の点を含ませるのが一般的である。別の手法として、他の次元で点を比較する「スーパーキー(superkey)」関数を定義する方法もある。他にも、中央値に等しい点を両側に属させることもありうる。 このアルゴリズムをPythonで実装すると次のようになる。 class Node:pass def kdtree(pointList, depth=0): if not pointList: return # 深さに応じて軸を選択し、軸が順次選択されるようにする k = len(pointList) # 全ての点が同じ次元を持つと仮定 axis = depth % k # 点のリストをソートし、中央値の点を選択する pointList.sort(key=lambda x:x) median = len(pointList)/2 # 中央値を選択 # ノードを作成し、部分木を構築する node = Node() node.location = pointList node.leftChild = kdtree(pointList, depth+1) node.rightChild = kdtree(pointList, depth+1) return node このアルゴリズムは任意のノードについて不変条件を生成し、左の部分木にある全ノードは分割平面の一方の側にあり、右の部分木にある全ノードは同じ分割平面のもう一方の側にある。分割平面上にある点はどちらの側にも出現する可能性がある。あるノードの分割平面はそのノードに対応した点を通る（上記コードでは ''node.location'' で表されている）。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kd木」の詳細全文を読む スポンサード リンク
|