File Exchange

image thumbnail

Distance Matrix

version 1.2 (3.95 KB) by

fast, vectorized inter/intra-point distance matrix calculation (Euclidean, Manhattan, or Chebyshev)

18 Downloads

Updated

View License

Computes a Distance Matrix for One or Two Sets of Points. (Returns the point-to-point distance between all pairs of points, similar to PDIST in the Statistics Toolbox, for those without it)
 
  Description: Computes a matrix of pair-wise distances between points in
               A and B, using one of {euclidean,cityblock,chessboard} methods
 
  Inputs:
      A - (required) MxD matrix where M is the number of points in D dimensions
      B - (optional) NxD matrix where N is the number of points in D dimensions
                  if not provided, B is set to A by default
      METHOD - (optional) string specifying one of the following distance methods:
                  'euclidean' Euclidean distance (default)
                  'taxicab','manhattan','cityblock' Manhattan distance
                  'chebyshev','chessboard','chess' Chebyshev distance
                  'grid','diag' Diagonal grid distance
 
  Outputs:
      DMAT - MxN matrix of pair-wise distances between points in A and B
 
  Usage:
      dmat = distmat(a)
        -or-
      dmat = distmat(a,b)
        -or-
      dmat = distmat(a,method)
        -or-
      dmat = distmat(a,b,method)
 
  Example:
      % Pairwise Euclidean distances within a single set of 2D points
      xy = 10*rand(25,2); % 25 points in 2D
      dmat = distmat(xy);
      figure; plot(xy(:,1),xy(:,2),'.');
      for i=1:25, text(xy(i,1),xy(i,2),[' ' num2str(i)]); end
      figure; imagesc(dmat); colorbar
 
  Example:
      % Pairwise Manhattan distances within a single set of 2D points
      xy = 10*rand(25,2); % 25 points in 2D
      dmat = distmat(xy,'cityblock');
      figure; plot(xy(:,1),xy(:,2),'.');
      for i=1:25, text(xy(i,1),xy(i,2),[' ' num2str(i)]); end
      figure; imagesc(dmat); colorbar
 
  Example:
      % Pairwise Chebyshev distances within a single set of 2D points
      xy = 10*rand(25,2); % 25 points in 2D
      dmat = distmat(xy,'chebyshev');
      figure; plot(xy(:,1),xy(:,2),'.');
      for i=1:25, text(xy(i,1),xy(i,2),[' ' num2str(i)]); end
      figure; imagesc(dmat); colorbar
 
  Example:
      % Inter-point Euclidean distances for 2D points
      xy = 10*rand(15,2); % 15 points in 2D
      uv = 10*rand(25,2); % 25 points in 2D
      dmat = distmat(xy,uv);
      figure; plot(xy(:,1),xy(:,2),'.');
      for i=1:15, text(xy(i,1),xy(i,2),[' ' num2str(i)]); end
      figure; plot(uv(:,1),uv(:,2),'.');
      for i=1:25, text(uv(i,1),uv(i,2),[' ' num2str(i)]); end
      figure; imagesc(dmat); colorbar

Comments and Ratings (7)

Andres Tovar

Andres Tovar (view profile)

Usman Ali

Newbie: can I use this function to compute distance between two matrices.
e.g [A]= 9x6 and [B]= 1x6. and I want to the distance matrix between A and B.

WurmD

WurmD (view profile)

(in the code, the automatic option selection)
numels = n*n*dims;
opt = 2; if numels > 5e4, opt = 3; elseif n < 20, opt = 1; end

The choice of opt 3 if "n*n*dims > 5e4" might be too conservative.
Those with 8 GB of RAM might want to change it to "n*n*dims > 2e8" safely (tested with the code below)

 - One thing I would like help understanding is, why is the double for loop faster than and of the distmat options (in all tested situations)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
rabo = rand(600);

tic,
distrabo = zeros(size(rabo,1));
for i = 1:size(rabo,1)
    for j = i:size(rabo,1)
        distrabo(i,j) = norm(rabo(i,:)-rabo(j,:));
        distrabo(j,i) = distrabo(i,j);
    end
end
toc,

%%
tic,
[distraboCompare opt] = distmat(rabo,1);
fprintf('Opt1 supposedly faster for smaller inputs '), toc,
%%
tic,
[distraboCompare opt] = distmat(rabo,2);
fprintf('Opt2 supposedly faster for medium inputs '), toc,
%%
tic,
[distraboCompare opt] = distmat(rabo,3);
fprintf('Opt3 only half vectorized for less memory '), toc,
%%
tic,
[distraboCompare opt] = distmat(rabo,4);
fprintf('Opt4 fully vectorized but for also less memory '), toc,

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Peter Nave

Nina Hendrarini

Jon Dattorro

For more methods of fast computation of distance matrices, see the book:
Convex Optimization & Euclidean Distance Geometry, Dattorro
http://convexoptimization.com

Siyi Deng

Good implementation. Nice examples and screen shots.

Updates

1.2

Changed title and description.

1.1

Major revision to allow intra-point or inter-point distance calculation, and offers multiple distance type options, including Euclidean, Manhattan (cityblock), and Chebyshev (chess) distances.

MATLAB Release
MATLAB 8.4 (R2014b)
Acknowledgements

Inspired: IPDM: Inter-Point Distance Matrix

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video