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

在Matlab中，我有两个包含坐标的相当大的矩阵（A和B）。两条线代表x和y，每列代表笛卡尔坐标（x; y）。检查坐标是否在另一个矩阵中任意点的给定距离内

现在我想存储矩阵B中所有比1（米）更接近矩阵A中任意点的点。

我可以遍历所有的数据，但它非常耗时（矩阵是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

来源

2017-09-27 user3932876

现在您已经提供了代码，我看到您的“比1更接近”的定义由对x和y的单独检查组成。这意味着你的点可能有一个sqrt（2）的距离，并且不在范围内 - 这是有意的还是你会使用直接的二维（欧几里得）距离？ – Wolfie

这是故意的，但是感谢提示 – user3932876

@ m7913d请注意，可以使用'pdist2'，但对于这个尺寸的数据我们只想知道是否有距离小于1的数据可能会比较慢。另外，它们需要x y坐标为+/- 1，而不是1个单位，所以可能需要使用“城市街区距离” – Wolfie

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

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

注意pdist2总是快于你的方法，但可能比莫扎特的建议比较慢，因为pdist2总是计算所有点之间的所有距离为A和B。

比较

我会比较：

原始：由莫扎特
pdist2提供的代码：你在你的答案
优化提供的代码：我的解决方案使用pdist2
bsxfun：rahnema1的回答
bsxfun（> = 2016B）：使用新2016B功能

使用下面的示例数据

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

在执行时间rahnema1的回答功能N和relativeAmplitude=1：

的执行时间的relativeAmplitude功能和N=10000：

结论

所有的解决方案（莫扎特的，rahnema1的和我）比原来的算法快。

优化（莫扎特）VS pdist2（矿）：如果它是有可能的B指数将在A被找到，那么莫扎特的答案可能是50倍的速度更快，但如果它是不可能的，pdist可能是50％更快。请注意，我的解决方案的执行时间与relativeAmplitude无关，而Wolfie's不是，但在某些情况下，Wolfie的答案可能会快得多。

bsxfun（rahnema1）VS pdist2（矿）：没有新R2016b功能，bsxfun总是比〜慢pdist2 50％，否则这两种方法总是（几乎）一样快。

来源

2017-09-27 10:32:28 m7913d

感谢您的基准，是的，早期的人会希望找到一个满足距离的点，这一点非常重要。 – Wolfie

性能改进根据当前实施：

% 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坐标的距离内的任何A协调，退出循环早，以避免进一步的检查。

一种（潜在地更多的内存友好）替代初始化的NaN秒的2D阵列将初始化一个布尔false阵列，然后使它在每一个满足jj索引真。最后，我们会那么做new_vec = B(:,booleanVector);

来源

2017-09-27 10:05:48 Wolfie

好点与'I'和'J'。我习惯C和Python语法。我没有预分配，因为结果向量将小于B的大小的1％。这是否合理？如果循环在第一场比赛中休息，只有第一场比赛将被覆盖或我缺少什么？ – user3932876

@ user3932876我建议（在底部）预先分配一维布尔数组，然后使用逻辑索引。这将会提高内存的效率。我还交换了循环，以便存储任何“A（：，ii）”的1（x和y）内的所有'B（：，jj）'。 – Wolfie

@ user3932876再次读你的评论，对我来说澄清'break'只会退出* inner *循环，然后继续下一个'jj'，这可能是有用的。 – Wolfie

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

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为：从@Wolfie被盗abs(B(2,jj)-A(2,ii)) <= 1

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;

*想法回答。

来源

2017-09-27 10:32:42 rahnema1

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

回答

相关问题