計算幾何学に出会う
最近棒探索について調べた
今作っている Ajax システムの中に
1000個オーダーの頂点を、マウスで選択できる仕組みを入れたくて
複数の点の中からマウスに一番近い点を探すアルゴリズムを調べていた
なかなかうまい方法が見つからない。。。
でも、点の集合から最近点を見つけるなんて、よくありそうだしなぁ。。
絶対に何かジャンルがあるはずに違いない。。。
そう思い、はてなの人力検索
http://q.hatena.ne.jp/1239891135
本当に、たくさんの回答・アドバイスをいただきました!!
ブクマコメより
paella 勉強, アルゴリズム 良い質問に良い回答(コメント欄も)。あとはこれが学校の宿題でないことを祈るのみ。 2009/04/19
学生ではないので、ご安心くださいw
dan kogai さんにも取り上げていただいた!
http://blog.livedoor.jp/dankogai/archives/51206550.html
あの有名な方に目をとめていただき、感謝感激
- 点集合は、あらかじめ原点からの距離順にソートしておく。
- その集合を、検索したい点の原点からの距離を使って二分探索(binary search)する。
一つ目の回答は、このようなものだった
おそらく 二次元→一次元にすれば、検索簡単ウマーってことだと思われるけど
残念ながら 直交座標系(x, y) を 極座標系(r, θ)に変換しているだけ
θの情報が抜けているので
ぬじゃらだーさんのコメント
このアルゴリズムって点が原点から等距離に分布している場合はまったく働かないですよね。
残念。
そうやって考えていくと、「とりあえず全ての点までの距離を測る」という素朴なアルゴリズムは、案外バランスが取れているかも知れない。
最近点だけでよければ O(n) でもあるし。
うーん もう一声
計算幾何学
皆様からアドバイスいただいたキーワードは次のもの
- 四分木
- kd木
- VP木
- R-Tree
- SS-Tree
- SR-Tree
- M-Tree
- LSH(Locality-Sensitive Hashing)
kd木については、agwさんが、丁寧かつわかりやすい記事を書いてくださりました
http://d.hatena.ne.jp/agw/20090427/1240905276
これらは 計算幾何学 というジャンルのものだそうだ
自分なりに調べて理解した内容をまとめると。。
- 四分木
再帰的に、領域を4分割する
領域の中の点の数が設定された数より小さくなるまで繰り返す
-
- 利点
木の構築が簡便
動的に要素を増やすのも容易
-
- 難点
木のバランスが悪くなる
したがって、検索が遅い
- kd木
一回目の分割は x軸
二回目の分割は y軸
三回目の分割は x軸
・
と交互に繰り返す
また、領域内の座標郡を等分するように分割する
-
- 利点
木のバランスが非常に良い
検索が早い O(log n)
-
- 難点
木の構築に時間がかかる
動的な要素追加に弱い
とりあえず kd木を javascript で実装してみたところ
1000 個のポイントなら、1ms で検索できた
これはウマイ!
計算幾何学っておもしろいなー
自分でも本を買って読み始めました
- 作者: Elmar Langetepe,Gabriel Zachmann,中本浩
- 出版社/メーカー: ボーンデジタル
- 発売日: 2007/04/01
- メディア: 単行本
- 購入: 1人 クリック: 61回
- この商品を含むブログ (8件) を見る
難しくて、進捗は遅々としたものですが。。。
次の展望
今まで集合は点の集合でしたが
この集合に、点・線・閉面を加えた場合はどんなアルゴリズムがあるでしょうか?
R木がそれっぽいですが、若輩の私にはまだ理解できない><
しょうこりもなく皆様のお力に頼ります
http://q.hatena.ne.jp/1240973914
どうぞなにとぞよろしくお願いいたします