人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

条件は次の通りです
1.集合Pはあらかじめ、任意の順番でソートしておける
2.点pの近似点にする条件は、margin範囲内で一番近いものとするが、margin値はそのときどきで変わる

ターゲットの言語はjavascriptで、200msぐらいの間隔で検索を続けるつもりです
集合P の個数が 1000 ~ 10000 点くらいだったらどうしますか?

みなさんのアイディアを貸してください

●質問者: you_got
●カテゴリ:コンピュータ
✍キーワード:JavaScript margin いもの アイディア アルゴリズム
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

1 ● sibazyun
●40ポイント

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

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


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

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

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

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


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

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

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

にはあります。


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

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


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

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

◎質問者からの返答

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

1.のアルゴリズムで悩んでいます

(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
●40ポイント

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

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

集合pのX座標を1000倍した集合Aをつくる。

集合pのY座標を1000倍した集合Bをつくる。

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

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

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

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

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

AAの要素とBBの要素の直積(3×3で9個)をとり、各1000で割るとそれは集合pのX、Y座標となる。

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

◎質問者からの返答

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

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

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

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


3 ● mfkcesse
●0ポイント

(はてなにより削除しました)

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ