計算幾何学に出会う - 道化がつぶやく

今作っている Ajax システムの中に
1000個オーダーの頂点を、マウスで選択できる仕組みを入れたくて
複数の点の中からマウスに一番近い点を探すアルゴリズムを調べていた

なかなかうまい方法が見つからない。。。
でも、点の集合から最近点を見つけるなんて、よくありそうだしなぁ。。
絶対に何かジャンルがあるはずに違いない。。。

本当に、たくさんの回答・アドバイスをいただきました！！

ブクマコメより

paella 勉強, アルゴリズム良い質問に良い回答（コメント欄も）。あとはこれが学校の宿題でないことを祈るのみ。 2009/04/19

学生ではないので、ご安心くださいｗ

あの有名な方に目をとめていただき、感謝感激

点集合は、あらかじめ原点からの距離順にソートしておく。

その集合を、検索したい点の原点からの距離を使って二分探索(binary search)する。

一つ目の回答は、このようなものだった
おそらく二次元→一次元にすれば、検索簡単ｳﾏｰってことだと思われるけど
残念ながら直交座標系（x, y）を極座標系（r, θ）に変換しているだけ
θの情報が抜けているので

ぬじゃらだーさんのコメント
このアルゴリズムって点が原点から等距離に分布している場合はまったく働かないですよね。

残念。

そうやって考えていくと、「とりあえず全ての点までの距離を測る」という素朴なアルゴリズムは、案外バランスが取れているかも知れない。
最近点だけでよければ O(n) でもあるし。

うーん　もう一声

皆様からアドバイスいただいたキーワードは次のもの

kd木については、agwさんが、丁寧かつわかりやすい記事を書いてくださりました
http://d.hatena.ne.jp/agw/20090427/1240905276

これらは計算幾何学というジャンルのものだそうだ

自分なりに調べて理解した内容をまとめると。。

再帰的に、領域を４分割する
領域の中の点の数が設定された数より小さくなるまで繰り返す

木の構築が簡便
動的に要素を増やすのも容易

木のバランスが悪くなる
したがって、検索が遅い

一回目の分割は x軸
二回目の分割は y軸
三回目の分割は x軸
・
と交互に繰り返す
また、領域内の座標郡を等分するように分割する

木のバランスが非常に良い
検索が早い O(log n)

木の構築に時間がかかる
動的な要素追加に弱い

とりあえず kd木を javascript で実装してみたところ
1000 個のポイントなら、1ms で検索できた
これはｳﾏｲ！

計算幾何学っておもしろいなー
自分でも本を買って読み始めました

難しくて、進捗は遅々としたものですが。。。

今まで集合は点の集合でしたが
この集合に、点・線・閉面を加えた場合はどんなアルゴリズムがあるでしょうか？

R木がそれっぽいですが、若輩の私にはまだ理解できない＞＜

しょうこりもなく皆様のお力に頼ります
http://q.hatena.ne.jp/1240973914

どうぞなにとぞよろしくお願いいたします