데이터 포인트 세트가 주어지면 "가장 가까운"것을 찾으십시오

Question

그래서 3D 포인트의 참조 세트 (R이라고 부름)와 다른 많은 3D 포인트 세트 (그 세트의 데이터 세트 점 P 및 그 Pi에있는 각 데이터 세트). 파이의 각 포인트에 대한

1. , 각 지점의 비교 : 작업이 일부 파이와 R.에서 유클리드 거리를 나는 그것을 볼 수있는 방법을 데이터 포인트를 최소화 파이를 반환하는 것입니다

   이있다 R과 두 점 사이의 최소 차이를 찾아라.

2. Pi와 R 사이의 최소 총 "차이"에 도달하도록이 최소 거리를 합산하십시오.
3. Pi는 가장 작은 차이가있는 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);