nikq::cube

今回のアップデートは、
kNN探索ができるようになったよ。

kd木の作り方(点リスト):
  一番長い辺を探す
  重心とか平均とか半分とかで分割平面決定(axisaligned)
  ネガティブリスト作る
  ポジティブリスト作る
  return (kd木の作り方( ネガティブ ), 分割面, kd木の作り方( ポジティブ ))

みたいな感じ。
kNNは、深さ優先トラバーサルの時に、
範囲限定つきで幅優先探索も行う感じ。

kd_GetKNN( 木,点,半径 ):
  kd_kNN(木,点,半径,点 )

kd_kNN(木,点,半径,最近傍点):
  今の木を処理する
  
  // 近い方は無条件で。
  kd_kNN( 木:近い方 , 点, 半径, 最近傍点 )
  
  // 遠い方は半径で打ち切り
  最近傍点を分割面で更新
  if( 最近傍点までの距離が半径以上なら )
     kd_kNN( 木:遠い方, 点, 半径, 最近傍点 )

みたいになる。
動くまで時間かかったー