Improvement of point cloud distance calculation in 2D

2 views (last 30 days)
Marc Laub
Marc Laub on 24 Apr 2020
Commented: Marc Laub on 25 Apr 2020
Hello everyone,
I have following question:
Given is an array of n- datapoints, with x and y coordinates for every point.
I know want to calculate the distance from every point to every other point.
For now the most efficient way for me is:
A=rand(5000,2);
Dista = squeeze(sqrt(sum((A - reshape(A',1,2,[])).^2,2)));
With increasing number of points this will take relativ long, and since i have to reapeat it inisde a loop it will in take to long in summary for me.
Theoretical, this could be optimized, since in my code above I calculate the distance from every point to everypoint, which is a waste of approximatly 50% (for an infinite number of points) of the calculations, since 50% of the calculations are done twice since the distcance from point A to point B is equal to B to A.
But how could I get this constraint inside my code, in best case without loops, since I guess, that this will slow it down in total.
All i have to do is to mirror the Dista matrix along the diagonal, but how do i manage that my code only calculates the uper(or lower) triangle of the matrix, in vectorized form.
Many thanks in advance.
Best regards
Marc
  6 Comments
Marc Laub
Marc Laub on 25 Apr 2020
I switched the order and now the asymetric one is faster.
Seems like
timeit(@()(A-B').^2)
bypasses this probelm.
timeit(@()(A.*B')
clearly shows that in the multiplacting case Matlabs gets some advantage of the symmetrie, here the symmetric one is alwys faster, independend on the order. In the upper case, there is nearly no advantage, maybe 0.001% and sometims the asymatric one beeing the faster one.
So the question is how to tell Matlab to get advantage of symmetric operations since the symmetrie is not automatically detected

Sign in to comment.

Answers (0)

Products


Release

R2019b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!