二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています高速、低負荷で検索するにはどうしたらいいでしょうか？条件は次の通りです ..

you_got あなたも質問に答えられます！ウォッチリストに追加
状態：終了
回答数：3 / 10件
回答ポイント：80ポイント
登録：2009-04-16 23:12:18
終了：2009-04-19 13:59:40
カテゴリー：コンピュータ

1 回答者：sibazyun 2009-04-17 01:04:33 満足！ 40ポイント

０：確認すると、距離はユークリッド距離、つまりSQRT（x*x+y*y)であり、

　margin*2 を直径とする円内にあって一番近い、ですね。

１：ソートを第1順位x、第2順位yでしておけば、まずx,yの値を見て、

　範囲を点pから、±margin, すなわち、margin*2を一編とする

　正方形内の点に限られます。これが最初のデータ量削減。

　この範囲にPの点がなければ、近似点はない。あれば２へ。

２：次に、±(margin/2)の範囲の点の存在を確認します。

　あればその中に限定。なければ、±(margin*3/4)の

　範囲に広げてみる。なければ、±(margin*3/4)～±margin

　にはあります。

３．２で点があれば、±(margin/4)で見て、なければ

　±(margin/4)～±(margin/2)にあります。

４．点数が高々1万点なら、その範囲でユークリッド距離を

　順に求めていってもよいと思います。

質問者：

you_got 2009-04-17 10:24:31

確認事項はそのとおりです

１．のアルゴリズムで悩んでいます

(1,1), (1,2), .... (1, 100)

(2,1), (2,2), .... (2, 100)

(3,1), (3,2), .... (3, 100)

(4,1), (4,2), .... (4, 100)

(5,1), (5,2), .... (5, 100)

このうち、(3,50) に関して margin = 1 で調べるとすると

　(2, 49), (2, 50), (2, 51)

　(3, 49), (3, 50), (3, 51)

　(4, 49), (4, 50), (4, 51)

を範囲にしたいわけです

しかし、この正方形だけを範囲にするにはどうやったらいいのでしょう？

> ソートを第1順位x、第2順位yでしておけば

となると

(1,1), (1,2), (1,3) ... (1,100), (2,1), (2,2),.....(5,100)

という順列になります

(2,49) から (4,51) の範囲を指定すると

(2,49) ... (2,100), (3,1), (3,2), .... (3,100), (4,1), (4,2), ... (4,51)

が検索範囲になります

(2,52) .. (3,48), (3,52) .. (4,48) が無駄な検索範囲となってしまいます

sibazyun さんのおっしゃるように、正方形の領域を検索対象とするには

どのようなデータの持ち方をしたらよいでしょう。。

2 回答者：Hyperion64 2009-04-18 13:28:54 満足！ 40ポイント

こういうのはどうでしょう。

集合ｐの座標値の小数点（任意の点pの座標も含めて）が例えば最大下三桁だとする。

集合ｐのX座標を１０００倍した集合Aをつくる。

集合ｐのY座標を１０００倍した集合Bをつくる。

AもBも整数で昇順ソート済みとする。

任意の点p（x,y）を各1000倍したものを（X,Y）とする。

Marginをm、1000倍したのをMとする。

集合Aから、X-M<=A<=X+Mとなる要素を抜き出す。AAとする（例えば３個とする）

同様に集合Bから、Y-M<=B<=Y+Mとなる要素を抜き出す。BBとする（例えば３個とする）

AAの要素とBBの要素の直積（３×３で９個）をとり、各1000で割るとそれは集合ｐのX、Y座標となる。

これは任意の点pと集合ｐの要素の距離ではなく、X座標のMarginとY座標のMarginが独立にmとした場合に要件を満足するようと思いますが、どうなのでしょうか。

質問者：

you_got 2009-04-19 13:59:17

直積というと、ベクトルの計算にでてくるやつでしょうか。

なんとなくイメージがつかめたような気がしますが、

具体的にどうプログラムしようか考えるとわかりません＞＜

でも、ありがとうございました

3 回答者：mfkcesse 2009-04-18 23:42:15 0ポイント

（はてなにより削除しました）

おとなり質問

この質問・回答へのコメント

GoldenDawn 2009-04-17 12:57:38

P に含まれる座標の範囲は決まっているのでしょうか。
また、座標値は実数でしょうか整数でしょうか。

you_got 2009-04-17 13:54:36

範囲は固定です
座標値は実数になります　ですので小数を含む形になります

practicalscheme 2009-04-17 19:32:50

代表的なのは、平面を再帰的に分割して木構造を作っておくものでしょう。
「四分木」、「kd木」、「VP木」などで検索してみてください。
調べるべき点を急速に絞り込むことができます。

あるいは、速度が必要でメモリに余裕があり、分解能がやや低くて良い場合はボロノイ図をあらかじめ計算して画像か配列で持っておけば、分解能で丸めた座標値から一発で一番近い点が出るのでそことの距離を計算してマージンと比較するだけになります。

you_got 2009-04-19 14:08:47

practicalscheme
木構造というもの、聞いたことはありましたが
具体的な使用例は知りませんでした
検索回数を減らすのにいいんですね！

四分木が一番手軽に使えそうですね
検索しやすく、無駄が少ないので非常にいいと思いました
これなら、検索もソートも効率的にできそうです

kd木だと、空間になるんでしょうか？
見つけた例がわるかったのかもしれませんが、
二次元にはどう応用できるのかいまいち理解できませんでした

VP木は、こちらの最近傍探索のことでしょうか
http://ja.wikipedia.org/wiki/%E6%9C%80%E8%BF%91%E5%82%8D%E6%8E%A2%E7%B4%A2
命題がぴったりそのものでびっくりしました
ちょっと時間がなくてまだ読み切れてないんですが
うまく使えそうです

ボロノイ図はなかなかおもしろいテーマですね
分解能のことを考えると今回目的としているものでは使えなさそうですが
少し掘り下げてみたいと思います

ありがとうございました！

この質問・回答へのトラックバック

agwの日記 - kd-tree Visualization(1) 2009-04-27 16:50:46

kd-tree Visualization(1) 前回のエントリに引き続き、連続したビット群の総数を求めるアルゴリズムを考える予定でしたが、今回は空間分割データ構造に関するエントリにしました。人力検索は

algorithm - 最近点検索 404 Blog Not Found 2009-04-28 23:50:03

食後のデザートにちょうどよいサイズの問題。二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています高速、低負荷で検索するにはどうしたらいいで

[Algorithm] kd-tree Visualization(2) agwの日記 2009-04-29 02:53:14

先日のエントリにて、kd木を紹介しました。前回はアルゴリズム Cに倣って、要素の追加のみでkd木を構築してみました。繰り返しになりますが、一般的に要素の追加のみでkd木を構築する

人力検索はてな先日、質問した内容の続きです「点の集合.. 2009-04-29 11:58:42

道化がつぶやく - 計算幾何学に出会う 2009-04-29 13:11:54

計算幾何学に出会う ** 最近棒探索について調べた今作っている Ajax システムの中に 1000個オーダーの頂点を、マウスで選択できる仕組みを入れたくて複数の点の中からマウスに一番近い点

[Algorithm] kd-tree Visualization(3) agwの日記 2009-04-29 17:28:03

さて、先日のエントリにて、メディアンを加味した2d木の構築を紹介しました。コードの見通しを簡潔にする目的もあり、メディアンの選択にはsort()を用いました。 #!/usr/bin/python -t from operat

2009-07-12 13:33:31