logo

nikq::cube

2006年11月11日(土) 23:15

kd木(2)

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

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

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

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

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

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

written by nikq [/program] [この記事のURL] [コメントを書く] [コメント(2)]

Comments

『タイトルなし』

フォトンマップで既にkd-tree実装してませんでしたっけ?

written by bee

『kd木は』

KD-tree実装しようと思ったところで
飽きてしまったのです。

昨日授業中にふと思いついて作り始めたら
うまく動いたので楽しくなって3時間で書きました。

written by nikq

TrackBacks

nikq::cube

MySketch 2.7.2 written by 夕雨