データポイントのセットが与えられた場合、「最も近い」ものを見つけよう

Question

3Dポイントのリファレンスセット（Rと呼ぶ）と、他の多くの3Dポイントセット（その一連のデータセット点P、およびそのPiに含まれる各データセット）。

タスクは、いくつかのPiとR.でユークリッド距離私はそれがこのある参照方法でデータ点を最小限に抑えるpIを返すことである。

1. Piの各点について、各点と比較2点間の最小差を求める。
2. PiとRの最小の合計「差」に達するように、これらの最小距離を合計します。
3. 答えPiは、最小の差を持つものです。

しかし、Rのすべての点とPのすべての点との間の距離を本質的に見ているので、これはかなり狂っています。確かに私はそれよりもうまくいくことができます。

私は慣れていないMatlabで働いています。

より良いアルゴリズムは何ですか？これには完璧なデータ構造がありますか？ （K-Dツリーなど）

Answer 1

実際にパフォーマンス上の問題となるような狂気の点がない限り、特にこれらの操作がMatlabで高度にベクトル化できるため、あらゆる点を比較するのが最も簡単な解決策です。例えば

：

R = [1 2 3; 1 3 4]; 
P{1} = [2 3 5;1 1 2;2 1 3]; 
P{2} = [4 4 4]; 

nP = length(P); 
sumMinDist = zeros(nP,1); 

%# make R into n-by-1-by-3 already 
Rperm = permute(R,[1 3 2]); 

for iP = 1:nP 

%# since we want to sum up the minima, we need to take the square root 
allDist = sqrt(sum(bsxfun(@minus, Rperm, permute(P{iP},[3 1 2])).^2, 3)); 

%# sum the minima (you may want to consider 
%# taking the mean instead!) 
sumMinDist(iP) = sum(min(allDist,[],1)); 

end 

%# now we can identify the closest set 
[~,idxOfClosestSet] = min(sumMinDist);