Is it possible to calculate the average Manhattan distance between a set of 2D points with one function?

19 views (last 30 days)
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
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?
Bálint Udvardy
Bálint Udvardy on 24 Feb 2020
Sorry, my question is quite confusing. I'm looking for the former mentioned one. More specifically: I want to calculate the distance of the nearest point (excluding the one I'm currently on) for all of the points separatelly; so there will be just as many 'nearest distances' as many points there are. After that I would like to average those distances. So I want an average nearest distance (one number) for the whole set.

Sign in to comment.

Accepted Answer

Jon
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
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)

Sign in to comment.

More Answers (0)

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!