1

多次元空間に大量の点があります。そして、特定のポイントに対して（近隣内の）少数の近隣を見つけたいと思います（すべてのポイントのスキャンを避ける必要があります）。

私の解決策が適切かどうか知りたい：

前処理:

  1. 一連の直交軸を定義する
  2. 各軸上の各点の射影を作成します
  3. 各射影は、軸の始点 (キー) と点の識別子 (値) からの距離に関連付けられています。インデックス プロジェクション- それらすべてをソートされたセット (ツリー セットなど) に入れます。
dist = distance of projection to the start point of axis
point_num = number of point 
sorted_set.put( dist, point_num )

任意の点の近傍を見つけるには:

  1. 各軸での投影を見つけます
  2. Idex の使用 - 各存在で最も近い射影を見つける
  3. 実際の隣人を見つける -すべての結果の交差
dx = radius of neighborhood (some constant) 

dist_1 = distance of projection of given point to start point of axis_1 
list_1 = sorted_set_1.get_sub_set( dist_1 - dx, dist_1 + dx )

dist_2 = distance of projection of given point to start point of axis_2
list_2 = sorted_set_2.get_sub_set( dist_2 - dx, dist_2 + dx ) 

return intersection_of( list_1, list_2 )

簡単な例を次に示します。

ここに画像の説明を入力

交差[2, 4, 1]し[4, 5]て答えを生み出す[4]

アルゴリズムで間違いを犯した場合は、指摘してください

ありがとう

4

1 に答える 1

1

実際の隣人セット (この場合は[2, 4, 1]と[4, 5]. あるインデックスから 3 つの要素を選択し、別のインデックスから 2 つの要素を選択したのはなぜですか?

また、いくつかの隣人を見つけたいと述べています。いくつかは少数ですか、それとも関数への入力にする必要がありますか? この例では 1 つしか見つかりませんでしたが、必要な数をアルゴリズムが決定する必要がありますか?

すべての点が軸の 1 つの線上にある場合はどうなりますか? すると、1 つの集合に必ずすべての要素が含まれます。

于 2013-02-15T14:50:53.530 に答える