logo

nikq::cube

2006年11月9日(木) 23:59

kd木

できたできた。kd木ができた。

http://nikq.nothing.sh/junkbox/kd3d.cpp

ランダム充填の10000ポイントに対して14クエリくらいだからまぁOK。
理想は平均してlog2(10000)=13.28クエリくらいになれば良いはずなので。

線形探索と違うポイントが出てくるのはOKだよね?
exactry hitとは限らないよね?
たまに線形探索よりもノルムの小さいポイント発見するのは何でだろう?
線形探索が狂ってるのか?

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

Comments

『Re:』

>たまに線形探索よりもノルムの小さいポイント発見するのは何でだろう?
距離計算がマンハッタンだからかも.
ふつうにやるようにしたらでなくなった(気がする.)

written by omo

『マンハッタン』

あ、本当だ…>マンハッタン距離
数時間前の俺はずいぶんな手抜きをしていたようです。
ありがとうございました。

written by nikq

『make_node前のソートについて』

こちらでは初めまして。
頂点配列を原点からの距離でソートしているのは何故でしょうか?
bounding boxの更新を抑えるためなら昇順ではなく降順ですし、
どちらにしても2段目以降のmake_nodeではソートが逆効果になってしまうような。
実際にソートしない、昇順、降順の3種類でbbox境界更新回数をカウントしてみたところ、ソートしないのが一番更新回数が少なかったです。
全然違う意図があったらすいません…

written by mts

『ソートの理由は』

ソートの理由は、本当に個数を2分するような(i++,j+=2とかで)
中間点を探すためだったのですが、
結局平均値で分割しちゃってるので、
全く意味はありません。
なんとなくそのままソート部分だけ残してしまいました。

多分なくても動きます。

written by nikq

TrackBacks

nikq::cube

MySketch 2.7.2 written by 夕雨