Учитывая набор точек данных, найдите ближайшую

Итак, у нас есть эталонный набор трехмерных точек (назовем его R) и многие другие наборы трехмерных точек (назовем этот набор наборов точек данных P и каждый набор данных в этом Pi).

Задача состоит в том, чтобы вернуть число Пи, которое минимизирует евклидово расстояние между точками данных в некоторых Пи и Р. Я вижу это так:

  1. Для каждой точки в Pi сравните с каждой точкой в ​​R и найдите минимальную разницу между двумя точками.
  2. Суммируйте эти минимальные расстояния, чтобы получить минимальную общую «разницу» между Pi и R.
  3. Ответ Pi - это тот, у которого наименьшая разница.

Но это довольно безумие, поскольку это означает, по сути, смотреть на расстояние между каждой точкой в ​​R и каждой точкой в ​​P, которое может составлять тысячи или миллионы. Конечно, у меня получится лучше.

Я работаю в Matlab, к чему не привык.

Какой алгоритм лучше использовать? Есть ли структура данных, которая идеально подходит для этого? (например, дерево K-D?)


matlab euclidean-distance
person Jeremy    schedule 08.05.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Если у вас нет такого сумасшедшего количества точек, что это действительно становится проблемой производительности, сравнение каждой точки действительно является самым простым решением, особенно потому, что эти операции могут быть сильно векторизованы в 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);
person Jonas    schedule 08.05.2012