检查坐标是否在另一个矩阵中任何点的给定距离内

Question

在 Matlab 中，我有两个包含坐标的相当大的矩阵（A 和 B）。两条线代表x和y，每列代表一个笛卡尔坐标(x;y)。

现在我想将矩阵 B 中距离矩阵 A 中任何点小于 1（米）的所有点存储在新矩阵中。

我可以遍历所有的数据，但是非常耗时（矩阵是2x800000）。

有什么方法可以提高性能吗？

这是我当前代码的结构：

new_vec = [0;0];
for i=1:length(A)
    cur_x = A(1, i);
    cur_y = A(2, i);

    for j=1:length(B)
        if B(2, j) <= cur_y + 1 && B(2, j) >= cur_y - 1 && ...
               B(1, j) <= cur_x + 1 && B(1, j) >= cur_x - 1
            new_vec = [new_vec, [B(1, j); B(2, j)]];
        end
    end
end

Answer 1

性能改进基于您当前的实施：

% Appending is bad practise for memory management, you should initialise the 
% entire output array at first.
new_vec = NaN(size(B));
% You should not use i as a loop variable, since you are overwriting the default i=sqrt(-1)
% Also length(A)=max(size(A)), clearer to use size(A,2)

% Loops have been swapped as we want to exit the *A* looping when satisfied
for jj=1:size(B,2)
    % No need to re-assign current variables each loop, waste of time/memory

    % Same as before, j also is sqrt(-1) by default!
    % We could remove this loop entirely using vectorization, but it's likely quicker to
    % loop *until the condition is satisfied* then exit the loop early, avoiding many ops.
    for ii=1:size(A,2)
        % We can *half* the number of logical operations by using the abs distance!
        if abs(B(2,jj)-A(2,ii)) <= 1 && abs(B(1,jj) - A(1,ii)) <= 1
            % We pre-allocated, so no need to append - use direct indexing
            new_vec(:,jj) = B(:,jj);
            % Now the condition is satisfied for B(:,jj), exit the jj loop!
            break;
        end
    end
end
% We initialised an array of NaNs, remove the columns which are still NaN
new_vec(:, isnan(new_vec(1,:))) = [];

亮点：

最佳实践：不要使用 i 或 j 作为循环变量，它们的默认值为 sqrt(-1)
Pre-allocate memory, don't append results during looping。
减少逻辑检查的次数，使用abs做绝对距离检查。
不要在不必要时为每个循环分配临时变量。
因为当给定的 B 坐标在 any A 坐标的距离内时你很高兴，所以 提前退出循环 以避免进一步检查。

初始化一个 NaN 的二维数组的替代方法（可能对内存更友好）是初始化一个布尔 false 数组，然后在每个满足 jj 指数。最后我们会做 new_vec = B(:,booleanVector);

Answer 2

另一种选择是使用 pdist2，如下所示：

new_vec = B(:, any(pdist2(A', B', 'Chebychev') < 1, 1));

注意 pdist2 总是比你的方法快，但可能比 Wolfie 的建议慢，因为 pdist2 总是计算 A 和 [= 的所有点之间的所有距离16=].

比较

我会比较：

原文: 您在回答中提供的代码
优化: Wolfie提供的代码
pdist2：我的解决方案使用 pdist2
bsxfun: rahnema1 的回答
bsxfun (>=2016b)：rahnema1 使用新的 2016b 功能的答案

使用以下示例数据

A = rand(2, N)*N*relativeAmplitude;
B = rand(2, N)*N*relativeAmplitude;

N 和 relativeAmplitude=1 函数的执行时间：

relativeAmplitude 和 N=10000 函数的执行时间：

结论

所有解决方案（Wolfie、rahnema1 和我的）都比原始算法快。

Optimised (Wolfie) vs pdist2 (mine)：如果 B 的索引很可能会在 A，那么 Wolfie 的答案可能会快 50 倍，但如果不太可能，pdist 可能会快 50%。请注意，我的解决方案的执行时间与 relativeAmplitude 无关，而 Wolfie 的则不然，但 Wolfie 的答案在某些情况下可能要快得多。

bsxfun (rahnema1) vs pdist2 (我的)：没有新的 R2016b 功能，bsxfun 总是慢 50%比 pdist2，否则两种方法总是（几乎）同样快。

Answer 3

这是一个向量化的解决方案：

cur_x = A(1,:);
cur_y = A(2,:);
B1= reshape(B(1,:),[],1);
B2= reshape(B(2,:),[],1);
condition = abs(bsxfun(@minus,B2,cur_y))<=1 & ...
            abs(bsxfun(@minus,B1,cur_x))<=1;

[x ,~]=find(condition);
new_vec = [[0;0] B(:,x)];

从 MATLAB r2016b 开始，您可以将 condition 写为：

condition = abs(B2-cur_y)<=1 & ...
            abs(B1-cur_x)<=1;

或

condition = B2 <= cur_y + 1 & B2 >= cur_y - 1 & ...
               B1 <= cur_x + 1 & B1 >= cur_x - 1;

*从@Wolfie 的回答中窃取的 abs(B(2,jj)-A(2,ii)) <= 1 的想法。

检查坐标是否在另一个矩阵中任何点的给定距离内

Check if coordinates are within given distance of any points in another matrix

performance

matlab

distance

matrix