A faster and more compact way to create a list of distances among all the pairs of points

Question

Sim 2023-4-28

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1954724-a-faster-and-more-compact-way-to-create-a-list-of-distances-among-all-the-pairs-of-points

编辑： chicken vector 2023-4-29

采纳的回答： chicken vector

test.txt

在 MATLAB Online 中打开

Hi, could you suggest a faster and more compact way to create a list of distances among all the pairs of points?

My attempt here below:

% Input (x and y coordinates of 6 points)

x = [1 2 2 3 4 5];

y = [1 2 3 7 2 5];

% Plot just to see the 6 points

plot(x,y,'o','MarkerFaceColor','b','markersize',15)

xlim([0 10])

ylim([0 10])

% Calculate the distances among each pair of points

Z = squareform(pdist([x' y']));

% Create a list that includes 3 elements: i-point ID, j-point ID, distance(i,j)

k = 1;

for i = 1 : length(x)-1

for j = i+1 : length(x)

list(k,:) = [i j Z(i,j)];

k = k + 1;

end

list,

list = 15×3

1.0000 2.0000 1.4142 1.0000 3.0000 2.2361 1.0000 4.0000 6.3246 1.0000 5.0000 3.1623 1.0000 6.0000 5.6569 2.0000 3.0000 1.0000 2.0000 4.0000 5.0990 2.0000 5.0000 2.0000 2.0000 6.0000 4.2426 3.0000 4.0000 4.1231

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

chicken vector 2023-4-29

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1954724-a-faster-and-more-compact-way-to-create-a-list-of-distances-among-all-the-pairs-of-points#answer_1225819

编辑：chicken vector 2023-4-29

在 MATLAB Online 中打开

N = 1e4;
x = randi(10,N,1);
y = randi(10,N,1);
tic
xIdx = repmat(1 : length(x), length(x), 1);
yIdx = xIdx';
vectorIdx = (1 : size(xIdx, 1))' > (1 : size(xIdx, 2));
xy = [x(:), y(:)];
dist = pdist2(xy, xy);
distPdist = dist(vectorIdx);
list = [xIdx(vectorIdx) , ...
    yIdx(vectorIdx) , ...
    distPdist]
list = 49995000×3
    1.0000    2.0000    5.3852
    1.0000    3.0000    6.7082
    1.0000    4.0000    3.0000
    1.0000    5.0000    5.8310
    1.0000    6.0000    8.6023
    1.0000    7.0000    2.2361
    1.0000    8.0000    8.5440
    1.0000    9.0000    8.5440
    1.0000   10.0000    5.0000
    1.0000   11.0000   10.8167
toc
Elapsed time is 2.501384 seconds.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

Image Analyst 2023-4-28

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1954724-a-faster-and-more-compact-way-to-create-a-list-of-distances-among-all-the-pairs-of-points#answer_1225344

在 MATLAB Online 中打开

Try pdist2

% Input (x and y coordinates of 6 points)
x = [1 2 2 3 4 5];
y = [1 2 3 7 2 5];
xy = [x(:), y(:)]
xy = 6×2
     1     1
     2     2
     2     3
     3     7
     4     2
     5     5
% Get distances between every (x,y) point and every other (x,y) point:
distances = pdist2(xy, xy)
distances = 6×6
         0    1.4142    2.2361    6.3246    3.1623    5.6569
    1.4142         0    1.0000    5.0990    2.0000    4.2426
    2.2361    1.0000         0    4.1231    2.2361    3.6056
    6.3246    5.0990    4.1231         0    5.0990    2.8284
    3.1623    2.0000    2.2361    5.0990         0    3.1623
    5.6569    4.2426    3.6056    2.8284    3.1623         0

12 个评论
显示 10更早的评论隐藏 10更早的评论

Image Analyst 2023-4-28

No, I must be thinking of the old way. Anyway, you can post a "final" fixed up program for a new answer and he can accept that.

Sim 2023-4-29

Thanks a lot both @Image Analyst and @chicken vector!!

If @chicken vector you want to re-post an Answer as @Image Analyst suggested I will accept it :-) Meanwhile, obviously, I will upvote both :-)

请先登录，再进行评论。

Answer 3

chicken vector 2023-4-28

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1954724-a-faster-and-more-compact-way-to-create-a-list-of-distances-among-all-the-pairs-of-points#answer_1225384

编辑：chicken vector 2023-4-28

在 MATLAB Online 中打开

You can build the indeces without for loop:

N = 5e2;
x = randi(10,1,N);
y = randi(10,1,N);
% Loop method:
tic;
k = 1;
for i = 1 : length(x)-1
    for j = i+1 : length(x)
        loopList(k,:) = [i j];
        k = k + 1;
    end
end
loopTime = toc;
% Vectorised method:
tic;
xIdx = repmat(1 : length(x), length(x), 1);
yIdx = xIdx';
vectorList = [xIdx((1 : size(xIdx, 1))' > (1 : size(xIdx, 2))) , ...
              yIdx((1 : size(yIdx, 1))' > (1 : size(yIdx', 2)))];
vectorTime = toc;
fprintf("Time with for loop:        %.3f seconds\n", loopTime)
Time with for loop:        0.988 seconds
fprintf("Time with vectorisation:   %.3f seconds\n", vectorTime)
Time with vectorisation:   0.009 seconds

You can also increase the speed for computing the distance with the following:

% Squareform method:
tic
squareFormZ = squareform(pdist([x' y']));
squareFormTime = toc;
% Vectorised method:
tic;
X = repmat(x, length(x), 1);
Y = repmat(y, length(y), 1);
deltaX = tril(x' - X, -1);
deltaY = tril(y' - Y, -1);
vectorZ = sqrt(deltaX(:).^2 + deltaY(:).^2);
vectorTime = toc;
fprintf("Time with squareform:        %.3f seconds\n", squareFormTime)
Time with squareform:        0.072 seconds
fprintf("Time with vectorisation:     %.3f seconds\n", vectorTime)
Time with vectorisation:     0.009 seconds

You can build your original list with the following wrapped up:

% Data:
x = [1 2 2 3 4 5];
y = [1 2 3 7 2 5];
% Initialise indeces:
xIdx = repmat(1 : length(x), length(x), 1);
yIdx = xIdx';
% Initialise elements distribution:
X = repmat(x, length(x), 1);
Y = repmat(y, length(y), 1);
% Compute distances:
deltaX = tril(x' - X, -1);
deltaY = tril(y' - Y, -1);
% Re-arrange to vector:
deltaX = deltaX((1 : size(deltaX, 1))' > (1 : size(deltaX, 2)));
deltaY = deltaY((1 : size(deltaY, 1))' > (1 : size(deltaY, 2)));
% Build lsit:
list = [xIdx((1 : size(xIdx, 1))' > (1 : size(xIdx, 2))) , ...
        yIdx((1 : size(yIdx, 1))' > (1 : size(yIdx', 2))) , ...
        sqrt(deltaX.^2 + deltaY.^2)]
list = 15×3
    1.0000    2.0000    1.4142
    1.0000    3.0000    2.2361
    1.0000    4.0000    6.3246
    1.0000    5.0000    3.1623
    1.0000    6.0000    5.6569
    2.0000    3.0000    1.0000
    2.0000    4.0000    5.0990
    2.0000    5.0000    2.0000
    2.0000    6.0000    4.2426
    3.0000    4.0000    4.1231