How do I determine the distance between ALOT of points smoothly?

15 views (last 30 days)
Kenneth
Kenneth on 5 May 2014
Answered: Friedrich on 5 May 2014
So, I have an array consisting of about 82000 x and y coordinates. I want to find out how many "neighbours" each points has within a radius of some value. I wrote something that does this, however the code takes roughly two months to compile...
I've been doing it with two for-loops (not a good idea), one running alle the points one by one and another checking the distance from the one point to each of the 82000 others. This does not work in practice.
Any good suggestions?

Accepted Answer

Friedrich
Friedrich on 5 May 2014
Hi,
you can do it using one for loop, e.g.
n = 82000;
A = rand(n,2);
nb = zeros(n,1);
dist = 0.1^2;
tic
for i=1:n-1
tmp = sum(power(bsxfun(@minus,A,A(i,:)),2),2);
nb(i) = sum(tmp < dist)-1;
end
toc
This needs approx. 94 seconds on my machine.
One can also parallelize that code pretty good (requieres Parallel Computing Toolbox), e.g.
pool = parpool(4);
tic
spmd
for i=labindex:numlabs:n-1
tmp = sum(power(bsxfun(@minus,A,A(i,:)),2),2);
nb(i) = sum(tmp < dist)-1;
end
end
toc
delete(pool)
Which needs approx. 67 seconds on my machine (not taking the worker startup/shutdown time into account). When you need to deal with more points to check the speedup should be even better.

More Answers (2)

Matt J
Matt J on 5 May 2014
Edited: Matt J on 5 May 2014
You could try IPDM (link).

Image Analyst
Image Analyst on 5 May 2014
Try eliminating the square root in the distance calculation and finding how how many points distance squareds are within the radius squared (calculated before the loop):
radius2 = radius^2
for k = 1 : length(x)
....
distance2 = deltax^2 + deltay^2;
if distance2 <= radius2
count = count + 1

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!