C++0x 3 - 暇つぶし2ch

C++0x 3 at TECH

568:564
08/05/05 21:33:30
>>566
bucket の番号を用いる例のためだけに、アルゴリズムの細かなことを書くのは
面倒だったから、本当に方針だけを書いたつもりなんだけどなあ。

まず、点を含む領域以外も見ないといけないのはそのとおりで、
ちゃんとやるには、点を含む領域から近い順に探索することになる。
（それまでに見つけた最も近い点までの距離を覚えておき、
　見る必要のある領域を限定していく）

見る領域に対応する bucket の番号は、領域の座標値が分かっているのだから
領域座標 → ハッシュを計算してやった後にハッシュ → bucket 番号と取得する。
このとき、隣接領域で bucket 番号が隣接している必要はない。

詳しいことは、適当な計算幾何学の本を読んで欲しいところ。
こういうのはバケット法などの名前で知られている割と標準的な技法。

次ページ

続きを表示

1を表示