0

所以我们有一个 3D 点的参考集(我们称之为 R),以及许多其他 3D 点集(我们称该组数据点集为 P,以及该 Pi 中的每个数据集)。

任务是返回使某些 Pi 和 R 中的数据点的欧几里得距离最小化的 Pi。我看到它的方式是这样的:

  1. 对于 Pi 中的每个点,与 R 中的每个点进行比较,并找到两点之间的最小差异。
  2. 将这些最小距离相加以达到 Pi 和 R 之间的最小总“差”。
  3. 答案 Pi 是差异最小的那个。

但这太疯狂了,因为这实际上意味着查看 R 中的每个点与 P 中的每个点之间的距离,可能是数千或数百万。当然,我可以做得更好。

我在 Matlab 工作,我不习惯。

有什么更好的算法可以使用?是否有适合此的数据结构?(例如KD树?)

4

1 回答 1

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);
于 2012-05-08T16:46:16.210 回答