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:
Vectorize Difference Between Two Sets of Points

Subject: Vectorize Difference Between Two Sets of Points

From: Bill Woessner

Date: 26 Jan, 2009 21:51:33

Message: 1 of 10

I'm sure this question has been asked and answered dozens of times.
But for the life of me, I can't find the answer.

I have two sets of 2D points, call them A and B. They're stored in
matrices such that size(A) = [M 2] and size(B) = [N 2]. For each a in
A and b in B, I need to compute a - b. This is painfully slow using
for loops. I've been trying to use repmat to speed it up, but so
far... it's hideous:

M = length(A);
N = length(B);

A2 = zeros(M, 1, 2);
A2(:, 1, :) = A;
A2 = repmat(A2, [1 N 1]);

B2 = zeros(1, N, 2);
B2(1, :, :) = B;
B2 = repmat(B2, [M 1 1]);

delta = A2 - B2;

A and B are relatively small so memory is not a concern. But speed
is. I know there's probably a better way to accomplish this. Can
someone please point me in the right direction?

Thanks in advance,
Bill Woessner

Subject: Vectorize Difference Between Two Sets of Points

From: NZTideMan

Date: 26 Jan, 2009 22:16:51

Message: 2 of 10

On Jan 27, 10:51=A0am, Bill Woessner <woess...@gmail.com> wrote:
> I'm sure this question has been asked and answered dozens of times.
> But for the life of me, I can't find the answer.
>
> I have two sets of 2D points, call them A and B. =A0They're stored in
> matrices such that size(A) =3D [M 2] and size(B) =3D [N 2]. =A0For each a=
 in
> A and b in B, I need to compute a - b. =A0This is painfully slow using
> for loops. =A0I've been trying to use repmat to speed it up, but so
> far... it's hideous:
>
> M =3D length(A);
> N =3D length(B);
>
> A2 =3D zeros(M, 1, 2);
> A2(:, 1, :) =3D A;
> A2 =3D repmat(A2, [1 N 1]);
>
> B2 =3D zeros(1, N, 2);
> B2(1, :, :) =3D B;
> B2 =3D repmat(B2, [M 1 1]);
>
> delta =3D A2 - B2;
>
> A and B are relatively small so memory is not a concern. =A0But speed
> is. =A0I know there's probably a better way to accomplish this. =A0Can
> someone please point me in the right direction?
>
> Thanks in advance,
> Bill Woessner

How about this:
% Convert to complex vectors
Ac=3DA(:,1) + i*A(:,2);
Bc=3DB(:,1) + i*B(:,2);
% Allocate storage
D=3Dzeros(M,N);
for ib=3D1:N
D(:,ib)=3DAc - Bc(ib);
end

Subject: Vectorize Difference Between Two Sets of Points

From: someone

Date: 26 Jan, 2009 22:19:02

Message: 3 of 10

Bill Woessner <woessner@gmail.com> wrote in message <43737d62-9a77-4c67-93d1-8f4112930c99@x16g2000prn.googlegroups.com>...
> I'm sure this question has been asked and answered dozens of times.
> But for the life of me, I can't find the answer.
>
> I have two sets of 2D points, call them A and B. They're stored in
> matrices such that size(A) = [M 2] and size(B) = [N 2]. For each a in
> A and b in B, I need to compute a - b. This is painfully slow using
> for loops. I've been trying to use repmat to speed it up, but so
> far... it's hideous:
>
> M = length(A);
> N = length(B);
>
> A2 = zeros(M, 1, 2);
> A2(:, 1, :) = A;
> A2 = repmat(A2, [1 N 1]);
>
> B2 = zeros(1, N, 2);
> B2(1, :, :) = B;
> B2 = repmat(B2, [M 1 1]);
>
> delta = A2 - B2;
>
> A and B are relatively small so memory is not a concern. But speed
> is. I know there's probably a better way to accomplish this. Can
> someone please point me in the right direction?
>
> Thanks in advance,
> Bill Woessner

How are you subtracting matricies of different sizes?

Subject: Vectorize Difference Between Two Sets of Points

From: Matt

Date: 26 Jan, 2009 22:29:03

Message: 4 of 10

NZTideMan <mulgor@gmail.com> wrote in message <c646b7d0-a6ca-4a62-a0db-983f49e361ca@z6g2000pre.googlegroups.com>...
> On Jan 27, 10:51=A0am, Bill Woessner <woess...@gmail.com> wrote:
> > I'm sure this question has been asked and answered dozens of times.
> > But for the life of me, I can't find the answer.
> >
> > I have two sets of 2D points, call them A and B. =A0They're stored in
> > matrices such that size(A) =3D [M 2] and size(B) =3D [N 2]. =A0For each a=
> in
> > A and b in B, I need to compute a - b. =A0This is painfully slow using
> > for loops. =A0I've been trying to use repmat to speed it up, but so
> > far... it's hideous:
> >
> > M =3D length(A);
> > N =3D length(B);
> >
> > A2 =3D zeros(M, 1, 2);
> > A2(:, 1, :) =3D A;
> > A2 =3D repmat(A2, [1 N 1]);
> >
> > B2 =3D zeros(1, N, 2);
> > B2(1, :, :) =3D B;
> > B2 =3D repmat(B2, [M 1 1]);
> >
> > delta =3D A2 - B2;
> >
> > A and B are relatively small so memory is not a concern. =A0But speed
> > is. =A0I know there's probably a better way to accomplish this. =A0Can
> > someone please point me in the right direction?
> >
> > Thanks in advance,
> > Bill Woessner
>
> How about this:
> % Convert to complex vectors
> Ac=3DA(:,1) + i*A(:,2);
> Bc=3DB(:,1) + i*B(:,2);
> % Allocate storage
> D=3Dzeros(M,N);
> for ib=3D1:N
> D(:,ib)=3DAc - Bc(ib);
> end

You can avoid the for-loop altogether using bsxfun

Ac=A(:,1) + i*A(:,2);
Bc=B(:,1) + i*B(:,2);
Bc=Bc.';
D=bsxfun(@minus, Ac,Bc);

Subject: Vectorize Difference Between Two Sets of Points

From: Matt

Date: 26 Jan, 2009 22:33:02

Message: 5 of 10

"Matt " <mjacobson.removethis@xorantech.com> wrote in message <glldff$m5s$1@fred.mathworks.com>...
>
> > How about this:
> > % Convert to complex vectors
> > Ac=3DA(:,1) + i*A(:,2);
> > Bc=3DB(:,1) + i*B(:,2);
> > % Allocate storage
> > D=3Dzeros(M,N);
> > for ib=3D1:N
> > D(:,ib)=3DAc - Bc(ib);
> > end
>
> You can avoid the for-loop altogether using bsxfun
>
> Ac=A(:,1) + i*A(:,2);
> Bc=B(:,1) + i*B(:,2);
> Bc=Bc.';
> D=bsxfun(@minus, Ac,Bc);

It's actually sad that you can't do this for 3D coordinates. MATLAB would have to support higher dimensional quaternions for that to be possible...

Subject: Vectorize Difference Between Two Sets of Points

From: Matt Fig

Date: 26 Jan, 2009 22:37:01

Message: 6 of 10

Just in case the OP is wondering, to get a solution in the same form he has, use

delta(:,:,1) = real(D);
delta(:,:,2) = imag(D);




{eZdiWW5ZVtttdtVV:^i^\e/]t#VjVbbt`iddj{ncXkVd]tZc]VdaNBZaXt

Subject: Vectorize Difference Between Two Sets of Points

From: Roger Stafford

Date: 26 Jan, 2009 22:39:02

Message: 7 of 10

Bill Woessner <woessner@gmail.com> wrote in message <43737d62-9a77-4c67-93d1-8f4112930c99@x16g2000prn.googlegroups.com>...
> I'm sure this question has been asked and answered dozens of times.
> But for the life of me, I can't find the answer.
>
> I have two sets of 2D points, call them A and B. They're stored in
> matrices such that size(A) = [M 2] and size(B) = [N 2]. For each a in
> A and b in B, I need to compute a - b. This is painfully slow using
> for loops. I've been trying to use repmat to speed it up, but so
> far... it's hideous:
>
> M = length(A);
> N = length(B);
>
> A2 = zeros(M, 1, 2);
> A2(:, 1, :) = A;
> A2 = repmat(A2, [1 N 1]);
>
> B2 = zeros(1, N, 2);
> B2(1, :, :) = B;
> B2 = repmat(B2, [M 1 1]);
>
> delta = A2 - B2;
>
> A and B are relatively small so memory is not a concern. But speed
> is. I know there's probably a better way to accomplish this. Can
> someone please point me in the right direction?
>
> Thanks in advance,
> Bill Woessner

 [I,J] = ndgrid(1:M,1:N);
 delta = A(I,:)-B(J,:);

Roger Stafford

Subject: Vectorize Difference Between Two Sets of Points

From: Matt Fig

Date: 26 Jan, 2009 23:03:02

Message: 8 of 10

Even with reshape, I think this should be faster than ndgrid:


[I,J] = meshgrid(1:N,1:M);
delta = reshape(A(J,:)-B(I,:),M,N,2);





`<vcYf\1c^Zvmvde}_XZvv%_gXX\v\lkfgkfDpXXkPlY`_ffe}\XvXd7bvf

Subject: Vectorize Difference Between Two Sets of Points

From: Roger Stafford

Date: 26 Jan, 2009 23:12:02

Message: 9 of 10

"Matt Fig" <spamanon@yahoo.com> wrote in message <gllff6$6n4$1@fred.mathworks.com>...
> Even with reshape, I think this should be faster than ndgrid:
>
> [I,J] = meshgrid(1:N,1:M);
> delta = reshape(A(J,:)-B(I,:),M,N,2);

  Now you have me intrigued, Matt. I was under the impression that 'ndgrid' and 'meshgrid' were as alike in execution times as two peas in a pod. They are faced with almost the same task.

Roger Stafford

Subject: Vectorize Difference Between Two Sets of Points

From: Matt Fig

Date: 26 Jan, 2009 23:36:02

Message: 10 of 10

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message
> Now you have me intrigued, Matt. I was under the impression that 'ndgrid' and 'meshgrid' were as alike in execution times as two peas in a pod. They are faced with almost the same task.
>
> Roger Stafford


Hello Roger,

Yes, you are correct, I should have made it clear I was thinking about inlining meshgrid, I pasted the wrong code. Sorry.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all
A = reshape(randperm(100),50,2);
B = reshape(randperm(80),40,2);
M = length(A);
N = length(B);
t = zeros(1,2);

tic
I = (1:N);
J = (1:M)';
I = I(ones(1,M),:);
J = J(:,ones(N,1));
delta1 = reshape(A(J,:)-B(I,:),M,N,2);
t(1) = toc;

tic
[I,J] = ndgrid(1:M,1:N);
delta2 = A(I,:)-B(J,:);
t(2) = toc;

all(delta1(:)==delta2(:))
t/min(t)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

ans =
     1
ans =
            1 41.141




JKGCEKRQVJQQVaQ;IaCWRCCaMO{'CaXCaQV[a"JNQGWhGPDE/NChoDOGPaa

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