Is it possible to calculate the average Manhattan distance between a set of 2D points with one function?
19 views (last 30 days)
Show older comments
Is there an easier way to calculate the average Manhattan distance between a set of points easier than I have it in my code? I have a matrix, which contains a set of 2D points (the columns corespond to the x and y coordinates).
%for the first point
[idx,~]=dsearchn(isec(2:end,:),isec(1,:));
sum=pdist2(isec(1,:), isec(idx+1,:), 'cityblock');
%for the rest of the points
for i=2:size(isec,1)-1
others=[isec(1:i-1,:); isec(i+1:end,:)];
[idx,~]=dsearchn(others,isec(i,:));
man=pdist2(isec((i,:), others(idx,:), 'cityblock');
sum=sum+man;
end
%for the last point
[idx,~]=dsearchn(isec(1:end-1,:),isec(end,:));
sum=sum+pdist2(isec(end,:), isec(idx,:), 'cityblock');
avg_dist=sum/size(isec,1);
As dsearch cannot calculate other distances than euclidean, I use it to find the index of the nearest point. After that I have to call the pdist2 function to measure the cityblock distance. What complicates things even more is the fact, that I have to exclude the current point (to which I'm trying to find the closest one); that's the purpos of my 'others' variable and the 2 pieces of code above and below the for-cycle.
To give a bit of context:
The goal is image segmentation. The points are actually line intersections in a grid. I want to calculate the average Manhattan distance in order to use the result as a treshhold to determine which points are roughly in the given row/column (unlike in the case of crosswords, sudokus, nonograms I'm not interested in the square areas between the lines, rather in the intersections).
2 Comments
David Goodmanson
on 23 Feb 2020
Hi Balint, are you looking for the average distance for all possible pairs of points, or the average distance for one particular path that visits all the points?
Accepted Answer
Jon
on 24 Feb 2020
Edited: Jon
on 24 Feb 2020
I think this does what you want. You could probably make it more efficient recognizing the symmetry of the distance matrix, but just wanted to get the main idea across
% just some data to try, you'd put your here
x = [1 8 7 2 6 3]
y = [3 6 2 5 1 4]
numPoints = length(x)
% make array of Manhattan distances (L1 norm) between between each point to all other points
D = zeros(numPoints)
for j = 1:numPoints
for k = 1:numPoints
D(j,k) = norm([x(j),y(j)] -[x(k),y(k)],1);
end
end
% set main diagonal to inf so it won't be included when looking for minimum
% distance
D = D + diag(inf(numPoints,1));
% find minimum distance for each row
dMin = min(D,[],2);
% find average minimum
dAvg = mean(dMin)
3 Comments
Jon
on 25 Feb 2020
Edited: Jon
on 25 Feb 2020
Here's a way to do it that is very simple without any loops. I benchmarked it using the MATLAB tic toc commands on my machine and found that with a 4000 points the earlier way with loops took 5 seconds and the one below with no loops took only 0.4 seconds!
% just some data to try, you'd put your here
x = [1 8 7 2 6 3];
y = [3 6 2 5 1 4];
numPoints = length(x)
tic
% find component distances
X = x - x';
Y = y - y';
% find total "Manhattan Distance"
D = abs(X) + abs(Y);
% set main diagonal to inf so it won't be included when looking for minimum
% distance
D(1:numPoints+1:end) = inf;
% find minimum distance for each row
dMin = min(D,[],2);
% find average minimum
dAvg = mean(dMin)
More Answers (0)
See Also
Categories
Find more on Performance and Memory in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!