- 568 名前：564 mailto:sage [2008/05/05(月) 21:33:30 ]
- >>566
bucket の番号を用いる例のためだけに、アルゴリズムの細かなことを書くのは
面倒だったから、本当に方針だけを書いたつもりなんだけどなあ。
まず、点を含む領域以外も見ないといけないのはそのとおりで、
ちゃんとやるには、点を含む領域から近い順に探索することになる。
（それまでに見つけた最も近い点までの距離を覚えておき、
見る必要のある領域を限定していく）
見る領域に対応する bucket の番号は、領域の座標値が分かっているのだから
領域座標 → ハッシュ を計算してやった後に ハッシュ → bucket 番号と取得する。
このとき、隣接領域で bucket 番号が隣接している必要はない。
詳しいことは、適当な計算幾何学の本を読んで欲しいところ。
こういうのはバケット法などの名前で知られている割と標準的な技法。
