二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています

高速、低負荷で検索するにはどうしたらいいでしょうか?

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

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

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

回答の条件
  • 1人5回まで
  • 登録:2009/04/16 23:12:18
  • 終了:2009/04/19 13:59:40

回答(3件)

id:sibazyun No.1

sibazyun回答回数1752ベストアンサー獲得回数2362009/04/17 01:04:33

ポイント40pt

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万点なら、その範囲でユークリッド距離を

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

id:you_got

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

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 さんのおっしゃるように、正方形の領域を検索対象とするには

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

2009/04/17 10:24:31
id:Hyperion64 No.2

Hyperion64回答回数791ベストアンサー獲得回数842009/04/18 13:28:54

ポイント40pt

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

集合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とした場合に要件を満足するようと思いますが、どうなのでしょうか。

id:you_got

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

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

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

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

2009/04/19 13:59:17
id:mfkcesse No.3

mfkcesse回答回数16ベストアンサー獲得回数02009/04/18 23:42:15

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

  • id:GoldenDawn
    P に含まれる座標の範囲は決まっているのでしょうか。
    また、座標値は実数でしょうか整数でしょうか。
  • id:you_got
    範囲は固定です
    座標値は 実数になります ですので小数を含む形になります
  • id:practicalscheme
    代表的なのは、平面を再帰的に分割して木構造を作っておくものでしょう。
    「四分木」、「kd木」、「VP木」などで検索してみてください。
    調べるべき点を急速に絞り込むことができます。

    あるいは、速度が必要でメモリに余裕があり、分解能がやや低くて良い場合はボロノイ図をあらかじめ計算して画像か配列で持っておけば、分解能で丸めた座標値から一発で一番近い点が出るのでそことの距離を計算してマージンと比較するだけになります。
  • id:you_got
    practicalscheme
    木構造というもの、聞いたことはありましたが
    具体的な使用例は知りませんでした
    検索回数を減らすのにいいんですね!


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

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

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

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


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

この質問への反応(ブックマークコメント)

トラックバック

  • 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木を構築する
  • 計算幾何学に出会う ** 最近棒探索について調べた 今作っている 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
「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません