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

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?

Answer 1

[Friedrich]

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.

Answer 2

[Matt J]

You could try IPDM (link).

Answer 3

[Image Analyst]

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