Comparing two sets of coordinates

Hello

I have two different datasets from two particle scans of a silicon wafer. Each dataset contains a number of x- and y-coordinates from particles found on the wafer. I now want to compare the pre dataset with the post dataset, and see if there are two particles that lie very close (within 30 um) and therefore must be the same.

Right now I am basically comparing each of the points from the pre measurment with all the points from the post measurement and see if any match. However, each dataset can contain several thousands of coordinates, which tend to make the process somewhat slow. Any suggestions on how to make this faster and smarter?

Kind regards Martin

[Jan]

Several thousands does not sound as a very large problem. Please post the code you are using - otherwise suggestions for improvements are impossible. Wild guessing does help usually but increase the level of confusion only.

Answer 1

[Matt Tearle]

Can you please show your code? The approach you describe works in less than a second (~ 0.6) on my computer, with n = 10000. Code:

%  Make some data
n1 = 48;
n2 = 42;
x1 = rand(n1,1);
y1 = rand(n1,1);
x2 = rand(n2,1);
y2 = rand(n2,1);

figure
plot(x1,y1,'o',x2,y2,'x')

% calculate all pairwise distances
tic
changes = zeros(n1,n2);
for k = 1:n2
    changes(:,k) = (x1-x2(k)).^2 + (y1-y2(k)).^2;
end
toc

% find distances less than a given tolerance
tol = 0.001;
[j,k] = find(changes < tol);

line(x1(j),y1(j),'color','r','marker','.','linestyle','none')
line(x2(k),y2(k),'color','r','marker','.','linestyle','none')

Note that I'm using square (Euclidean) distance, to save on sqrt calculations.

Answer 2

[Martin]

Note to self: Prealocate memory

I basically did what Matt is doing in his code (however not as elegant). I did however not pre-allocate memory with the "zeros" command. Without pre-allocation: 2.5 s; with pre-allocation 15 ms.

Thank you very much Matt!!

[Matt Tearle]

Note to *everyone*: preallocate memory!

Thanks, Martin, for providing a perfect example of why: speedup factor = 167!

[Daniel Shub]

I would be curious what version of MATLAB this is in. I thought since r2011a that the cost of not preallocating was greatly reduced. Not to say that you shouldn't when you can, just curious if it is still problematic.