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:
Calculate distance between many points and one certain point

Subject: Calculate distance between many points and one certain point

From: JohnMC

Date: 18 Aug, 2010 19:23:04

Message: 1 of 9

I have a large matrix, I want to calculate the distance of each point of the matrix from one certain point which is also in the matrix.

if I used a loop,

for i= 1:m
   for j= 1:n
  dist(i,j) = sqrt((i-x0)^2 + (j-y0)^2));
end
end

Is there any fast way to do this, because the matrix I am processing is large.

Thanks a lot.

Subject: Calculate distance between many points and one certain point

From: Sean

Date: 18 Aug, 2010 19:30:28

Message: 2 of 9

"JohnMC " <nirmathink@gmail.com> wrote in message <i4hbuo$fd2$1@fred.mathworks.com>...
> I have a large matrix, I want to calculate the distance of each point of the matrix from one certain point which is also in the matrix.
>
> if I used a loop,
>
> for i= 1:m
> for j= 1:n
> dist(i,j) = sqrt((i-x0)^2 + (j-y0)^2));
> end
> end
>
> Is there any fast way to do this, because the matrix I am processing is large.
>
> Thanks a lot.

%
[xx yy] = meshgrid(1:n,1:m);
my_dist = sqrt((xx-x0)^2 + (yy-y0)^2));

Subject: Calculate distance between many points and one certain point

From: Sean

Date: 18 Aug, 2010 19:36:04

Message: 3 of 9

"Sean " <sean.dewolski@nospamplease.umit.maine.edu> wrote in message <i4hcck$h6j$1@fred.mathworks.com>...
> "JohnMC " <nirmathink@gmail.com> wrote in message <i4hbuo$fd2$1@fred.mathworks.com>...
> > I have a large matrix, I want to calculate the distance of each point of the matrix from one certain point which is also in the matrix.
> >
> > if I used a loop,
> >
> > for i= 1:m
> > for j= 1:n
> > dist(i,j) = sqrt((i-x0)^2 + (j-y0)^2));
> > end
> > end
> >
> > Is there any fast way to do this, because the matrix I am processing is large.
> >
> > Thanks a lot.
>
> %
> [xx yy] = meshgrid(1:n,1:m);
> my_dist = sqrt((xx-x0)^2 + (yy-y0)^2));

Of course that's going to give you a "Error: matrix dimensions must agree"
It should've read:
my_dist = sqrt((xx-x0).^2 + (yy-y0).^2));

Subject: Calculate distance between many points and one certain point

From: Andy

Date: 18 Aug, 2010 19:40:31

Message: 4 of 9

"JohnMC " <nirmathink@gmail.com> wrote in message <i4hbuo$fd2$1@fred.mathworks.com>...
> I have a large matrix, I want to calculate the distance of each point of the matrix from one certain point which is also in the matrix.
>
> if I used a loop,
>
> for i= 1:m
> for j= 1:n
> dist(i,j) = sqrt((i-x0)^2 + (j-y0)^2));
> end
> end
>
> Is there any fast way to do this, because the matrix I am processing is large.
>
> Thanks a lot.

A few things:
1) Don't use i and j as your index variables, as these are both used for the complex unit.
2) Your loop does not use points given in a matrix. Rather it finds the distance from your point (x0,y0) to each integer point of the form (i,j) for 1<=i<=m and 1<=j<=n. This doesn't sound like your intent.
3) How are your points stored? I will assume they are in an nx2 matrix, where the first column is the x-value and the second column is the y-value.
4) sqrt is vectorized, so, under the assumption from (3), the following will work:

n=100; % number of points
A=rand(n,2); % random data
x0 = 0.5;
y0 = 0.5; % a fixed point of interest
distances = sqrt((A(:,1)-x0).^2 + (A(:,2)-y0).^2);

Subject: Calculate distance between many points and one certain point

From: Matt J

Date: 18 Aug, 2010 19:43:07

Message: 5 of 9



Another method, which will save you a bit of memory, as compared to meshgrid


dist=sqrt( bsxfun(@plus, ((1:m).'-x0).^2 , ((1:n)-y0).^2 ) )

Subject: Calculate distance between many points and one certain point

From: JohnMC

Date: 18 Aug, 2010 20:17:20

Message: 6 of 9

"Sean " <sean.dewolski@nospamplease.umit.maine.edu> wrote in message <i4hcn4$bbo$1@fred.mathworks.com>...
> "Sean " <sean.dewolski@nospamplease.umit.maine.edu> wrote in message <i4hcck$h6j$1@fred.mathworks.com>...
> > "JohnMC " <nirmathink@gmail.com> wrote in message <i4hbuo$fd2$1@fred.mathworks.com>...
> > > I have a large matrix, I want to calculate the distance of each point of the matrix from one certain point which is also in the matrix.
> > >
> > > if I used a loop,
> > >
> > > for i= 1:m
> > > for j= 1:n
> > > dist(i,j) = sqrt((i-x0)^2 + (j-y0)^2));
> > > end
> > > end
> > >
> > > Is there any fast way to do this, because the matrix I am processing is large.
> > >
> > > Thanks a lot.
> >
> > %
> > [xx yy] = meshgrid(1:n,1:m);
> > my_dist = sqrt((xx-x0)^2 + (yy-y0)^2));
>
> Of course that's going to give you a "Error: matrix dimensions must agree"
> It should've read:
> my_dist = sqrt((xx-x0).^2 + (yy-y0).^2));

it seems the dimension of matrix is switched with meshgrid. (x,y) becomes (y,x).

a simple example:
(1,1) (1,2)
(2,1) (2,2)

the point is (3,4)

meshgrid gives distance matrix as

3.61 3.16
2.83 2.24

but the distance between (2,1) and (3,4) should be
sqrt(1+9) = 3.16 , NOT 2.83.

Subject: Calculate distance between many points and one certain point

From: Roger Stafford

Date: 18 Aug, 2010 20:30:24

Message: 7 of 9

"JohnMC " <nirmathink@gmail.com> wrote in message <i4hbuo$fd2$1@fred.mathworks.com>...
> I have a large matrix, I want to calculate the distance of each point of the matrix from one certain point which is also in the matrix.
>
> if I used a loop,
>
> for i= 1:m
> for j= 1:n
> dist(i,j) = sqrt((i-x0)^2 + (j-y0)^2));
> end
> end
>
> Is there any fast way to do this, because the matrix I am processing is large.
>
> Thanks a lot.
- - - - - - - - - -
  One of the shortcomings of your nested for-loops, and of various vectorizations of it, is that the same computations are repeated up to eight times, depending on the location of (x0,y0) relative to the center of the m by n rectangle. You have stated that (x0,y0) "is also in the matrix", meaning, I would suppose, that x0 and y0 are both integers in the range 1:m and 1:n. If you divide up the full rectangle into octants relative to (x0,y0) as their center, you can do the nested loops just for the largest of these octants. Then all the remaining octants can be filled in by merely copying the contents of this one octant appropriately. You might experiment with that and see if it is faster than any of the offered vectorized schemes. It will obviously be the most advantageous when (x0,y0) lies near the center of the rectangle.

Roger Stafford

Subject: Calculate distance between many points and one certain point

From: JohnMC

Date: 18 Aug, 2010 20:40:26

Message: 8 of 9

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <i4hft0$t50$1@fred.mathworks.com>...
> "JohnMC " <nirmathink@gmail.com> wrote in message <i4hbuo$fd2$1@fred.mathworks.com>...
> > I have a large matrix, I want to calculate the distance of each point of the matrix from one certain point which is also in the matrix.
> >
> > if I used a loop,
> >
> > for i= 1:m
> > for j= 1:n
> > dist(i,j) = sqrt((i-x0)^2 + (j-y0)^2));
> > end
> > end
> >
> > Is there any fast way to do this, because the matrix I am processing is large.
> >
> > Thanks a lot.
> - - - - - - - - - -
> One of the shortcomings of your nested for-loops, and of various vectorizations of it, is that the same computations are repeated up to eight times, depending on the location of (x0,y0) relative to the center of the m by n rectangle. You have stated that (x0,y0) "is also in the matrix", meaning, I would suppose, that x0 and y0 are both integers in the range 1:m and 1:n. If you divide up the full rectangle into octants relative to (x0,y0) as their center, you can do the nested loops just for the largest of these octants. Then all the remaining octants can be filled in by merely copying the contents of this one octant appropriately. You might experiment with that and see if it is faster than any of the offered vectorized schemes. It will obviously be the most advantageous when (x0,y0) lies near the center of the rectangle.
>
> Roger Stafford

This is a great idea! I never thought about that way. The position of (x0,y0) is arbitrary, i will see how well i can improve the speed.

Subject: Calculate distance between many points and one certain point

From: Matt J

Date: 19 Aug, 2010 22:12:20

Message: 9 of 9

"JohnMC " <nirmathink@gmail.com> wrote in message <i4hgfq$b42$1@fred.mathworks.com>...

> > - - - - - - - - - -
> > One of the shortcomings of your nested for-loops, and of various vectorizations of it, is that the same computations are repeated up to eight times, depending on the location of (x0,y0) relative to the center of the m by n rectangle. You have stated that (x0,y0) "is also in the matrix", meaning, I would suppose, that x0 and y0 are both integers in the range 1:m and 1:n. If you divide up the full rectangle into octants relative to (x0,y0) as their center, you can do the nested loops just for the largest of these octants. Then all the remaining octants can be filled in by merely copying the contents of this one octant appropriately. You might experiment with that and see if it is faster than any of the offered vectorized schemes. It will obviously be the most advantageous when (x0,y0) lies near the center of the rectangle.
> >
> > Roger Stafford
>
> This is a great idea! I never thought about that way. The position of (x0,y0) is arbitrary, i will see how well i can improve the speed.
===================

It's worth a try, but I wonder about locality considerations. If you compute
dist(i,j) and then copy it to symmetrically-related
coordinates (i',j') , you end up making a lot of disconntiguous memory accesses. I'm wondering if this would counteract the benefits of the 8-fold reduction in flops...

Tags for this Thread

No tags are associated with 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