Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Computing euclidean distances between every row of a position matrix

Subject: Computing euclidean distances between every row of a position matrix

From: Kelsey

Date: 31 May, 2011 21:13:02

Message: 1 of 8

I'm new to MATLAB and have been learning how to program with it through Internet research and trial/error. I have a matrix that contains position data (columns are x, y, and z, and rows are each node on the graph.) I would like to create an N*N matrix (where N is the number of nodes on the graph) where each entry is the euclidean distance between the nodes specified by the indices of that entry. I know that I want to use a biograph object so that I can use the allshortestpaths function to get the distance matrix I want, but I need help creating the biograph object and connection matrix and somehow loading it with all of my position data so that I can use the allshortestpaths function.

Any help on biograph objects would be greatly appreciated!

-Kelsey

Subject: Computing euclidean distances between every row of a position matrix

From: Matt J

Date: 31 May, 2011 21:21:04

Message: 2 of 8

No idea what a biograph object is, but here's what I use:




function Graph=interdists(A,B)
%Finds the graph of distances between point coordinates
%
% (1) Graph=interdists(A,B)
%
% in:
%
% A: matrix of coordinates, for example [x1;y1;z1, x2;y2;z2 ,..., xM;yM;zM]
% but columns may be points in a space of any dimension, not just 3D.
%
% B: matrix of coordinates, similar to A, but possibly
% containing a different number N of columns/points.
% Default=A.
%
%
% out:
%
% Graph: The MxN matrix of separation distances in l2 norm. That is
% Graph(i,j) will be the distance between A(:,i) and B(:,j)
%
%
% (2) interdists(A,'noself') is the same as interdists(A), except the output
% diagonals will be NaN instead of zero. Hence, for example, operations
% like min(interdists(A,'noself')) will ignore self-distances.
%
% See also getgraph

noself=false;
if nargin<2
    B=A;
elseif ischar(B)&&strcmpi(B,'noself')
    noself=true;
    B=A;
end

B=permute(B,[1 3 2]);

Graph=l2norm(bsxfun(@minus, A, B),1);

Graph=permute(Graph,[2,3,1]);

if noself
    n=length(Graph);
   Graph(linspace(1,n^2,n))=nan;
end


function out=l2norm(X,varargin)
%out=l2norm(X,varargin)
%
%Takes the L2 norm along desired dimensions of the array X.
%
%VARARGIN can be any of the additional arguments of the sum.m function
%and follows the same conventions as this and similar functions. That is,
%if VARARGIN={}, the function operates along the first non-singleton
%dimension, etc...
%
%SEE ALSO sumsq


X=X.^2;

out=sum(X,varargin{:});

out=sqrt(out);

Subject: Computing euclidean distances between every row of a position matrix

From: Roger Stafford

Date: 31 May, 2011 22:51:04

Message: 3 of 8

"Kelsey" wrote in message <is3lku$ku1$1@newscl01ah.mathworks.com>...
> ...... I have a matrix that contains position data (columns are x, y, and z, and rows are each node on the graph.) I would like to create an N*N matrix (where N is the number of nodes on the graph) where each entry is the euclidean distance between the nodes specified by the indices of that entry. .......
> -Kelsey
- - - - - - - - -
  If M is the N by 3 matrix with each row a node's coordinates, try this:

 M2 = M*M.';
 D = diag(M2);
 M2 = sqrt(bsxfun(@plus,D,D.')-2*M2);

M2 would be your desired N by N matrix of distances.

Roger Stafford

Subject: Computing euclidean distances between every row of a position matrix

From: Matt J

Date: 1 Jun, 2011 13:54:05

Message: 4 of 8

"Roger Stafford" wrote in message <is3rco$5vj$1@newscl01ah.mathworks.com>...
>
> If M is the N by 3 matrix with each row a node's coordinates, try this:
>
> M2 = M*M.';
> D = diag(M2);
> M2 = sqrt(bsxfun(@plus,D,D.')-2*M2);
>
> M2 would be your desired N by N matrix of distances.
==================


This method can be less numerically robust. For example,

 %data
 M=ones(2,3)*10000;
 M(1,:)=M(1,:)+[0 0 .001]; %Euclidean distance should be .001

 M2 = M*M.';
 D = diag(M2);
 M2 = sqrt(bsxfun(@plus,D,D.')-2*M2),

gives me

M2 =

  1.0e-003 *

         0 0.9766
    0.9766 0


which is in 2% error whereas with interdists(), I get the result to numerical precision

>> M3=interdists(M.')

M3 =

         0 0.0010
    0.0010 0


>> M3(2)-.001

ans =

  2.0373e-013

Subject: Computing euclidean distances between every row of a position matrix

From: Kelsey

Date: 1 Jun, 2011 18:41:02

Message: 5 of 8

"Matt J" wrote in message <is5g9t$gs9$1@newscl01ah.mathworks.com>...
> "Roger Stafford" wrote in message <is3rco$5vj$1@newscl01ah.mathworks.com>...
> >
> > If M is the N by 3 matrix with each row a node's coordinates, try this:
> >
> > M2 = M*M.';
> > D = diag(M2);
> > M2 = sqrt(bsxfun(@plus,D,D.')-2*M2);
> >
> > M2 would be your desired N by N matrix of distances.
> ==================
>
>
> This method can be less numerically robust. For example,
>
> %data
> M=ones(2,3)*10000;
> M(1,:)=M(1,:)+[0 0 .001]; %Euclidean distance should be .001
>
> M2 = M*M.';
> D = diag(M2);
> M2 = sqrt(bsxfun(@plus,D,D.')-2*M2),
>
> gives me
>
> M2 =
>
> 1.0e-003 *
>
> 0 0.9766
> 0.9766 0
>
>
> which is in 2% error whereas with interdists(), I get the result to numerical precision
>
> >> M3=interdists(M.')
>
> M3 =
>
> 0 0.0010
> 0.0010 0
>
>
> >> M3(2)-.001
>
> ans =
>
> 2.0373e-013

Thank you all so very much for your help. Now, I have this array of distances between nodes and I want to find "k" (user input variable) number of minimums in each row. I'm trying to do the following:

%for i=1:numberOfNeighbors %find k (numberOfNeighbors) min distances between nodes
    minDistances = min(distanceMatrix, [], 2);
    if ((min(distanceMatrix, [], 2)) == 0)
        min(distanceMatrix, [], 2) = Inf;
    end
    
    [rowIndex, columnIndex] = min(distanceMatrix, [], 2);%find and store indexes
    minDistances = min(distanceMatrix, [], 2); %find and store distances

I've tried several other versions of the same idea, but either get an error saying that I can't reassign value to the variable min (except I'm never trying to use min as a variable), or I get all zeroes for the minima. I understand that the distance array has a 0 in each row that corresponds to the distance from a node to itself, but I want to reassign that to Inf so that minDistances is not just an array of 0 distances.

Any help on this further question would be greatly appreciated.

Subject: Computing euclidean distances between every row of a position matrix

From: Image Analyst

Date: 1 Jun, 2011 20:07:04

Message: 6 of 8

How about
minDistances = min(distanceMatrix(distanceMatrix>0), [], 2);
That way, you're only computing the minimum of values that are greater than zero. The elements having values that are zero (or less) are ignored.

Subject: Computing euclidean distances between every row of a position matrix

From: Kelsey

Date: 1 Jun, 2011 20:21:04

Message: 7 of 8

"Image Analyst" wrote in message <is6658$pbh$1@newscl01ah.mathworks.com>...
> How about
> minDistances = min(distanceMatrix(distanceMatrix>0), [], 2);
> That way, you're only computing the minimum of values that are greater than zero. The elements having values that are zero (or less) are ignored.

Thanks very much for the suggestion. I actually just realized that I can use the sort function to sort the distance matrix and then it's really easy to get any number of minimum values, and there indices are a piece of cake! Maybe that realization will help someone else in the future- seriously, way easier than dealing with the min function.

Subject: Computing euclidean distances between every row of a position matrix

From: Roger Stafford

Date: 1 Jun, 2011 20:58:07

Message: 8 of 8

"Matt J" wrote in message <is5g9t$gs9$1@newscl01ah.mathworks.com>...
> "Roger Stafford" wrote in message <is3rco$5vj$1@newscl01ah.mathworks.com>...
> > M2 = M*M.';
> > D = diag(M2);
> > M2 = sqrt(bsxfun(@plus,D,D.')-2*M2);
> This method can be less numerically robust. For example, .....
- - - - - - - - - -
  Yes, you are right, Matt. When the points are in a tight little cluster and located far away from the origin, the method I used will be less accurate than doing the subtractions first and then squaring the differences. It's the problem of evaluating (a-b)^2 rather than a^2-2*a*b+b^2. If a and b are both very large as compared with their difference, the first of these expressions will give more accurate results than the second.

Roger Stafford

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us