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

1 次查看（过去 30 天）
Sim
Sim 2023-4-28
编辑： chicken vector 2023-4-29
Ran in:
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
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

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

采纳的回答

chicken vector
chicken vector 2023-4-29
编辑：chicken vector 2023-4-29
Ran in:
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.

更多回答（2 个）

Image Analyst
Image Analyst 2023-4-28
Ran in:
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更早的评论
Image Analyst
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.

请先登录，再进行评论。

chicken vector
chicken vector 2023-4-28
编辑：chicken vector 2023-4-28
Ran in:
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

类别

在 Help Center 和 File Exchange 中查找有关 Performance and Memory 的更多信息

标签

产品

Community Treasure Hunt

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

Start Hunting!

Translated by