http://www.mathworks.com/matlabcentral/newsreader/view_thread/243164
MATLAB Central Newsreader  Vectorize Difference Between Two Sets of Points
Feed for thread: Vectorize Difference Between Two Sets of Points
enus
©19942014 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Mon, 26 Jan 2009 21:51:33 +0000
Vectorize Difference Between Two Sets of Points
http://www.mathworks.com/matlabcentral/newsreader/view_thread/243164#624130
Bill Woessner
I'm sure this question has been asked and answered dozens of times.<br>
But for the life of me, I can't find the answer.<br>
<br>
I have two sets of 2D points, call them A and B. They're stored in<br>
matrices such that size(A) = [M 2] and size(B) = [N 2]. For each a in<br>
A and b in B, I need to compute a  b. This is painfully slow using<br>
for loops. I've been trying to use repmat to speed it up, but so<br>
far... it's hideous:<br>
<br>
M = length(A);<br>
N = length(B);<br>
<br>
A2 = zeros(M, 1, 2);<br>
A2(:, 1, :) = A;<br>
A2 = repmat(A2, [1 N 1]);<br>
<br>
B2 = zeros(1, N, 2);<br>
B2(1, :, :) = B;<br>
B2 = repmat(B2, [M 1 1]);<br>
<br>
delta = A2  B2;<br>
<br>
A and B are relatively small so memory is not a concern. But speed<br>
is. I know there's probably a better way to accomplish this. Can<br>
someone please point me in the right direction?<br>
<br>
Thanks in advance,<br>
Bill Woessner

Mon, 26 Jan 2009 22:16:51 +0000
Re: Vectorize Difference Between Two Sets of Points
http://www.mathworks.com/matlabcentral/newsreader/view_thread/243164#624135
NZTideMan
On Jan 27, 10:51=A0am, Bill Woessner <woess...@gmail.com> wrote:<br>
> I'm sure this question has been asked and answered dozens of times.<br>
> But for the life of me, I can't find the answer.<br>
><br>
> I have two sets of 2D points, call them A and B. =A0They're stored in<br>
> matrices such that size(A) =3D [M 2] and size(B) =3D [N 2]. =A0For each a=<br>
in<br>
> A and b in B, I need to compute a  b. =A0This is painfully slow using<br>
> for loops. =A0I've been trying to use repmat to speed it up, but so<br>
> far... it's hideous:<br>
><br>
> M =3D length(A);<br>
> N =3D length(B);<br>
><br>
> A2 =3D zeros(M, 1, 2);<br>
> A2(:, 1, :) =3D A;<br>
> A2 =3D repmat(A2, [1 N 1]);<br>
><br>
> B2 =3D zeros(1, N, 2);<br>
> B2(1, :, :) =3D B;<br>
> B2 =3D repmat(B2, [M 1 1]);<br>
><br>
> delta =3D A2  B2;<br>
><br>
> A and B are relatively small so memory is not a concern. =A0But speed<br>
> is. =A0I know there's probably a better way to accomplish this. =A0Can<br>
> someone please point me in the right direction?<br>
><br>
> Thanks in advance,<br>
> Bill Woessner<br>
<br>
How about this:<br>
% Convert to complex vectors<br>
Ac=3DA(:,1) + i*A(:,2);<br>
Bc=3DB(:,1) + i*B(:,2);<br>
% Allocate storage<br>
D=3Dzeros(M,N);<br>
for ib=3D1:N<br>
D(:,ib)=3DAc  Bc(ib);<br>
end

Mon, 26 Jan 2009 22:19:02 +0000
Re: Vectorize Difference Between Two Sets of Points
http://www.mathworks.com/matlabcentral/newsreader/view_thread/243164#624138
someone
Bill Woessner <woessner@gmail.com> wrote in message <43737d629a774c6793d18f4112930c99@x16g2000prn.googlegroups.com>...<br>
> I'm sure this question has been asked and answered dozens of times.<br>
> But for the life of me, I can't find the answer.<br>
> <br>
> I have two sets of 2D points, call them A and B. They're stored in<br>
> matrices such that size(A) = [M 2] and size(B) = [N 2]. For each a in<br>
> A and b in B, I need to compute a  b. This is painfully slow using<br>
> for loops. I've been trying to use repmat to speed it up, but so<br>
> far... it's hideous:<br>
> <br>
> M = length(A);<br>
> N = length(B);<br>
> <br>
> A2 = zeros(M, 1, 2);<br>
> A2(:, 1, :) = A;<br>
> A2 = repmat(A2, [1 N 1]);<br>
> <br>
> B2 = zeros(1, N, 2);<br>
> B2(1, :, :) = B;<br>
> B2 = repmat(B2, [M 1 1]);<br>
> <br>
> delta = A2  B2;<br>
> <br>
> A and B are relatively small so memory is not a concern. But speed<br>
> is. I know there's probably a better way to accomplish this. Can<br>
> someone please point me in the right direction?<br>
> <br>
> Thanks in advance,<br>
> Bill Woessner<br>
<br>
How are you subtracting matricies of different sizes?

Mon, 26 Jan 2009 22:29:03 +0000
Re: Vectorize Difference Between Two Sets of Points
http://www.mathworks.com/matlabcentral/newsreader/view_thread/243164#624146
Matt
NZTideMan <mulgor@gmail.com> wrote in message <c646b7d0a6ca4a62a0db983f49e361ca@z6g2000pre.googlegroups.com>...<br>
> On Jan 27, 10:51=A0am, Bill Woessner <woess...@gmail.com> wrote:<br>
> > I'm sure this question has been asked and answered dozens of times.<br>
> > But for the life of me, I can't find the answer.<br>
> ><br>
> > I have two sets of 2D points, call them A and B. =A0They're stored in<br>
> > matrices such that size(A) =3D [M 2] and size(B) =3D [N 2]. =A0For each a=<br>
> in<br>
> > A and b in B, I need to compute a  b. =A0This is painfully slow using<br>
> > for loops. =A0I've been trying to use repmat to speed it up, but so<br>
> > far... it's hideous:<br>
> ><br>
> > M =3D length(A);<br>
> > N =3D length(B);<br>
> ><br>
> > A2 =3D zeros(M, 1, 2);<br>
> > A2(:, 1, :) =3D A;<br>
> > A2 =3D repmat(A2, [1 N 1]);<br>
> ><br>
> > B2 =3D zeros(1, N, 2);<br>
> > B2(1, :, :) =3D B;<br>
> > B2 =3D repmat(B2, [M 1 1]);<br>
> ><br>
> > delta =3D A2  B2;<br>
> ><br>
> > A and B are relatively small so memory is not a concern. =A0But speed<br>
> > is. =A0I know there's probably a better way to accomplish this. =A0Can<br>
> > someone please point me in the right direction?<br>
> ><br>
> > Thanks in advance,<br>
> > Bill Woessner<br>
> <br>
> How about this:<br>
> % Convert to complex vectors<br>
> Ac=3DA(:,1) + i*A(:,2);<br>
> Bc=3DB(:,1) + i*B(:,2);<br>
> % Allocate storage<br>
> D=3Dzeros(M,N);<br>
> for ib=3D1:N<br>
> D(:,ib)=3DAc  Bc(ib);<br>
> end<br>
<br>
You can avoid the forloop altogether using bsxfun<br>
<br>
Ac=A(:,1) + i*A(:,2);<br>
Bc=B(:,1) + i*B(:,2); <br>
Bc=Bc.';<br>
D=bsxfun(@minus, Ac,Bc);

Mon, 26 Jan 2009 22:33:02 +0000
Re: Vectorize Difference Between Two Sets of Points
http://www.mathworks.com/matlabcentral/newsreader/view_thread/243164#624148
Matt
"Matt " <mjacobson.removethis@xorantech.com> wrote in message <glldff$m5s$1@fred.mathworks.com>...<br>
><br>
> > How about this:<br>
> > % Convert to complex vectors<br>
> > Ac=3DA(:,1) + i*A(:,2);<br>
> > Bc=3DB(:,1) + i*B(:,2);<br>
> > % Allocate storage<br>
> > D=3Dzeros(M,N);<br>
> > for ib=3D1:N<br>
> > D(:,ib)=3DAc  Bc(ib);<br>
> > end<br>
> <br>
> You can avoid the forloop altogether using bsxfun<br>
> <br>
> Ac=A(:,1) + i*A(:,2);<br>
> Bc=B(:,1) + i*B(:,2); <br>
> Bc=Bc.';<br>
> D=bsxfun(@minus, Ac,Bc);<br>
<br>
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...

Mon, 26 Jan 2009 22:37:01 +0000
Re: Vectorize Difference Between Two Sets of Points
http://www.mathworks.com/matlabcentral/newsreader/view_thread/243164#624152
Matt Fig
Just in case the OP is wondering, to get a solution in the same form he has, use<br>
<br>
delta(:,:,1) = real(D);<br>
delta(:,:,2) = imag(D);<br>
<br>
<br>
<br>
<br>
{eZdiWW5ZVtttdtVV:^i^\e/]t#VjVbbt`iddj{ncXkVd]tZc]VdaNBZaXt

Mon, 26 Jan 2009 22:39:02 +0000
Re: Vectorize Difference Between Two Sets of Points
http://www.mathworks.com/matlabcentral/newsreader/view_thread/243164#624153
Roger Stafford
Bill Woessner <woessner@gmail.com> wrote in message <43737d629a774c6793d18f4112930c99@x16g2000prn.googlegroups.com>...<br>
> I'm sure this question has been asked and answered dozens of times.<br>
> But for the life of me, I can't find the answer.<br>
> <br>
> I have two sets of 2D points, call them A and B. They're stored in<br>
> matrices such that size(A) = [M 2] and size(B) = [N 2]. For each a in<br>
> A and b in B, I need to compute a  b. This is painfully slow using<br>
> for loops. I've been trying to use repmat to speed it up, but so<br>
> far... it's hideous:<br>
> <br>
> M = length(A);<br>
> N = length(B);<br>
> <br>
> A2 = zeros(M, 1, 2);<br>
> A2(:, 1, :) = A;<br>
> A2 = repmat(A2, [1 N 1]);<br>
> <br>
> B2 = zeros(1, N, 2);<br>
> B2(1, :, :) = B;<br>
> B2 = repmat(B2, [M 1 1]);<br>
> <br>
> delta = A2  B2;<br>
> <br>
> A and B are relatively small so memory is not a concern. But speed<br>
> is. I know there's probably a better way to accomplish this. Can<br>
> someone please point me in the right direction?<br>
> <br>
> Thanks in advance,<br>
> Bill Woessner<br>
<br>
[I,J] = ndgrid(1:M,1:N);<br>
delta = A(I,:)B(J,:);<br>
<br>
Roger Stafford

Mon, 26 Jan 2009 23:03:02 +0000
Re: Vectorize Difference Between Two Sets of Points
http://www.mathworks.com/matlabcentral/newsreader/view_thread/243164#624158
Matt Fig
Even with reshape, I think this should be faster than ndgrid:<br>
<br>
<br>
[I,J] = meshgrid(1:N,1:M);<br>
delta = reshape(A(J,:)B(I,:),M,N,2);<br>
<br>
<br>
<br>
<br>
<br>
`<vcYf\1c^Zvmvde}_XZvv%_gXX\v\lkfgkfDpXXkPlY`_ffe}\XvXd7bvf

Mon, 26 Jan 2009 23:12:02 +0000
Re: Vectorize Difference Between Two Sets of Points
http://www.mathworks.com/matlabcentral/newsreader/view_thread/243164#624161
Roger Stafford
"Matt Fig" <spamanon@yahoo.com> wrote in message <gllff6$6n4$1@fred.mathworks.com>...<br>
> Even with reshape, I think this should be faster than ndgrid:<br>
> <br>
> [I,J] = meshgrid(1:N,1:M);<br>
> delta = reshape(A(J,:)B(I,:),M,N,2);<br>
<br>
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.<br>
<br>
Roger Stafford

Mon, 26 Jan 2009 23:36:02 +0000
Re: Vectorize Difference Between Two Sets of Points
http://www.mathworks.com/matlabcentral/newsreader/view_thread/243164#624168
Matt Fig
"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <br>
> 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.<br>
> <br>
> Roger Stafford<br>
<br>
<br>
Hello Roger, <br>
<br>
Yes, you are correct, I should have made it clear I was thinking about inlining meshgrid, I pasted the wrong code. Sorry.<br>
<br>
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
clear all<br>
A = reshape(randperm(100),50,2);<br>
B = reshape(randperm(80),40,2);<br>
M = length(A);<br>
N = length(B);<br>
t = zeros(1,2);<br>
<br>
tic <br>
I = (1:N);<br>
J = (1:M)';<br>
I = I(ones(1,M),:);<br>
J = J(:,ones(N,1));<br>
delta1 = reshape(A(J,:)B(I,:),M,N,2);<br>
t(1) = toc;<br>
<br>
tic <br>
[I,J] = ndgrid(1:M,1:N);<br>
delta2 = A(I,:)B(J,:);<br>
t(2) = toc;<br>
<br>
all(delta1(:)==delta2(:))<br>
t/min(t)<br>
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>
<br>
ans =<br>
1<br>
ans =<br>
1 41.141<br>
<br>
<br>
<br>
<br>
JKGCEKRQVJQQVaQ;IaCWRCCaMO{'CaXCaQV[a"JNQGWhGPDE/NChoDOGPaa